Crystal中的递归程序

Question

Crystal中是否可能存在递归过程？

类似于Ruby中的lambda。

我正在尝试在Crystal中实现y-combinator，类似于Ruby中的实现：

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)
}.()

以上代码源自函数式编程冒险。

- Faustino Aguilar

---

Brian Cardiff建议您查看https://github.com/crystal-lang/crystal/issues/710#issuecomment-188261557。 - mgarciaisaia

Answer 1

据我所知，Crystal没有递归过程。但是，为了创建Y组合子，您不需要递归过程。实际上，根据definition：

在函数式编程中，可以使用Y组合子来在不支持递归的编程语言中正式定义递归函数。

这里是使用recursive types在Crystal中编写Y组合子的示例：

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

更新: 在Crystal中可以使用uninitialized关键字创建递归过程:

g = uninitialized Int32 -> Int32
g = ->(n : Int32) { n.zero? ? 1 : n * g.call(n - 1) }
g.call(5) # => 120

感谢 @mgarciaisaia 的评论。

- Vitalii Elenhaupt