Haskellの技法:無限リストのトリック

文:Nick Gibson(Builder AU)  翻訳校正:原井彰弘
2007-12-13 07:15:00
  • このエントリーをはてなブックマークに追加
triangle1 = scanl (+) 1 [2..]
triangle2 = 1 : [x+y | x <- [2..] | y <- triangle2]

factorial1 = scanl (*) 1 [2..]
factorial2 = 1 : [x*y | x <- [2..] | y <- factorial2]

$ ghci -flglasgow-exts
*Main> (take 1000 triangle1) == (take 1000 triangle2)
True
*Main> (take 1000 factorial1) == (take 1000 factorial2)
True
*Main> take 10 triangle1
[1,3,6,10,15,21,28,36,45,55]
*Main> take 10 factorial2
[1,2,6,24,120,720,5040,40320,362880,3628800]

さて、無限リストを説明する際には、フィボナッチ数列も例としてよく用いられる。実際、WikipediaのHaskellのページでは、フィボナッチ数列を無限リストで定義するために、2種類の方法が記述されている。次に、scanl関数を用いたもう一つの方法を紹介しよう。

fibs1 = 0 : 1 : zipWith (+) fibs1 (tail fibs1)
fibs2 = 0 : 1 : [ a+b | a <- fibs2 | b <- tail fibs2 ]

fibs3 = 0 : scanl (+) 1 fibs3

$ ghci -fglasgow-exts
*Main> (take 1000 fibs1) == (take 1000 fibs2)
True
*Main> (take 1000 fibs2) == (take 1000 fibs3)
True
*Main> take 10 fibs3
[0,1,1,2,3,5,8,13,21,34]

無限リストは整数値以外でも使用することが可能である。次の例では、指定した文字数未満の全ての文字列を生成するために無限リストが用いられている。

strings = [x++[a] | x <- "" : strings, a <- ['a'..'z']]

stringsLessThan n = takeWhile (\x -> length x < 5) strings

$ ghci
*Main> length (stringsLessThan 3)
702

全ての状況で無限リストが役立つわけではないが、無限リストを用いることによってコードがよりシンプルかつ簡潔になる場合もあるだろう。簡単なプロファイリングによって、反復的なプログラムとリストを用いたプログラムは同等のパフォーマンスで動作することが確認されている。つまり、遅延評価の仕組みを利用することによるペナルティはないのである。

もし、Haskellの遅延リストについてより深く知りたければ、Haskell Wikiを読むのがベストだろう。特に「infinite list of prime numbers」は、このテクニックが用いられているよい例である。

このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]