5 people like it.

Generic Collections, Type Classes and friends

A crazy experiment for "Scalable" collections. Inspired by the paper "Fighting Bit Rot with Types"

 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: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
78: 
79: 
80: 
81: 
82: 
83: 
84: 
85: 
86: 

// http://lampwww.epfl.ch/~odersky/papers/fsttcs2009.pdf
open System
open System.Text
open System.Collections.Generic

// Type classes encoding for iteration and building
type Iterable<'From, 'Elem> = Iterable of (('Elem -> unit) -> unit) 
type Iter = Iter with
    static member inline ($) (_ : Iter, values : 'Elem []) = 
        Iterable (fun f -> 
                    for value in values do
                        f value)
    static member inline ($) (_ : Iter, values : 'Elem list) = 
        Iterable (fun f -> 
                    for value in values do
                        f value)
    static member inline ($) (_ : Iter, values : Map<_, _>) = 
        Iterable (fun f -> 
                    for value in Map.toSeq values do
                        f value)
    static member inline ($) (_ : Iter, values : String) = 
        Iterable (fun f -> 
                    for value in values do
                        f value)

type CanBuildFrom<'From, 'Elem, 'To> = CanBuildFrom of ('From -> Builder<'Elem, 'To>)  
and Builder<'Elem, 'To> = Builder of ('Elem -> unit) * (unit -> 'To)
 
type CanBuild = CanBuild with

    static member inline (?<-) (_ : Map<_, _>, _ : CanBuild, _ : Map<'Key, 'Value>) = fun (_ : 'Key * 'Value) ->
        CanBuildFrom (fun _ ->
            let mapRef = ref Map.empty
            Builder ((fun (key, value) -> mapRef := Map.add key value !mapRef), fun () -> !mapRef))

    static member inline (?<-) (_ : Map<_, _>, _ : CanBuild, _ : 'Elem []) = fun (_ : 'Elem) ->
        CanBuildFrom (fun _ ->
            let list = new List<'Elem>()
            Builder ((fun elem -> list.Add elem), fun () -> list.ToArray()))

    static member inline (?<-) (_ : _ [], _ : CanBuild, _ : 'Elem []) = fun (_ : 'Elem) ->
        CanBuildFrom (fun _ ->
            let list = new List<'Elem>()
            Builder ((fun elem -> list.Add elem), fun () -> list.ToArray()))

    static member inline (?<-) (_ : _ list, _ : CanBuild, _ : 'Elem list) = fun (_ : 'Elem) ->
        CanBuildFrom (fun _ -> 
            let listRef = ref []
            Builder ((fun elem -> listRef := elem :: !listRef), fun () -> List.rev !listRef))
 
    static member inline (?<-) (_ : String, _ : CanBuild, _ : String) = fun (_ : Char) ->
        CanBuildFrom (fun _ ->
            let stringBuilder = new StringBuilder()
            Builder ((fun (elem : char) -> stringBuilder.Append elem |> ignore), fun () -> stringBuilder.ToString()))
 
    static member inline (?<-) (_ : String, _ : CanBuild, _ : 'Elem []) = fun (_ : 'Elem) ->
        CanBuildFrom (fun _ ->
            let list = new List<'Elem>()
            Builder ((fun elem -> list.Add elem), fun () -> list.ToArray()))
 
// Generic high-order functions
let inline map (f : ^A -> ^B) col : ^R =
    let (CanBuildFrom getBuilder) = (col ? (CanBuild) <- Unchecked.defaultof< ^R> ) Unchecked.defaultof< ^B>
    let (Builder (add, result)) = getBuilder col
    let (Iterable iter) = Iter $ col
    iter (fun x -> add (f x))
    result()

let inline filter (f : ^A -> bool) col : ^R =
    let (CanBuildFrom getBuilder) = (col ? (CanBuild) <- Unchecked.defaultof< ^R> ) Unchecked.defaultof< ^A>
    let (Builder (add, result)) = getBuilder col
    let (Iterable iter) = Iter $ col
    iter (fun x -> if f x then add x)
    result()
 
// Examples
let testMap = Map.add 1 2 Map.empty
let m : Map<int, int> = map (fun (x, y) -> (y, x)) testMap // map [(2, 1)]
let m' : int [] = map (fun (x, y) -> x + y) testMap // [|3|]
map (fun x -> x + 1) [|1..3|] // [|2; 3; 4|]
map (fun x -> x + 1) [1..3] // [2; 3; 4]
let s : String = map (fun c -> Char.ToUpper c) "abc" // "ABC"
map (fun c -> int c) "abc" // [|97; 98; 99|]

filter (fun x -> x > 2) [1..3] // [3]
let m'' : Map<int, int> = filter (fun (x, y) -> x = y) testMap // map []
namespace System
namespace System.Text
namespace System.Collections
namespace System.Collections.Generic
Multiple items
union case Iterable.Iterable: (('Elem -> unit) -> unit) -> Iterable<'From,'Elem>

--------------------
type Iterable<'From,'Elem> = | Iterable of (('Elem -> unit) -> unit)

Full name: Script.Iterable<_,_>
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
Multiple items
union case Iter.Iter: Iter

--------------------
type Iter =
  | Iter
  static member ( $ ) : Iter * values:'Elem [] -> Iterable<'a,'Elem>
  static member ( $ ) : Iter * values:'Elem list -> Iterable<'a,'Elem>
  static member ( $ ) : Iter * values:Map<'a,'b> -> Iterable<'c,('a * 'b)> (requires comparison)
  static member ( $ ) : Iter * values:String -> Iterable<'a,char>

Full name: Script.Iter
val values : 'Elem []
val f : ('Elem -> unit)
val value : 'Elem
val values : 'Elem list
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val values : Map<'a,'b> (requires comparison)
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
val f : ('a * 'b -> unit) (requires comparison)
val value : 'a * 'b (requires comparison)
val toSeq : table:Map<'Key,'T> -> seq<'Key * 'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.toSeq
val values : String
Multiple items
type String =
  new : value:char -> string + 7 overloads
  member Chars : int -> char
  member Clone : unit -> obj
  member CompareTo : value:obj -> int + 1 overload
  member Contains : value:string -> bool
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EndsWith : value:string -> bool + 2 overloads
  member Equals : obj:obj -> bool + 2 overloads
  member GetEnumerator : unit -> CharEnumerator
  member GetHashCode : unit -> int
  ...

Full name: System.String

--------------------
String(value: nativeptr<char>) : unit
String(value: nativeptr<sbyte>) : unit
String(value: char []) : unit
String(c: char, count: int) : unit
String(value: nativeptr<char>, startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int) : unit
String(value: char [], startIndex: int, length: int) : unit
String(value: nativeptr<sbyte>, startIndex: int, length: int, enc: Encoding) : unit
val f : (char -> unit)
val value : char
Multiple items
union case CanBuildFrom.CanBuildFrom: ('From -> Builder<'Elem,'To>) -> CanBuildFrom<'From,'Elem,'To>

--------------------
type CanBuildFrom<'From,'Elem,'To> = | CanBuildFrom of ('From -> Builder<'Elem,'To>)

Full name: Script.CanBuildFrom<_,_,_>
type Builder<'Elem,'To> = | Builder of ('Elem -> unit) * (unit -> 'To)

Full name: Script.Builder<_,_>
Multiple items
union case Builder.Builder: ('Elem -> unit) * (unit -> 'To) -> Builder<'Elem,'To>

--------------------
type Builder<'Elem,'To> = | Builder of ('Elem -> unit) * (unit -> 'To)

Full name: Script.Builder<_,_>
Multiple items
union case CanBuild.CanBuild: CanBuild

--------------------
type CanBuild =
  | CanBuild
  static member ( ?<- ) : Map<'a,'b> * CanBuild * Map<'Key,'Value> -> ('Key * 'Value -> CanBuildFrom<'c,('d * 'e),Map<'d,'e>>) (requires comparison and comparison and comparison)
  static member ( ?<- ) : Map<'a,'b> * CanBuild * 'Elem [] -> ('Elem -> CanBuildFrom<'c,'Elem,'Elem []>) (requires comparison)
  static member ( ?<- ) : 'a [] * CanBuild * 'Elem [] -> ('Elem -> CanBuildFrom<'b,'Elem,'Elem []>)
  static member ( ?<- ) : 'a list * CanBuild * 'Elem list -> ('Elem -> CanBuildFrom<'b,'c,'c list>)
  static member ( ?<- ) : String * CanBuild * String -> (Char -> CanBuildFrom<'a,char,string>)
  static member ( ?<- ) : String * CanBuild * 'Elem [] -> ('Elem -> CanBuildFrom<'a,'Elem,'Elem []>)

Full name: Script.CanBuild
val mapRef : Map<'d,'e> ref (requires comparison)
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 empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty
val key : 'd (requires comparison)
val value : 'e
val add : key:'Key -> value:'T -> table:Map<'Key,'T> -> Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.add
Multiple items
val list : List<'Elem>

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
type List<'T> =
  new : unit -> List<'T> + 2 overloads
  member Add : item:'T -> unit
  member AddRange : collection:IEnumerable<'T> -> unit
  member AsReadOnly : unit -> ReadOnlyCollection<'T>
  member BinarySearch : item:'T -> int + 2 overloads
  member Capacity : int with get, set
  member Clear : unit -> unit
  member Contains : item:'T -> bool
  member ConvertAll<'TOutput> : converter:Converter<'T, 'TOutput> -> List<'TOutput>
  member CopyTo : array:'T[] -> unit + 2 overloads
  ...
  nested type Enumerator

Full name: System.Collections.Generic.List<_>

--------------------
List() : unit
List(capacity: int) : unit
List(collection: IEnumerable<'T>) : unit
val elem : 'Elem
List.Add(item: 'Elem) : unit
List.ToArray() : 'Elem []
val listRef : 'c list ref
val elem : 'c
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
type Char =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 1 overload
    static val MaxValue : char
    static val MinValue : char
    static member ConvertFromUtf32 : utf32:int -> string
    static member ConvertToUtf32 : highSurrogate:char * lowSurrogate:char -> int + 1 overload
    static member GetNumericValue : c:char -> float + 1 overload
    ...
  end

Full name: System.Char
val stringBuilder : StringBuilder
Multiple items
type StringBuilder =
  new : unit -> StringBuilder + 5 overloads
  member Append : value:string -> StringBuilder + 18 overloads
  member AppendFormat : format:string * arg0:obj -> StringBuilder + 4 overloads
  member AppendLine : unit -> StringBuilder + 1 overload
  member Capacity : int with get, set
  member Chars : int -> char with get, set
  member Clear : unit -> StringBuilder
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EnsureCapacity : capacity:int -> int
  member Equals : sb:StringBuilder -> bool
  ...

Full name: System.Text.StringBuilder

--------------------
StringBuilder() : unit
StringBuilder(capacity: int) : unit
StringBuilder(value: string) : unit
StringBuilder(value: string, capacity: int) : unit
StringBuilder(capacity: int, maxCapacity: int) : unit
StringBuilder(value: string, startIndex: int, length: int, capacity: int) : unit
val elem : char
Multiple items
val char : value:'T -> char (requires member op_Explicit)

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

--------------------
type char = Char

Full name: Microsoft.FSharp.Core.char
StringBuilder.Append(value: char []) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: obj) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint64) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint32) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint16) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: decimal) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: float) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: float32) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: int64) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: int) : StringBuilder
   (+0 other overloads)
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
StringBuilder.ToString() : string
StringBuilder.ToString(startIndex: int, length: int) : string
val map : f:('A -> 'B) -> col:'a -> 'R (requires member ( ?<- ) and member ( $ ))

Full name: Script.map
val f : ('A -> 'B)
val col : 'a (requires member ( ?<- ) and member ( $ ))
val getBuilder : ('a -> Builder<'B,'R>) (requires member ( ?<- ) and member ( $ ))
module Unchecked

from Microsoft.FSharp.Core.Operators
val defaultof<'T> : 'T

Full name: Microsoft.FSharp.Core.Operators.Unchecked.defaultof
val add : ('B -> unit)
val result : (unit -> 'R) (requires member ( ?<- ) and member ( $ ))
val iter : (('A -> unit) -> unit)
val x : 'A
val filter : f:('A -> bool) -> col:'a -> 'R (requires member ( ?<- ) and member ( $ ))

Full name: Script.filter
val f : ('A -> bool)
type bool = Boolean

Full name: Microsoft.FSharp.Core.bool
val getBuilder : ('a -> Builder<'A,'R>) (requires member ( ?<- ) and member ( $ ))
val add : ('A -> unit)
val testMap : Map<int,int>

Full name: Script.testMap
val m : Map<int,int>

Full name: Script.m
Multiple items
val int : value:'T -> int (requires member op_Explicit)

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

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
val x : int
val y : int
val m' : int []

Full name: Script.m'
val s : String

Full name: Script.s
val c : char
Char.ToUpper(c: char) : char
Char.ToUpper(c: char, culture: Globalization.CultureInfo) : char
val m'' : Map<int,int>

Full name: Script.m''
Raw view Test code New version

More information

Link:http://fssnip.net/hk
Posted:11 years ago
Author:Nick Palladinos
Tags: type classes , collections , scala

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.