Polyvariadic fixpoint

Polyvariadic fixpoint combinator in F# (heavily inspired by Haskell)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18:

// http://okmij.org/ftp/Computation/fixed-point-combinators.html

let force (value : Lazy<_>) = value.Force()
let fix f = let rec x = lazy (f x) in x

let fix' (fs : list<Lazy<list<'a -> 'b>> -> 'a -> 'b>) : Lazy<list<'a -> 'b>> = 
    fix (fun r -> fs |> List.map (fun f -> f r)) 

let fe l x = 
    let [e; o] = force l
    x = 0 || o (x-1)
let fo l x = 
    let [e; o] = force l
    x <> 0 && e (x-1)
let l = fix' [fe; fo]
let [e; o] = force l
e 42 // true
o 42 // false

val force : value:Lazy<'a> -> 'a

Full name: Script.force

val value : Lazy<'a>

Multiple items
active recognizer Lazy: Lazy<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.( |Lazy| )

--------------------
type Lazy<'T> = System.Lazy<'T>

Full name: Microsoft.FSharp.Control.Lazy<_>

member System.Lazy.Force : unit -> 'T

val fix : f:(Lazy<'a> -> 'a) -> Lazy<'a>

Full name: Script.fix

val f : (Lazy<'a> -> 'a)

val x : Lazy<'a>

val fix' : fs:(Lazy<('a -> 'b) list> -> 'a -> 'b) list -> Lazy<('a -> 'b) list>

Full name: Script.fix'

val fs : (Lazy<('a -> 'b) list> -> 'a -> 'b) list

type 'T list = List<'T>

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

val r : Lazy<('a -> 'b) list>

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

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

val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map

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

val fe : l:Lazy<(int -> bool) list> -> x:int -> bool

Full name: Script.fe

val l : Lazy<(int -> bool) list>

val x : int

val e : (int -> bool)

val o : (int -> bool)

val fo : l:Lazy<(int -> bool) list> -> x:int -> bool

Full name: Script.fo

val l : Lazy<(int -> bool) list>

Full name: Script.l

val e : (int -> bool)

Full name: Script.e

val o : (int -> bool)

Full name: Script.o

Raw view Test code New version

More information

Link:	http://fssnip.net/9v
Posted:	13 years ago
Author:	Nick Palladinos
Tags:	fixedpoint , haskell , laziness