Rosetta Code

Y combinator: Difference between revisions

Page Discussion

Y combinator (view source)

Revision as of 12:33, 15 March 2024

2,245 bytes added ,  2 months ago
m
→‎{{header|F Sharp|F#}}
imported>HumptydumptyMe
mNo edit summary
 
(9 intermediate revisions by 6 users not shown)
Line 318:
 
 
The version below works with [[ALGOL 68 Genie]] 3.45.40 tested with Linux kernel release 6.67.94-200.fc39.x86_64.
 
N.B. 4 warnings are issued of the form
Line 339:
Y_combinator =
func_gen => ( x => x( x ) )( x => func_gen( arg => x( x )( arg ) ) )
;
#
 
PROC y combinator = ( PROC( F ) F func gen ) F:
( ( X x ) F: x( x ) )
(
(
( PROC( F ) F func gen , X x ) F:
(
func gen( PROC( F( X x , INT arg ) FINT: funcx( genx ,)( Xarg ) )( x , ) F:)
)( func gen( ( ( X x , INT arg ) INT: x( x )( arg ) )( x , ) )
)
)( func gen , )
)
;
 
 
#
fac_gen = fac => (n => ( ( n === 0 ) ? 1 : n * fac( n - 1 ) ) ) ;
#
 
PROC fac gen = ( F fac ) F:
( ( F fac , INT n ) INT: IF n = 0 THEN 1 ELSE n * fac( n - 1 ) FI )( fac , )
;
 
PROC fac gen = ( F f ) F: fac( f , ) ;
 
#
factorial = Y_combinator( fac_gen ) ;
#
 
Line 372 ⟶ 370:
#
fib_gen =
fib =>
fib => ( n => ( ( n === 0 ) ? 0 : ( n === 1 ) ? 1 : fib( n - 2 ) + fib( n - 1 ) ) )
( n => ( ( n === 0 ) ? 0 : ( n === 1 ) ? 1 : fib( n - 2 ) + fib( n - 1 ) ) )
;
#
 
PROC fib gen = ( F fib ) F:
(
( F fib , INT n ) INT: CASE n + 1 IN 0 , 1 OUT fib( n - 2 ) + fib( n - 1 ) ESAC
( F fib , INT n ) INT:
CASE n + 1 IN 0 , 1 OUT fib( n - 2 ) + fib( n - 1 ) ESAC
)( fib , )
;
 
PROC fib gen = ( F f ) F: fib( f , ) ;
 
#
fibonacci = Y_combinator( fib_gen ) ;
#
 
Line 389:
 
 
#
# for ( i = 1 ; i <= 12 ; i++) { console.log( " " + factorial( i ) ) ; } #
for ( i = 1 ; i <= 12 ; i++) { process.stdout.write( " " + factorial( i ) ) }
#
 
INT nofacs = 12 ;
printf( ( $ l , "TheHere are the first " , g( 0 ) , " factorials." , l $ , nofacs ) ) ;
FOR i TO nofacs
DO
printf( ( $ " " , g( 0 ) , l $ , factorial( i ) ) )
OD ;
print( newline ) ;
 
 
#
# for ( i = 1 ; i <= 12 ; i++) { console.log( " " + fibonacci( i ) ) ; } #
for ( i = 1 ; i <= 12 ; i++) { process.stdout.write( " " + fibonacci( i ) ) }
#
 
INT nofibs = 12 ;
printf( (
printf( ( $ l , "The first " , g( 0 ) , " fibonacci numbers." , l $ , nofibs ) ) ;
$ l , "Here are the first " , g( 0 ) , " fibonacci numbers." , l $
, nofibs
) )
;
FOR i TO nofibs
DO
printf( ( $ " " , g( 0 ) , l $ , fibonacci( i ) ) )
OD ;
print( newline )
 
END</syntaxhighlight>
Line 978 ⟶ 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,219 ⟶ 1,234:
fib(9)=34
fib(10)=55</pre>
 
=={{header|Bruijn}}==
As defined in <code>std/Combinator</code>:
<syntaxhighlight lang="bruijn">
: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]])
</syntaxhighlight>
 
=={{header|C}}==
Line 2,864 ⟶ 2,899:
 
=={{header|F Sharp|F#}}==
===March 2024===
In spite of everything that follows I am going to go with this.
<syntaxhighlight lang="fsharp">
// 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,872 ⟶ 4,923:
 
=={{header|R}}==
<syntaxhighlight lang="r">Y <- function(f) {
#' Y = λf.(λs.ss)(λx.f(xx))
(function(x) { (x)(x) })( function(y) { f( (function(a) {y(y)})(a) ) } )
#' 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
function(n) {
</syntaxhighlight>
if (n<2)
1
else
n*f(n-1)
}
}
 
Y-combinator test:
fib <- function(f) {
 
function(n) {
<syntaxhighlight lang="r">
if (n <= 1)
fac.y <- fixp.Y (\ (f) \ (n) if (n<2) 1 else n*f(n-1))
n
fac.y(9) # [1] 362880
else
 
f(n-1) + f(n-2)
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))
for(i in 1:9) print(Y(fib)(i))</syntaxhighlight>
 
=={{header|Racket}}==
Line 5,609 ⟶ 5,666:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="ecmascriptwren">var y = Fn.new { |f|
var g = Fn.new { |r| f.call { |x| r.call(r).call(x) } }
return g.call(g)
Nigel Galloway
2,172

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/349439...361948"