Deduping a list of tuples, but keeping collisions as a list

Question

I am new to F# and functional languages in general. I'm having a hard time coming up with a recursive way to de-dupe a list of tuples in the following way:

 [("Apple", "500");
  ("Orange", "123");
  ("Pineapple", "300");
  ("Apple", "200");
  ("Apple", "100");
  ("Orange", "234");
  ("Cucumber", "900");]

  --becomes-->

  [("Apple", ["500", "200", "100"]);
  ("Orange", ["123", "234"]);
  ("Pineapple", ["300"]);
  ("Cucumber", ["900"]);]

Basically i want something like a map to a list. Explanations appreciated, as I am still having a hard time reading functional code.

Answer 1

The grouping can be performed using Seq.groupBy.

Running Seq.groupBy fst input yields:

seq
  [("Apple", seq [("Apple", "500"); ("Apple", "200"); ("Apple", "100")]);
   ("Orange", seq [("Orange", "123"); ("Orange", "234")]);
   ("Pineapple", seq [("Pineapple", "300")]);
   ("Cucumber", seq [("Cucumber", "900")])]

This is close, but not quite what you want because the second items of the resulting tuple contain the full input object, whereas your example indicates you want to pull out the second item from the list. You can get the second item from a tuple using snd, and since you have a sequence of tuples from which you wish to pull the second element, you can use Seq.map:

let grouped = Seq.groupBy fst input
              |> Seq.map (fun (a, b) -> (a, Seq.map snd b))

printfn "%A" grouped

// yields...
seq
  [("Apple", seq ["500"; "200"; "100"]); ("Orange", seq ["123"; "234"]);
   ("Pineapple", seq ["300"]); ("Cucumber", seq ["900"])]

Answer 2

Or you can use a List.fold to accomplish your goal:

let input = 
    [
        ("Apple", "500");
        ("Orange", "123");
        ("Pineapple", "300");
        ("Apple", "200");
        ("Apple", "100");
        ("Orange", "234");
        ("Cucumber", "900");
    ]

let output =
    List.fold (fun (acc : Map<string,string list>) (k,v) ->
        match Map.tryFind k acc with
        | Some x -> Map.add k (v :: x) acc
        | None -> Map.add k [v] acc
    ) Map.empty input
    // If you want a list instead of a map in the end, uncomment the next line.
    // |> Map.toList 

which yields:

val output : Map = map [("Apple", ["100"; "200"; "500"]); ("Cucumber", ["900"]); ("Orange", ["234"; "123"]); ("Pineapple", ["300"])]

While not as to the point as the groupBy version, the fold is your Swiss army knife for many occasions and worth being used to.

And - while there are those nice ready made functions like fold coming for free with F#, if you want a recursive definition, you can write your own fold as a learning exercise. It could look like this and should work with the same lambda I used above.

let rec myFold folder acc values =
    match values with
    | [] -> acc
    | (x::xs) -> myFold folder (folder acc x) xs