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 :> IEnumerable<'a>
            yield! y :> IEnumerable<'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 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 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

Full name: Script.JoinList.head

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

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/6I
Posted:	13 years ago
Author:	Ryan Riley
Tags:	sequences , collections , lists