3 people like it.

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