Y combinator: Difference between revisions
→{{header|D}}: added a contribution for the Crystal language...
m (→{{header|Julia}}: Restored the Julia version of Ismaei-vc) |
GordonBGood (talk | contribs) (→{{header|D}}: added a contribution for the Crystal language...) |
||
Line 2,118:
? (mapcar #'fib '(1 2 3 4 5 6 7 8 9 10))
(1 1 2 3 5 8 13 21 34 55)</lang>
=={{header|Crystal}}==
Although Crystal is very much an OOP language, it does have "Proc"'s that can be used as lambda functions and even as closures where they capture state from the environment external to the body, and these can be used to implement the Y-Combinator. Note that many of the other static strict languages don't implement the true Y-Combinator but rather the Z-Combinator, which lacks one Beta reduction from the Y-Combinator and is more limiting in use. For strict languages such as Crystal, all that is needed to implement the true Y-Combinator is to inject some laziness by deferring execution using a "Thunk" - a function without any arguments returning a deferred value, which requires that functions can also be closures.
The following Crystal code implements the name-recursion Y-Combinator without assuming that functions are recursive (which in Crystal they actually are):
<lang crystal>require "big"
struct RecursiveFunc(T) # a generic recursive function wrapper...
getter recfnc : RecursiveFunc(T) -> T
def initialize(@recfnc) end
end
struct YCombo(T) # a struct or class needs to be used so as to be generic...
def initialize (@fnc : Proc(T) -> T) end
def fixy
g = -> (x : RecursiveFunc(T)) {
@fnc.call(-> { x.recfnc.call(x) }) }
g.call(RecursiveFunc(T).new(g))
end
end
def fac(x) # horrendouly inefficient not using tail calls...
facp = -> (fn : Proc(BigInt -> BigInt)) {
-> (n : BigInt) { n < 2 ? n : n * fn.call.call(n - 1) } }
YCombo.new(facp).fixy.call(BigInt.new(x))
end
def fib(x) # horrendouly inefficient not using tail calls...
facp = -> (fn : Proc(BigInt -> BigInt)) {
-> (n : BigInt) {
n < 3 ? n - 1 : fn.call.call(n - 2) + fn.call.call(n - 1) } }
YCombo.new(facp).fixy.call(BigInt.new(x))
end
puts fac(10)
puts fib(11) # starts from 0 not 1!</lang>
The "horrendously inefficient" massively repetitious implementations can be made much more efficient by changing the implementation for the two functions as follows:
<lang crystal>def fac(x) # the more efficient tail recursive version...
facp = -> (fn : Proc(BigInt -> (Int32 -> BigInt))) {
-> (n : BigInt) { -> (i : Int32) {
i < 2 ? n : fn.call.call(i * n).call(i - 1) } } }
YCombo.new(facp).fixy.call(BigInt.new(1)).call(x)
end
def fib(x) # the more efficient tail recursive version...
fibp = -> (fn : Proc(BigInt -> (BigInt -> (Int32 -> BigInt)))) {
-> (f : BigInt) { -> (s : BigInt) { -> (i : Int32) {
i < 2 ? f : fn.call.call(s).call(f + s).call(i - 1) } } } }
YCombo.new(fibp).fixy.call(BigInt.new).call(BigInt.new(1)).call(x)
end</lang>
Finally, since Crystal function's/"def"'s can call themselves recursively, the implementation of the Y-Combinator can be changed to use this while still being "call by name" (not value/variable recursion) as follows; this uses the identical lambda "Proc"'s internally with just the application to the Y-Combinator changed:
<lang crystal>def ycombo(f)
f.call(-> { ycombo(f) })
end
def fac(x) # the more efficient tail recursive version...
facp = -> (fn : Proc(BigInt -> (Int32 -> BigInt))) {
-> (n : BigInt) { -> (i : Int32) {
i < 2 ? n : fn.call.call(i * n).call(i - 1) } } }
ycombo(facp).call(BigInt.new(1)).call(x)
end
def fib(x) # the more efficient tail recursive version...
fibp = -> (fn : Proc(BigInt -> (BigInt -> (Int32 -> BigInt)))) {
-> (f : BigInt) { -> (s : BigInt) { -> (i : Int32) {
i < 2 ? f : fn.call.call(s).call(f + s).call(i - 1) } } } }
ycombo(fibp).call(BigInt.new).call(BigInt.new(1)).call(x)
end</lang>
All versions produce the same output:
{{out}}
<pre>3628800
55</pre>
=={{header|D}}==
| |||