FoldBy Combinator

Suggestion for a core library function.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39:

module List =

    /// <summary>
    ///     fold by key combinator
    /// </summary>
    /// <param name="proj">Key projection function.</param>
    /// <param name="folder">Folding function.</param>
    /// <param name="init">Initial state function.</param>
    /// <param name="ts">Input list.</param>
    let foldBy (proj : 'T -> 'Key) (folder : 'State -> 'T -> 'State) (init : unit -> 'State) (ts : 'T list) =
        let dict = new System.Collections.Generic.Dictionary<'Key, 'State ref>()

        let rec aux = function
            | [] -> ()
            | t :: ts ->
                let k = proj t
                let ok, cached = dict.TryGetValue k
                let state = 
                    if ok then cached 
                    else 
                        let state = ref <| init ()
                        dict.[k] <- state
                        state

                state := folder state.Value t
                aux ts

        aux ts

        dict |> Seq.map (fun kv -> kv.Key, kv.Value.Value) |> Seq.toList


    // example: implementing other known combinators in terms of foldBy

    let groupBy (proj : 'T -> 'Key) (ts : 'T list) =
        foldBy proj (fun ts t -> t :: ts) (fun () -> []) ts

    let countBy (proj : 'T -> 'Key) (ts : 'T list) =
        foldBy proj (fun n _ -> n + 1) (fun _ -> 0) ts

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val foldBy : proj:('T -> 'Key) -> folder:('State -> 'T -> 'State) -> init:(unit -> 'State) -> ts:'T list -> ('Key * 'State) list (requires equality)

Full name: Script.List.foldBy

<summary>
fold by key combinator
</summary>
<param name="proj">Key projection function.</param>
<param name="folder">Folding function.</param>
<param name="init">Initial state function.</param>
<param name="ts">Input list.</param>

val proj : ('T -> 'Key) (requires equality)

val folder : ('State -> 'T -> 'State)

val init : (unit -> 'State)

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

val ts : 'T list

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

val dict : System.Collections.Generic.Dictionary<'Key,'State ref> (requires equality)

namespace System

namespace System.Collections

namespace System.Collections.Generic

Multiple items
type Dictionary<'TKey,'TValue> =
  new : unit -> Dictionary<'TKey, 'TValue> + 5 overloads
  member Add : key:'TKey * value:'TValue -> unit
  member Clear : unit -> unit
  member Comparer : IEqualityComparer<'TKey>
  member ContainsKey : key:'TKey -> bool
  member ContainsValue : value:'TValue -> bool
  member Count : int
  member GetEnumerator : unit -> Enumerator<'TKey, 'TValue>
  member GetObjectData : info:SerializationInfo * context:StreamingContext -> unit
  member Item : 'TKey -> 'TValue with get, set
  ...
  nested type Enumerator
  nested type KeyCollection
  nested type ValueCollection

Full name: System.Collections.Generic.Dictionary<_,_>

--------------------
System.Collections.Generic.Dictionary() : unit
System.Collections.Generic.Dictionary(capacity: int) : unit
System.Collections.Generic.Dictionary(comparer: System.Collections.Generic.IEqualityComparer<'TKey>) : unit
System.Collections.Generic.Dictionary(dictionary: System.Collections.Generic.IDictionary<'TKey,'TValue>) : unit
System.Collections.Generic.Dictionary(capacity: int, comparer: System.Collections.Generic.IEqualityComparer<'TKey>) : unit
System.Collections.Generic.Dictionary(dictionary: System.Collections.Generic.IDictionary<'TKey,'TValue>, comparer: System.Collections.Generic.IEqualityComparer<'TKey>) : unit

Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>

val aux : ('T list -> unit)

val t : 'T

val k : 'Key (requires equality)

val ok : bool

val cached : 'State ref

System.Collections.Generic.Dictionary.TryGetValue(key: 'Key, value: byref<'State ref>) : bool

val state : 'State ref

property Ref.Value: 'State

module Seq

from Microsoft.FSharp.Collections

val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val kv : System.Collections.Generic.KeyValuePair<'Key,'State ref> (requires equality)

property System.Collections.Generic.KeyValuePair.Key: 'Key

property System.Collections.Generic.KeyValuePair.Value: 'State ref

val toList : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.Seq.toList

val groupBy : proj:('T -> 'Key) -> ts:'T list -> ('Key * 'T list) list (requires equality)

Full name: Script.List.groupBy

val countBy : proj:('T -> 'Key) -> ts:'T list -> ('Key * int) list (requires equality)

Full name: Script.List.countBy

val n : int

Raw view Test code New version

More information

Link:	http://fssnip.net/nY
Posted:	10 years ago
Author:	Eirik Tsarpalis
Tags:	collections , core , combinators