終わりのない表から必要な分だけ
遅延評価とは、値が本当に必要になるまで、計算を先送りする仕組みです。そのため Haskell では、終わりのない無限リストを書いても、必要な分だけを取り出して使えます。
電車の時刻表で、「毎日あとに続く発車時刻の全部」を式で書いておき、次の3本だけを見る場面を考えます。全部を先に作らず、見る分だけ作るので、無限でも困りません。
このレッスンのゴール
メモ
再帰の関数を書き、無限リストが使える理由を説明することができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| 再帰 | 関数が自分自身を呼ぶこと | |
| 基底 | 再帰を止める、最も単純な場合 | |
| 遅延評価 | 値が必要になるまで計算しないこと | |
| 無限リスト | 終わりのないリスト | [1 ..] |
| take | リストの先頭から指定の個数だけ取る関数 | take 3 [1 ..] |
学生が入力するセルは、このプレビューでは空白です。
再帰は基底と自己呼び出しでできる
Haskell には for 文がありません。繰り返しは、再帰と、第5回の map や fold で書きます。
再帰の関数は、2つの部分でできています。止まる場合を答える基底と、少し小さくした問題を自分に任せる部分です。リストなら、空のリストが基底です。
例: リストの長さを数える
-- 例です。count は、リストの要素の数を返します。
count :: [Int] -> Int
-- 基底: 空のリストの要素は 0 個です。
count [] = 0
-- 再帰: 先頭の 1 個と、残りの個数を足します。
count (_ : rest) = 1 + count rest例: count [5, 6, 7] の計算
| 手順 | 式 | わかること |
|---|---|---|
| 1 | count [5, 6, 7] | 1 + count [6, 7] になる |
| 2 | 1 + count [6, 7] | 1 + (1 + count [7]) になる |
| 3 | 1 + (1 + (1 + count [])) | 基底で count [] は 0 |
| 4 | 1 + (1 + (1 + 0)) | 答えは 3 |
学生が入力するセルは、このプレビューでは空白です。
再帰の関数を呼ぶ
docker exec haskell ghc -e 'let count :: [Int] -> Int; count [] = 0; count (_ : rest) = 1 + count rest in count [5, 6, 7]'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
階乗を再帰で求める
docker exec haskell ghc -e 'let fact :: Int -> Int; fact 0 = 1; fact n = n * fact (n - 1) in fact 5'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
遅延評価は必要になるまで計算しない
遅延評価では、式は、結果が必要になったときに初めて計算されます。使われない部分は、計算されません。
undefined は、計算すると必ずエラーになる値です。でも、使われなければ何も起きません。下の2つの式は、undefined を含んでも、エラーなしで答えを出します。
使わない部分は計算されない
docker exec haskell ghc -e 'fst (3, undefined)'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
引数を使わない関数の場合
docker exec haskell ghc -e 'const 1 undefined'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
無限リストは必要な分だけ使える
[1 ..] は、1から先へ終わりなく続く無限リストです。遅延評価なので、先頭の数個を取るだけなら、その分しか作られません。
take 5 [1 ..] は、先頭の5個を返します。takeWhile (< 40) は、条件に合う間だけ取り続けます。
無限リストの先頭を取る
docker exec haskell ghc -e 'take 5 [1 ..]'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
40より小さい平方数だけ取る
docker exec haskell ghc -e 'takeWhile (< 40) (map (^2) [1 ..])'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
100より大きい最初の3の倍数
docker exec haskell ghc -e 'take 1 (filter (> 100) (map (*3) [1 ..]))'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
自分自身で作るフィボナッチ数
docker exec haskell ghc -e 'let fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs) in take 10 fibs'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
「無限リストを書くと、メモリが尽きる」と考える人が多くいます。使った分しか作られないので、take などで有限にすれば安全です。ただし、length や sum で無限リストの全体を求める式は、終わりません。
Python のジェネレータで遅延を見る
# yield は、値を1つ出して止まります。次に頼まれるまで動きません。
def naturals():
n = 0
while True:
yield n
n = n + 1
stream = naturals()
print(next(stream), next(stream), next(stream))
# print の中の next を 1 つ増やして、続きの値が出ることを確かめましょう。