関数型のループ

2015年 5月 5日 関数型プログラミング Kotlin Swift Ruby

関数型プログラミングのスタイルを導入すべくScala関数型デザイン&プログラミングという本で関数型プログラミングについて勉強しています。
練習問題がいくつか出てくるのですが、Scalaは使う機会がないので、最近よく使うSwift、Kotlin、Rubyだとどんなかんじになるのかやってみようと思います。
Scalaでの回答はGitHubにあります。



とりあえず最初の課題。

課題2.1 n番目のフィボナッチ数を取得する再帰関数を記述せよ。

Scalaでの回答

scala
def fib(n: Int): Int = {
  @annotation.tailrec
  def loop(n: Int, prev: Int, cur: Int): Int =
    if (n == 0) prev
    else loop(n - 1, cur, prev + cur)
  loop(n, 0, 1)
}

Kotlin

KotlinはScalaと同じく三項演算子が使えません。
あと、Scalaと同じく、末尾再帰最適化がされないパターンだとコンパイラがエラーにしてくれるtailRecursiveというアノテーションがあるんですが、ローカル関数では使えないようです。

kotlin
fun fib(n: Int): Int {
    fun loop(n: Int, prev: Int, cur: Int): Int {
        return if (n == 0) prev else loop(n -1, cur, prev + cur)
    }
    return loop(n, 0, 1)
}

Swift

swift
func fib(n: Int) -> Int {
    func loop(n: Int, prev: Int, cur: Int) -> Int {
        return n == 0 ? prev : loop(n - 1, cur, prev + cur)
    }
    return loop(n, 0, 1)
}

これだとLocal functions cannot reference themselvesのエラーになりました。
Swiftはローカル関数で再帰ができないようです。
仕方ないのでloop関数を外に出しました。

swift
func loop(n: Int, prev: Int, cur: Int) -> Int {
    return n == 0 ? prev : loop(n - 1, cur, prev + cur)
}
 
func fib(n: Int) -> Int {
    return loop(n, 0, 1)
}

Ruby

Rubyは末尾再帰が最適化されませんでした。
ここを読むと

ruby
RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

を書けばいけるみたいですが、できませんでした。
10000でstack level too deepのエラーになりました。

ruby
def fib(n)
  def loop(n, prev, cur)
    n == 0 ? prev : loop(n - 1, cur, prev + cur)
  end
  loop(n, 0, 1)
end


前へ 次へ