Hughes's CPSFuncList

A CPS version of FuncList, in order to avoid blowing the stack.

 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:

// Continuation of http://fssnip.net/5i

type FuncList<'a> = 'a list -> 'a list
type CPSFuncList<'a> = FuncList<'a> -> FuncList<'a>
// Monoid comprehension
type CPSFuncListBuilder() =
    member self.Combine (first : CPSFuncList<'a>, second : CPSFuncList<'a>) : CPSFuncList<'a>  = 
        (fun k -> second (fun tail -> first (fun tail' -> k tail') tail))
    member self.Zero() : CPSFuncList<'a> = (fun k tail -> k tail)
    member self.Yield (value : 'a) : CPSFuncList<'a> = (fun k tail -> k (value :: tail))
    member self.YieldFrom (value : CPSFuncList<'a>) : CPSFuncList<'a> = value
    member self.Delay ( f : unit -> CPSFuncList<'a>) : CPSFuncList<'a> = (fun k tail -> f () k tail)
 
let cpsFuncList = new CPSFuncListBuilder()


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

let rec map f list =
    match list with
    | [] -> cpsFuncList.Zero()
    | x :: xs -> cpsFuncList { yield f x; yield! map f xs }

reverse [1..1000000] id []
map ((+) 1) [1..1000000] id []

type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>

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

Full name: Script.CPSFuncList<_>

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

Full name: Script.FuncList<_>

Multiple items
type CPSFuncListBuilder =
  new : unit -> CPSFuncListBuilder
  member Combine : first:CPSFuncList<'a> * second:CPSFuncList<'a> -> CPSFuncList<'a>
  member Delay : f:(unit -> CPSFuncList<'a>) -> CPSFuncList<'a>
  member Yield : value:'a -> CPSFuncList<'a>
  member YieldFrom : value:CPSFuncList<'a> -> CPSFuncList<'a>
  member Zero : unit -> CPSFuncList<'a>

Full name: Script.CPSFuncListBuilder

--------------------
new : unit -> CPSFuncListBuilder

val self : CPSFuncListBuilder

member CPSFuncListBuilder.Combine : first:CPSFuncList<'a> * second:CPSFuncList<'a> -> CPSFuncList<'a>

Full name: Script.CPSFuncListBuilder.Combine

val first : CPSFuncList<'a>

val second : CPSFuncList<'a>

val k : FuncList<'a>

val tail : 'a list

val tail' : 'a list

member CPSFuncListBuilder.Zero : unit -> CPSFuncList<'a>

Full name: Script.CPSFuncListBuilder.Zero

member CPSFuncListBuilder.Yield : value:'a -> CPSFuncList<'a>

Full name: Script.CPSFuncListBuilder.Yield

val value : 'a

member CPSFuncListBuilder.YieldFrom : value:CPSFuncList<'a> -> CPSFuncList<'a>

Full name: Script.CPSFuncListBuilder.YieldFrom

val value : CPSFuncList<'a>

member CPSFuncListBuilder.Delay : f:(unit -> CPSFuncList<'a>) -> CPSFuncList<'a>

Full name: Script.CPSFuncListBuilder.Delay

val f : (unit -> CPSFuncList<'a>)

type unit = Unit

Full name: Microsoft.FSharp.Core.unit

val cpsFuncList : CPSFuncListBuilder

Full name: Script.cpsFuncList

val reverse : list:'a list -> CPSFuncList<'a>

Full name: Script.reverse

Multiple items
val list : 'a list

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

Full name: Microsoft.FSharp.Collections.list<_>

member CPSFuncListBuilder.Zero : unit -> CPSFuncList<'a>

val x : 'a

val xs : 'a list

val map : f:('a -> 'b) -> list:'a list -> CPSFuncList<'b>

Full name: Script.map

val f : ('a -> 'b)

val id : x:'T -> 'T

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

Raw view Test code New version

More information

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