3 people like it.

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 New version

More information

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