無限の長さの配列を扱うこともできる、Haskellの遅延評価とは

Haskellを勉強していて、一番最初に面白いなと思ったのは、「無限の長さの配列を扱える」ということです。
他のほとんどのプログラミング言語では、配列を定義するということは、メモリ空間を確保する、ということなので、無限の配列は扱えません。無限の容量のメモリはないですからね。
引き続き、こちらの本を読んでいます。

すごいHaskellたのしく学ぼう!

GHCiを起動

StackからHaskellの対話シェルを起動して実験してみます。

stack ghci

Stackのインストールについては、こちらのブログに書きました。
HaskellのWebフレームワークYesodでHello World
Haskell Platformをインストールして、GHCiを起動してもOKです。
Mac OS XにHaskellの開発環境を構築してHello World

無限の長さの配列を定義してみる

たとえば、1から10までのリストは、こうやって定義できます。

finiteList = [1..10]

こういうのは、他のプログラミング言語でも書けたりしますよね。
本題に入ります。無限の長さのリストの例として、自然数を列挙したリストを定義してみます。

infiniteList = [1..]

これをGHCiで実行しても何もおきません。他の言語ではこういう記法自体がありませんが、あったとしてもメモリ不足で強制終了してしまうと思います。
これを出力してみます。まずは有限の長さのリストからやってみます。

putStrLn $ show finiteList
// => [1,2,3,4,5,6,7,8,9,10]

これは普通ですね。
続いて、無限の長さのリストをやってみます。

putStrLn $ show list
// => [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...

画面にどんどん数字が溢れて、止まらなくなります。無限の要素数があるので、無限に出力し続けます。

なぜ無限のリストが定義できるのか？

なぜ無限のリストが定義できるのか、というと、Haskellが遅延評価だからです。

Haskellは怠け者です。特にそうしろと言われた場合を除いては、結果が必要になるまで関数を実行しないのです。

遅延評価なので無限リストを定義しても、それをすぐには評価しようとはしないです。
評価しないということは、メモリを確保することもしない、ということです。

遅延評価とは

無限の処理はできないので、通常は有限で打ち切れるような処理を加える必要があります。
たとえば、最初の3要素を取得する、とかです。

headOfInfiniteList = take 3 infiniteList
putStrLn $ show headOfInfiniteList
// => [1,2,3]

このheadOfInfiniteListも、putStrLnで出力する必要が出てから評価されています。
遅延評価なので、headOfInfiniteListが定義された時点では、take関数は実行されていないはずです。
その証拠に、先頭から「1京個の要素」を取り出す、という処理を書くことができます。

hugeHeadOfInfiniteList = take 10000000000000000 infiniteList

1京個の要素は、1要素1バイトとしても、10ペタバイトのメモリが必要です。僕のノートPCレベルでは、メモリに確保できないはずです。

終わりに

プログラミングを長らくやってきて、コードを書く、ということは、処理が実行される、ということでした。
Haskellでは、コードが書かれていても、実行されるとは限りません。コードの途中のある1行を、まったく評価することなく通過することもあるわけです。
処理を記述する、というより、概念を記述しているようで、不思議な感覚ですが、面白いです。