Y combinator
editable example
Click the pencil to open this in an editor, change it, and run it in your browser. The same solution is posted on Rosetta Code.
The y combinator
ghul
use IO.Std.write_line
class SELF_APPLY[A, B](_f: (SELF_APPLY[A, B]) -> (A -> B)) is
apply(r: SELF_APPLY[A, B]) -> (A -> B) => _f(r)
si
y[A, B](f: (A -> B) -> (A -> B)) -> (A -> B) =>
let wrap =
SELF_APPLY[A, B](
(r: SELF_APPLY[A, B]) => (a: A) => f(r.apply(r))(a))
in wrap.apply(wrap)
let factorial =
y(recurse => n =>
if n <= 1 then 1L else cast(n) * recurse(n - 1) fi)
let fibonacci =
y(recurse => n =>
if n < 2 then n else recurse(n - 1) + recurse(n - 2) fi)
let countdown =
y(recurse => n =>
if n <= 0 then "liftoff" else "{n}, {recurse(n - 1)}" fi)
let gcd =
y(recurse => ((a, b): (int, int)) =>
if b == 0 then a else recurse((b, a % b)) fi)
for n in 0::10 do
write_line(
"factorial({n}) = {factorial(n)}, "
"fibonacci({n}) = {fibonacci(n)}")
od
write_line("countdown(5) = {countdown(5)}")
write_line("gcd(1071, 462) = {gcd((1071, 462))}")
Using rec
ghul
use IO.Std.write_line
let factorial = n rec => if n <= 1 then 1L else cast(n) * rec(n - 1) fi
let fibonacci = n rec => if n < 2 then n else rec(n - 1) + rec(n - 2) fi
let countdown =
n rec => if n <= 0 then "liftoff" else "{n}, {rec(n - 1)}" fi
let gcd =
((a, b): (int, int)) rec =>
if b == 0 then a else rec((b, a % b)) fi
for n in 0::10 do
write_line(
"factorial({n}) = {factorial(n)}, "
"fibonacci({n}) = {fibonacci(n)}")
od
write_line("countdown(5) = {countdown(5)}")
write_line("gcd(1071, 462) = {gcd((1071, 462))}")