Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

efficient way to create map of lists in functional style

Tags:

f#

Given a dataset, for example a CSV file that might look like this:

x,y
1,2
1,5
2,1
2,2
1,1
...

I wish to create a map of lists containing the y's for a given x... The result could look like this:

{1:[2,5,1], 2:[1,2]}

In python this would be straight forward to do in an imperative manner.. and would probably look somewhat like this:

d = defaultdict(list)
for x,y in csv_data:
    d[x].append(y)

How would you go about achieving the same using functional programming techniques in F#? Is it possible to do it as short, efficient and concise (and read-able) as in the given python example, using only functional style?, or would you have to fall back to imperative programming style with mutable data structures..?

Note: this is not a homework assignment, just me trying to wrap my head around functional programming

EDIT: My conclusion based on answers thus far

I tried timing each of the provided answers on a relative big csv file, just to get a feeling of the performance.. Furthermore I did a small test with the imperative approach:

let res = new Dictionary<string, List<string>>()
for row in l do
    if (res.ContainsKey(fst row) = false) then 
        res.[fst row] <- new List<string>()
    res.[fst row].Add(snd row)

The imperative approach completed in ~0.34 sec.

I think that the answer provided by Lee is the most general FP one, however the running time was ~4sec.

The answer given by Daniel ran in ~1.55sec.

And at last the answer given by jbtule ran in ~0.26. (I find it very interesting that it beat the imperative approach)

I used 'System.Diagnostics.Stopwatch()' for timing, and the code is executed as F# 3.0 in .Net 4.5

EDIT2: fixed stupid error in imperative f# code, and ensured that it uses the same list as the other solutions


2 Answers

[
  1,2
  1,5
  2,1
  2,2
  1,1
]
|> Seq.groupBy fst
|> Seq.map (fun (x, ys) -> x, [for _, y in ys -> y])
|> Map.ofSeq
like image 154
Daniel Avatar answered Jan 29 '26 06:01

Daniel


let addPair m (x, y) =
    match Map.tryFind x m with
    | Some(l) -> Map.add x (y::l) m
    | None -> Map.add x [y] m

let csv (pairs : (int * int) list) = List.fold addPair Map.empty pairs

Note this adds the y values to the list in reverse order

like image 29
Lee Avatar answered Jan 29 '26 08:01

Lee



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!