[Haskell途中下車の旅] until で手続き型のループ文気分を

Haskell のサンプルコードを見て「なるほど」とわかった気になってもいざ自分で一から書くとなるとなかなか書けないものです。典型的なのは「手続き型ならループ文で簡単に書けるのに・・・」でしょう。

フィボナッチ数の値を求める問題を例にしてみましょう。
rubyでループを使って書いてみます。

def fib(n)
  a,b,i = 1,1,n         # (A) 初期化
  until (i == 0)        # (B) 終了条件
    a,b,i = b,a+b,i-1   # (C) ループ本体
  end
  return a
end

さてループ構文もなく変数の再代入も許されない Haskell ではどう書けばよいのでしょう。
ループで変数への再代入を避ける一番単純な方法はループを再帰関数で書いて再代入する変数すべてを関数で 持ち回ることです。
各変数を別々の引数にして持ち回ってもいいのですがいっぱいあると混乱するので引数を一つにまとめてしまいましょう。
Haskell で複数の値を一かたまりにするもっとも簡単な方法は tuple です。再代入する変数の a と b と i を (a,b,i) という tuple にまとめてやってみます。

fib n = loop (1,1,n)
loop (a,b,0) = a
loop (a,b,i) = loop (b,a+b,i-1)

このコードで立派に動きますがこれで終わりだとつまらないですね。
今回は手続き型のループの気分で使える高階関数 until を紹介しましょう。
until p f z は rubyコードでいうところの

x = z
until (p(x))
  x = f(x)
end
return x

と同様の計算を行ないます。
z が初期値、p がループ終了判定関数、f がループ本体にあたります。
この until を使うと fib は次のように書けます。

fib n = a2
  where
    (a2,b2,i2) = until (\(a,b,i) -> i == 0) (\(a,b,i) -> (b,a+b,i-1)) (1,1,n)

rubyコードの
(A) の a,b,i = 1,1,n が
until 第３引数の (1,1,n) に、
(B) の (i == 0) が
until 第１引数の (\(a,b,i) -> i == 0) に、
(C) の a,b,i = b,a+b,i-1 が
until 第２引数の (\(a,b,i) -> (b,a+b,i-1)) に

それぞれ対応しています。

でも上記のコードは Haskellらしくないですね。やはりフィボナッチ数列といえば

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

が一番の絶景でしょう。

次回は fold系高階関数の効能について取り上げます。