1 people like it.
Like the snippet!

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:	13 years ago
Author:	Nick Palladinos
Tags:	list , hughes