フィボナッチ数列
これももう、やりつくされているであろう例題。数式に近い形で関数定義ができました。
fibonacci 1 = 1 fibonacci 2 = 1 fibonacci n = fibonacci (n - 1) + fibonacci (n - 2) main = print $ map fibonacci [1..30]
確かにこれでも計算はできますが、30だとやっと耐えられる程度の処理時間です。40にすると、数分かかってしまいます。それ以降も、求められた値に比例した実行時間を浪費してしまいます。詳しくは分かりませんが、単純に値の回数分の再帰が発生しているからでしょうか。
そこで、公式を使った方法で書き直してみました(参考:フィボナッチ数 - Wikipedia)。
root5 = sqrt 5 :: Float goldenRatio = ( 1 + root5 ) / 2 :: Float fibonacci n = floor $ goldenRatio ^ n / root5 + 0.5 main = print $ map fibonacci [1..100]
この場合だと、100にしても一瞬で計算が終わります。(200だと、直前でIntがオーバーフローします。)