3 people like it.

A polyvariadic fixpoint in F#

Or who needs non-strict semantics when you have references?

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
let Y (Fs : (('a -> 'b) list -> 'a -> 'b) list) : ('a -> 'b) list =
    let refs = [ for _ in Fs -> ref Unchecked.defaultof<'a -> 'b> ]
    let etaExpanded = refs |> List.map (fun fp -> (fun x -> fp.Value x))
    
    Fs 
    |> List.map (fun F -> F etaExpanded)
    |> List.zip refs
    |> List.iter (fun (fp, f) -> fp := f)

    etaExpanded

// example
#nowarn "25"

let [even; odd] =
    let even = fun [even; odd] n -> n = 0 || odd (n-1)
    let odd =  fun [even; odd] n -> n <> 0 && even (n-1)
    Y [even; odd]


odd 2013
val Y : Fs:(('a -> 'b) list -> 'a -> 'b) list -> ('a -> 'b) list

Full name: Script.Y
val Fs : (('a -> 'b) list -> 'a -> 'b) list
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val refs : ('a -> 'b) ref list
Multiple items
val ref : value:'T -> 'T ref

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

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
module Unchecked

from Microsoft.FSharp.Core.Operators
val defaultof<'T> : 'T

Full name: Microsoft.FSharp.Core.Operators.Unchecked.defaultof
val etaExpanded : ('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 fp : ('a -> 'b) ref
val x : 'a
property Ref.Value: 'a -> 'b
val F : (('a -> 'b) list -> 'a -> 'b)
val zip : list1:'T1 list -> list2:'T2 list -> ('T1 * 'T2) list

Full name: Microsoft.FSharp.Collections.List.zip
val iter : action:('T -> unit) -> list:'T list -> unit

Full name: Microsoft.FSharp.Collections.List.iter
val f : ('a -> 'b)
val even : (int -> bool)

Full name: Script.even
val odd : (int -> bool)

Full name: Script.odd
val even : ((int -> bool) list -> int -> bool)
val even : (int -> bool)
val odd : (int -> bool)
val n : int
val odd : ((int -> bool) list -> int -> bool)
Raw view Test code New version

More information

Link:http://fssnip.net/gQ
Posted:11 years ago
Author:Eirik Tsarpalis
Tags: y combinator , polyvariadic fixpoint