フィボナッチ数列(つづき)

id:nobsun さんからコメントをもらった。ありがとうございます。

fib n = fibIter 1 1 n
  where fibIter a b 0 = a
    fibIter a b n = fibIter b (a+b) (n-1)

(※ちょっと変えました)

*Main> map fib [1..10]
[1,2,3,5,8,13,21,34,55,89]

id:nobsun さんはこれ(↑)が id:pyletさんとこのループ版と同等だというのだけど,むしろ反復版(↓これ)と同等じゃないのかなぁ。

def fib3_iter(a, b, i, n):
    if i == n:
        return a
    else:
        return fib3_iter(b, a + b, i + 1, n)

def fib3(n):
    return fib3_iter(1, 1, 0, n)

このPythonの関数(メソッド?)はカウンタに変数 i を使っているけど,重要なのは n と i の差 n-i なんだから n-i -> n に置き換えて n 自身をカウンタに使えば i をなくせる。内側のfib3_iterの引数は n-(i+1) = (n-i)-1 -> n-1 と置き換えられるから

def fib3_iter(a, b, n):
    if n == 0:
        return a
    else:
        return fib3_iter(b, a + b, n - 1)

def fib3(n):
    return fib3_iter(1, 1, n)

これならまさしく上のHaskellと同じだ。

あー,でも,そうか。既知の第0項と第1項をもとにして第n項まで頭から順に計算していく,という点ではどっちも同等だといえるのか。
いや,まて。再帰してる反復版ではスタックを積まなきゃいけないけどループ版ではいらないはずだな。
いやいや,遅延評価するからいらないのか?……違うか?
だめだ。わかんなくなった。

カテゴリー: Haskell パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください