Group totals in F# - easy with sequences, is it possible with lists?

Given a sequence of a group id/value tuples, it was easy to calculate group totals (pretty much the same way I would do it with C# and LINQ):

let items = ["g1",5; "g2",10; "g1",20]

let groupsums = 
    items  
    |> S开发者_如何学JAVAeq.groupBy (fun x -> fst x) 
    |> Seq.map (fun (g, s) -> Seq.fold (fun acc x -> acc + snd x) 0 s)

But being new to F#, I can't see a way to so the same with lists. Do I have to use mutable variables, or is there a functional way to do the same with lists?

There is no built in List.groupBy. A number of F# built in types have functions that are assigned the seq version of said function. e.g. from list.fs

let inline sumBy f (list : list<_>) = Seq.sumBy f list

I'm pretty sure the designers of F# had many discussions about what to duplicate for the sake of consistency and what to omit for for sake of DRY. I personally wish they stuck with DRY.

If you want to make your own "functional" List.groupBy I'd use map and list.

let groupBy list =
    list 
    |> List.fold (fun group (g, x) -> 
        match group |> Map.tryFind g with
        | Some(s) -> group |> Map.remove g |> Map.add g (x::s)
        | None -> group |> Map.add g [x]
        ) Map.empty
    |> Map.toList 

let groupsums = groupBy >> List.map (snd >> List.sum)

You can skip keeping lists if you only need the sum.

let groupAndSumBy list =
    list 
    |> List.fold (fun group (g, x) -> 
        match group |> Map.tryFind g with
        | Some(s) -> group |> Map.remove g |> Map.add g (x + s)
        | None -> group |> Map.add g x
        ) Map.empty
    |> Map.toList
    |> List.map snd

Output

> groupsums items;;
val it : int list = [25; 10]

> groupAndSumBy items;;
val it : int list = [25; 10]

While there's nothing wrong with gradbot's solution, I'd just keep it simple and use Seq.toList to convert sequences back to lists when desired. So you could rewrite your definition as:

let groupsums =
    items
    |> Seq.groupBy fst
    |> Seq.toList
    |> List.map (fun (_,s) -> Seq.sumBy snd s)

Although I would use kvb's suggestion, if you're going to roll your own, I suggest using Dictionary instead of Map. In my testing it was at least 400% faster.

let groupBy f (list:list<_>) =
  let dict = Dictionary()
  for v in list do
    let k = f v
    match dict.TryGetValue(k) with
    | true, l -> dict.[k] <- v :: l
    | _ -> dict.Add(k, [v])
  dict |> Seq.map (|KeyValue|) |> Seq.toList

Or:

let groupSumBy (list:list<_>) =
  let dict = Dictionary()
  for k, v in list do
    match dict.TryGetValue(k) with
    | true, n -> dict.[k] <- v + n
    | _ -> dict.Add(k, v)
  dict |> Seq.map (|KeyValue|) |> Seq.toList

By ref version:

let groupSumBy (list:list<_>) =
  let dict = Dictionary()
  let mutable n = 0
  for k, v in list do
    match dict.TryGetValue(k, &n) with
    | true -> dict.[k] <- v + n
    | false -> dict.Add(k, v)
  dict |> Seq.map (|KeyValue|) |> Seq.toList