5 people like it.

Y(n) Polyvariadic fixpoint

Encoding mutually-recursive functions with a Polyvariadic fixpoint combinator.

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

let rec Y f x = f (Y f) x
let curry f a b = f (a, b)  

let rec Y2 f1 f2 =
    let f1' = Y (fun f1' -> (curry f1) f1' (Y (fun f2' -> (curry f2) f1' f2')))
    let f2' = Y (fun f2' -> (curry f2) (Y (fun f1' -> (curry f1) f1' f2')) f2')
    f1', f2'

// Example
let even, odd = 
    Y2 (fun (even, odd) x ->
           x = 0 || odd (x-1))
       (fun (even, odd) x ->
           x <> 0 && even (x-1))

even 42 // true 
odd 42 // false
val Y : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.Y
val f : (('a -> 'b) -> 'a -> 'b)
val x : 'a
val curry : f:('a * 'b -> 'c) -> a:'a -> b:'b -> 'c

Full name: Script.curry
val f : ('a * 'b -> 'c)
val a : 'a
val b : 'b
val Y2 : f1:(('a -> 'b) * ('c -> 'd) -> 'a -> 'b) -> f2:(('a -> 'b) * ('c -> 'd) -> 'c -> 'd) -> ('a -> 'b) * ('c -> 'd)

Full name: Script.Y2
val f1 : (('a -> 'b) * ('c -> 'd) -> 'a -> 'b)
val f2 : (('a -> 'b) * ('c -> 'd) -> 'c -> 'd)
val f1' : ('a -> 'b)
val f2' : ('c -> 'd)
val even : (int -> bool)

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

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

More information

Link:http://fssnip.net/cT
Posted:12 years ago
Author:Nick Palladinos
Tags: fixpoint , recursion

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.