2013/07/16

zipWithフィボナッチ関数は正格評価でも書ける

fibs = 0:1:zipWith (+) fibs (tail fibs)
Haskellでフィボナッチ数列を返す関数の一例.2番めを取りに行くとfibsの0番目と1番目を足したものが返り,3番目を取りに行くとfibsの1番目と2番目を足したものが返るというややキモい流れで,これをもって遅延評価怖いとする声があるが,実はこれは正格評価でも問題なく動く.

正格評価で結果を得るには基底部を用意して有限列で止める必要があるため,fibs関数の引数でカウントダウンするようにする.(fibs(n)=フィボナッチ数列のn番目という意味ではないので注意)

function fibs(n){
    return n<=0 ? [] : [0,1].concat(zipWithPlus(fibs(n-1), fibs(n-1).slice(1)));
}

function zipWithPlus(arr1, arr2){
    return arr1.map(function(e, n){return e+arr2[n]}).slice(0,arr2.length);
}

nが0になったら空配列を返す以外はHaskellの場合と変わっていない.

なお,Wikipediaにはこのfibsの定義を「共再帰の例」と書いてあるが,corecursionの訳としては余再帰が正しい.(coに対するcontraが存在すれば「共〜」と「反〜」という訳が当てはまる.)余再帰とは圏論でいう再帰の双対概念である.圏論勉強会 at ワークスアプリケーションズで聞きかじったところによると,F始代数にあたるデータ型を帰納的データ型(inductive data type),F終余代数にあたるデータ型を余帰納的データ型(coinductive data type)と呼び,前者が有限,後者が無限のデータ型を扱えるらしい.Wikipediaではcorecursionの実例としてこのfibsを与えているが,要は無限データ列を返す再帰関数なら全部corecursionなのだろう.