Y combinator: Difference between revisions
m
→{{header|F Sharp|F#}}
m (→ALGOL 68) |
|||
(7 intermediate revisions by 4 users not shown) | |||
Line 988:
test("fac")
test("fib")</syntaxhighlight>
=={{header|Binary Lambda Calculus}}==
This BLC program outputs 6!, as computed with the Y combinator, in unary (generated from https://github.com/tromp/AIT/blob/master/rosetta/facY.lam) :
<pre>11 c2 a3 40 b0 bf 65 ee 05 7c 0c ef 18 89 70 39 d0 39 ce 81 6e c0 3c e8 31</pre>
=={{header|BlitzMax}}==
Line 1,229 ⟶ 1,234:
fib(9)=34
fib(10)=55</pre>
=={{header|Bruijn}}==
As defined in <code>std/Combinator</code>:
:import std/Number .
# sage bird combinator
y [[1 (0 0)] [1 (0 0)]]
# factorial using y
factorial y [[=?0 (+1) (0 ⋅ (1 --0))]]
:test ((factorial (+6)) =? (+720)) ([[1]])
# (very slow) fibonacci using y
fibonacci y [[0 <? (+1) (+0) (0 <? (+2) (+1) rec)]]
rec (1 --0) + (1 --(--0))
:test ((fibonacci (+6)) =? (+8)) ([[1]])
=={{header|C}}==
Line 2,874 ⟶ 2,899:
=={{header|F Sharp|F#}}==
===March 2024===
In spite of everything that follows I am going to go with this.
// Y combinator. Nigel Galloway: March 5th., 2024
type Y<'T> = { eval: Y<'T> -> ('T -> 'T) }
let Y n g=let l = { eval = fun l -> fun x -> (n (l.eval l)) x } in (l.eval l) g
let fibonacci=function 0->1 |x->let fibonacci f= function 0->0 |1->1 |x->f(x - 1) + f(x - 2) in Y fibonacci x
let factorial n=let factorial f=function 0->1 |x->x*f(x-1) in Y factorial n
printfn "fibonacci 10=%d\nfactorial 5=%d" (fibonacci 10) (factorial 5)
</syntaxhighlight>
{{output}}
<pre>
fibonacci 10=55
factorial 5=120
</pre>
===Pre March 2024===
<syntaxhighlight lang="fsharp">type 'a mu = Roll of ('a mu -> 'a) // ' fixes ease syntax colouring confusion with
Line 4,882 ⟶ 4,923:
=={{header|R}}==
<syntaxhighlight lang="r">
#' Y = λf.(λs.ss)(λx.f(xx))
#' Z = λf.(λs.ss)(λx.f(λz.(xx)z))
▲}</syntaxhighlight>
#'
fixp.Y <- \ (f) (\ (x) (x) (x)) (\ (y) (f) ((y) (y))) # y-combinator
▲<syntaxhighlight lang="r">fac <- function(f) {
fixp.Z <- \ (f) (\ (x) (x) (x)) (\ (y) (f) (\ (...) (y) (y) (...))) # z-combinator
</syntaxhighlight>
Y-combinator test:
fac.y <- fixp.Y (\ (f) \ (n) if (n<2) 1 else n*f(n-1))
fac.y(9) # [1] 362880
fib.y <- fixp.Y (\ (f) \ (n) if (n <= 1) n else f(n-1) + f(n-2))
fib.y(9) # [1] 34
▲}</syntaxhighlight>
</syntaxhighlight>
Z-combinator test:
<syntaxhighlight lang="r">
fac.z <- fixp.Z (\ (f) \ (n) if (n<2) 1 else n*f(n-1))
fac.z(9) # [1] 362880
fib.z <- fixp.Z (\ (f) \ (n) if (n <= 1) n else f(n-1) + f(n-2))
fib.z(9) # [1] 34
</syntaxhighlight>
You can verify these codes by [https://shinylive.io/r/editor/#code=NobwRAdghgtgpmAXGAZgSwB5wCYAcD2aEALgHQBOYANGAMb4lwlJgDEA5AAQCanAvJ0DdwClIAKQQGdSEiQEpxGUilEYMs2QB0IHTgC1+QkeKkz5gxcsEAvMatlX1WnVq3oMuUrwA8AWk4aNTlEUWSCAoLUI0JV1MMDRAE9okKDE6KTY1k4En3oYACMiKGJ8cldMD31ff3iU0XCYqKjohqSguobSLvSeoK7SdVCsq1z8AqKSsognLgBXCTgXCBQoWlIEzmq3D1562tCGiFC0FCCILwAmUIBGTjgAGwXOCAAqZQgfa8dl1fXRAE4hpxgNcALqcADMADYLgAOWEABiW6Hy602fm2nji7QO8SOnBOZ02Ai+zzujzgnHen1CAGoqaIPldNMs0KiEgCgSDwRCACxLVy-KzoqkVUj6PY4mpnY6nRmXG7kp6valfFkrNZWTmcLLcyEw+FI6as1HCrZiiUNFKHWVErwk0IQJWU1V0hlM74o0hawE64FgyH8iBgAC+oKAA here]
▲<syntaxhighlight lang="r">for(i in 1:9) print(Y(fac)(i))
=={{header|Racket}}==
|