Already existing high-order function for this algorithm?

Question

I've come up with this simple algorithm (convert list of tuples to a map collection of keys to lists) that I needed in my F# code:

let MergeIntoMap<'K,'V when 'K: comparison>(from: seq<'K*'V>): Map<'K,seq<'V>>=
    let keys = from.Select(fun (k,v) -> k)
    let keyValuePairs = seq {
        for key in keys do
            let valsForKey = from.Where(fun (k,v) -> key = k).Select(fun (k,v) -> v) |> seq
            yield key,valsForKey
    }
    keyValuePairs |> Map.ofSeq

Example input:

[ ("a", 1); ("b", 2), ("a", 3) ]

Output:

dict [ ("a", [1; 3]), ("b", [2]) ]

And I was thinking this must be something that is already in the BCL or F#'s set of high order functions maybe? If yes, can someone reference me to it? Because I'm sure my code is not very efficient as it is...

score 3 · Answer 1 · edited May 23 '17 at 12:25

3

It seems you want to get something like that

let toGroupMap x = 
    x
    |> Seq.groupBy fst 
    |> Seq.map 
        (fun (k,v) -> k, v |> Seq.map snd |> Seq.toArray)
    |> Map.ofSeq

fsi:

val toGroupMap : x:seq<'a * 'b> -> Map<'a,'b []> when 'a : comparison
val input : (string * int) list = [("a", 1); ("b", 2); ("a", 3)]
val output : Map<string,int []> = map [("a", [|1; 3|]); ("b", [|2|])]

Edit

As written Fyodor Soikin in the comments, there is a extension method ToLookup, which probably does what you need.

open System.Linq

let output = input.ToLookup(fst, snd)

You can read here about the difference between ILookup and IDictionary interfaces

edited May 23 '17 at 12:25

Community

1
1

answered Feb 26 '17 at 07:23

FoggyFinder

2,230
2
20
34

so there's no higher order function that already does this? why is your solution better than mine? are you suggesting yours is more efficient? – ympostor Feb 26 '17 at 09:13
5

Two things look better in this code than your original algorithm. First, `Seq.groupBy` is O(N), whereas yours is O(N^2) since it runs through the entire `from` sequence for each key. Second, Foggy Finder's code looks much more idiomatic. I.e., as an experienced F# coder, I can read it and immediately see what it's doing. Whereas your code that makes heavy use of LINQ is more C#-like and more opaque, and it would take me quite a bit longer to see what it does. Code that's easier to read leads to better understanding of the program, which in turn leads to far fewer bugs in the long run. – rmunn Feb 26 '17 at 09:27
5

Wait, doesn't `.ToLookup` do exactly that? – Fyodor Soikin Feb 26 '17 at 13:49

Already existing high-order function for this algorithm?

1 Answers1