1 people like it.

Hughes's FuncList

A FuncList is a "list-like" datatype with constant time append (represented as a function of cons-lists). The implementation is based on a convenient computation builder.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
// for more info http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf

type FuncList<'a> = 'a list -> 'a list

type FuncListBuilder() =
    member self.Combine (first : FuncList<'a>, second : FuncList<'a>) : FuncList<'a>  = (first << second) 
    member self.Zero() : FuncList<'a> = id
    member self.Yield (value : 'a) : FuncList<'a> = fun tail -> value :: tail
    member self.YieldFrom (value : FuncList<'a>) : FuncList<'a> = value
    member self.Delay ( f : unit -> FuncList<'a>) : FuncList<'a> = (fun tail -> f () tail)
 
let funcList = new FuncListBuilder()


// example
let rec reverse list =
    match list with
    | [] -> funcList.Zero()
    | x :: xs -> funcList { yield! reverse xs; yield x }

reverse [1..10] [] // returns [10; 9; 8; 7; 6; 5; 4; 3; 2; 1]
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
type FuncListBuilder =
  new : unit -> FuncListBuilder
  member Combine : first:FuncList<'a> * second:FuncList<'a> -> FuncList<'a>
  member Delay : f:(unit -> FuncList<'a>) -> FuncList<'a>
  member Yield : value:'a -> FuncList<'a>
  member YieldFrom : value:FuncList<'a> -> FuncList<'a>
  member Zero : unit -> FuncList<'a>

Full name: Script.FuncListBuilder

--------------------
new : unit -> FuncListBuilder
val self : FuncListBuilder
member FuncListBuilder.Combine : first:FuncList<'a> * second:FuncList<'a> -> FuncList<'a>

Full name: Script.FuncListBuilder.Combine
val first : FuncList<'a>
type FuncList<'a> = 'a list -> 'a list

Full name: Script.FuncList<_>
val second : FuncList<'a>
member FuncListBuilder.Zero : unit -> FuncList<'a>

Full name: Script.FuncListBuilder.Zero
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id
member FuncListBuilder.Yield : value:'a -> FuncList<'a>

Full name: Script.FuncListBuilder.Yield
val value : 'a
val tail : 'a list
member FuncListBuilder.YieldFrom : value:FuncList<'a> -> FuncList<'a>

Full name: Script.FuncListBuilder.YieldFrom
val value : FuncList<'a>
member FuncListBuilder.Delay : f:(unit -> FuncList<'a>) -> FuncList<'a>

Full name: Script.FuncListBuilder.Delay
val f : (unit -> FuncList<'a>)
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
val funcList : FuncListBuilder

Full name: Script.funcList
val reverse : list:'a list -> FuncList<'a>

Full name: Script.reverse
Multiple items
val list : 'a list

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

Full name: Microsoft.FSharp.Collections.list<_>
member FuncListBuilder.Zero : unit -> FuncList<'a>
val x : 'a
val xs : 'a list
Next Version Raw view Test code New version

More information

Link:http://fssnip.net/5i
Posted:12 years ago
Author:Nick Palladinos
Tags: list , hughes