CODEWITHSUNDEEP
f#
user483036
user483036

Reputation:

efficient way to create map of lists in functional style

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

Upvotes: 3

Views: 1699

Answers (4)

Tarmil
Tarmil

Reputation: 11362

For fun, an implementation using a query expression:

let res =
    query { for (k, v) in data do
            groupValBy v k into g
            select (g.Key, List.ofSeq g) }
    |> Map.ofSeq

Upvotes: 1

jbtule
jbtule

Reputation: 31799

use LINQ in F#, LINQ is functional.

open System.Linq

let data =[
  1,2
  1,5
  2,1
  2,2
  1,1
]

let lookup = data.ToLookup(fst,snd)

lookup.[1] //seq [2;5;1]
lookup.[2] //seq [1;2

Upvotes: 2

Lee
Lee

Reputation: 144136

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

Upvotes: 3

Daniel
Daniel

Reputation: 47904

[
  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

Upvotes: 7

Related Questions