Is recursive proc posible in Crystal?
Something like lambda in Ruby
I'm trying to do a y-combinator
in Crystal,something like Ruby one:
puts -> {
fact_improver = ->(partial) {
-> (n) { n.zero? ? 1 : n * partial.(n-1) }
}
y = ->(f) {
->(x) { f.(->(v) { x.(x).(v) }) }.(
->(x) { f.(->(v) { x.(x).(v) }) }
)
}
fact = y.(fact_improver)
fact = fact_improver.(fact)
fact.(100)
}.()
The above code was taken from Y Not- Adventures in Functional Programming
As far as I know Crystal does not have recursive procs. But to create Y combinator you don't need a recursive proc. Actually, according to the definition:
In functional programming, the Y combinator can be used to formally define recursive functions in a programming language that doesn't support recursion.
Here is an example of Y combinator written in Crystal using recursive types:
alias T = Int32
alias Func = T -> T
alias FuncFunc = Func -> Func
alias RecursiveFunction = RecursiveFunction -> Func
fact_improver = ->(partial : Func) {
->(n : T) { n.zero? ? 1 : n * partial.call(n - 1) }
}
y = ->(f : FuncFunc) {
g = ->(r : RecursiveFunction) { f.call(->(x : T) { r.call(r).call(x) }) }
g.call(g)
}
fact = y.call(fact_improver)
fact = fact_improver.call(fact)
fact.call(5) # => 120
UPDATE: it is possible to create recursive proc in Crystal with uninitialized
keyword:
g = uninitialized Int32 -> Int32
g = ->(n : Int32) { n.zero? ? 1 : n * g.call(n - 1) }
g.call(5) # => 120
Thanks to @mgarciaisaia for the comment.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With