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