5 people like it.

# JoinList

A JoinList is a variation on the list type that offers a constant time append operation.

 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: open System open System.Collections open System.Collections.Generic open System.Diagnostics.Contracts type JoinList<'a> = | Empty | Unit of 'a | Join of JoinList<'a> * JoinList<'a> * int (* the total length of the JoinList *) with interface IEnumerable<'a> with member this.GetEnumerator() = let enumerable = seq { match this with | Empty -> () | Unit x -> yield x | Join(x,y,_) -> yield! x :> seq<'a> yield! y :> seq<'a> } enumerable.GetEnumerator() member this.GetEnumerator() = let enumerable = seq { match this with | Empty -> () | Unit x -> yield x | Join(x,y,_) -> yield! x :> seq<'a> yield! y :> seq<'a> } enumerable.GetEnumerator() :> IEnumerator module JoinList = let empty<'a> : JoinList<'a> = Empty let isEmpty l = match l with Empty -> true | _ -> false let length l = match l with | Empty -> 0 | Unit _ -> 1 | Join(_,_,l) -> l let singleton x = Unit x let ofSeq s = Seq.fold (fun xs x -> match xs with | Join(_,_,l) -> Join(xs, Unit x, l+1) | _ -> Join(Unit x, Empty, 1)) Empty s let toSeq (l:JoinList<_>) = l :> seq<_> let toList (l:JoinList<_>) = List.ofSeq l let toArray (l:JoinList<_>) = Array.ofSeq l let rec equal left right = match left with | Empty -> match right with Empty -> true | _ -> false | Unit x -> match right with Unit y -> x = y | _ -> false | Join(x,y,l) -> match right with | Join(x',y',l') -> l = l' && equal x x' && equal y y' // TODO: || iterate each and compare the values. | _ -> false let cons hd tl = Join(Unit hd, tl, length tl + 1) let append left right = Join(left, right, length left + length right) let rec head l = match l with | Unit x -> x | Join(x,y,_) -> head x | _ -> failwith "JoinList.head: empty list" let tail (l:JoinList<'a>) : JoinList<'a> = let rec step (xs:JoinList<'a>) (acc:JoinList<'a>) : JoinList<'a> = match xs with | Empty -> Empty | Unit _ -> acc | Join(x,y,_) -> step x (append y acc) step l Empty type JoinList<'a> with static member op_Equality(left, right) = JoinList.equal left right static member op_Nil() = JoinList.empty static member op_Cons(hd, tl) = JoinList.cons hd tl static member op_Append(left, right) = JoinList.append left right
namespace System
namespace System.Collections
namespace System.Collections.Generic
namespace System.Diagnostics
namespace System.Diagnostics.Contracts
type JoinList<'a> =
| Empty
| Unit of 'a
| Join of JoinList<'a> * JoinList<'a> * int
interface IEnumerable<'a>
static member ( @ ) : left:JoinList<'a0> * right:JoinList<'a0> -> JoinList<'a0>
static member op_Cons : hd:'a0 * tl:JoinList<'a0> -> JoinList<'a0>
static member ( = ) : left:JoinList<'a0> * right:JoinList<'a0> -> bool (requires equality)
static member ( [] ) : unit -> JoinList<'a0>

Full name: Script.JoinList<_>
union case JoinList.Empty: JoinList<'a>
union case JoinList.Unit: 'a -> JoinList<'a>
union case JoinList.Join: JoinList<'a> * JoinList<'a> * int -> JoinList<'a>
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<_>
Multiple items
type IEnumerable =
member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable

--------------------
type IEnumerable<'T> =
member GetEnumerator : unit -> IEnumerator<'T>

Full name: System.Collections.Generic.IEnumerable<_>
val this : JoinList<'a>
override JoinList.GetEnumerator : unit -> IEnumerator<'a>

Full name: Script.JoinList`1.GetEnumerator
val enumerable : seq<'a>
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

--------------------
type seq<'T> = IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val x : 'a
val x : JoinList<'a>
val y : JoinList<'a>
IEnumerable.GetEnumerator() : IEnumerator<'a>
override JoinList.GetEnumerator : unit -> IEnumerator

Full name: Script.JoinList`1.GetEnumerator
Multiple items
type IEnumerator =
member Current : obj
member MoveNext : unit -> bool
member Reset : unit -> unit

Full name: System.Collections.IEnumerator

--------------------
type IEnumerator<'T> =
member Current : 'T

Full name: System.Collections.Generic.IEnumerator<_>
val empty<'a> : JoinList<'a>

Full name: Script.JoinList.empty
val isEmpty : l:JoinList<'a> -> bool

Full name: Script.JoinList.isEmpty
val l : JoinList<'a>
val length : l:JoinList<'a> -> int

Full name: Script.JoinList.length
val l : int
val singleton : x:'a -> JoinList<'a>

Full name: Script.JoinList.singleton
val ofSeq : s:seq<'a> -> JoinList<'a>

Full name: Script.JoinList.ofSeq
val s : seq<'a>
module Seq

from Microsoft.FSharp.Collections
val fold : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> 'State

Full name: Microsoft.FSharp.Collections.Seq.fold
val xs : JoinList<'a>
val toSeq : l:JoinList<'a> -> seq<'a>

Full name: Script.JoinList.toSeq
val toList : l:JoinList<'a> -> 'a list

Full name: Script.JoinList.toList
Multiple items
type List<'T> =
new : unit -> List<'T> + 2 overloads
member Add : item:'T -> unit
member AddRange : collection:IEnumerable<'T> -> unit
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 ofSeq : source:seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
val toArray : l:JoinList<'a> -> 'a []

Full name: Script.JoinList.toArray
type Array =
member Clone : unit -> obj
member CopyTo : array:Array * index:int -> unit + 1 overload
member GetEnumerator : unit -> IEnumerator
member GetLength : dimension:int -> int
member GetLongLength : dimension:int -> int64
member GetLowerBound : dimension:int -> int
member GetUpperBound : dimension:int -> int
member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
member Initialize : unit -> unit
member IsFixedSize : bool
...

Full name: System.Array
val ofSeq : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofSeq
val equal : left:JoinList<'a> -> right:JoinList<'a> -> bool (requires equality)

Full name: Script.JoinList.equal
val left : JoinList<'a> (requires equality)
val right : JoinList<'a> (requires equality)
val x : 'a (requires equality)
val y : 'a (requires equality)
val x : JoinList<'a> (requires equality)
val y : JoinList<'a> (requires equality)
val x' : JoinList<'a> (requires equality)
val y' : JoinList<'a> (requires equality)
val l' : int
val cons : hd:'a -> tl:JoinList<'a> -> JoinList<'a>

Full name: Script.JoinList.cons
val hd : 'a
val tl : JoinList<'a>
val append : left:JoinList<'a> -> right:JoinList<'a> -> JoinList<'a>

Full name: Script.JoinList.append
val left : JoinList<'a>
val right : JoinList<'a>
val head : l:JoinList<'a> -> 'a

val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val tail : l:JoinList<'a> -> JoinList<'a>

Full name: Script.JoinList.tail
val step : (JoinList<'a> -> JoinList<'a> -> JoinList<'a>)
val acc : JoinList<'a>
Multiple items
module JoinList

from Script

--------------------
type JoinList<'a> =
| Empty
| Unit of 'a
| Join of JoinList<'a> * JoinList<'a> * int
interface IEnumerable<'a>
static member ( @ ) : left:JoinList<'a0> * right:JoinList<'a0> -> JoinList<'a0>
static member op_Cons : hd:'a0 * tl:JoinList<'a0> -> JoinList<'a0>
static member ( = ) : left:JoinList<'a0> * right:JoinList<'a0> -> bool (requires equality)
static member ( [] ) : unit -> JoinList<'a0>

Full name: Script.JoinList<_>
static member JoinList.op_Cons : hd:'a0 * tl:JoinList<'a0> -> JoinList<'a0>

Full name: Script.JoinList`1.op_Cons