遅延評価

私たちはHaskellが遅延評価を使っていることを何の疑いもなく受け入れてきましたが、実際にはどのように動作しているのでしょうか？ Haskellの遅延評価の背後にあるものは、「サンク（Thunk）」と呼ばれるものです。サンクはまだ評価されていない計算で、必要になるまで メモリに保存されます。サンクを理解するために、以下の例を見てみましょう。

f a b = if a `mod` 2 == 0 then a else b
 
res = f (1+1) (2+1) -- (1+1) と (2+1) はまだ評価されていないサンクです

上記のfの例を見てみましょう。条件がどちらに当てはまるかを判断するためにはまず、aが評価される必要があります。したがって、aが評価されます。

f 2 (2+1) = if 2 `mod` 2 == 0 then 2 else (2+1)

すると最初の条件が真であることがわかるため、(2+1)を計算せずに2を返します。これは、不要な計算を避けることができたので素晴らしいです。

遅延評価のデメリット

残念ながら、この世には銀の弾などなく、遅延評価が常に良いわけではありません。以下のfoldlの例を見てみましょう。

foldl (+) 0 [1,2,3]

上記を遅延的に計算してみましょう。

foldl (+) 0 [1,2,3]
-- = foldl (+) (0+1) [2,3]
-- = foldl (+) ((0+1)+2) [3]
-- = foldl (+) (((0+1)+2)+3) []
-- = ((0+1)+2)+3
-- = (1+2)+3
-- = 3+3
-- = 6

値を即座に足さないため、大きなサンク(((0+1)+2)+3)を積み重ねて後で評価し、結果としてより多くのステップとメモリを使用してしまいました。 配列のサイズが小さかったので実際には問題にはなりませんが、配列のサイズが大きくなると問題が発生し始めます。ここで厳格性が役立ちます。 foldl'関数は厳格な評価を強制し、ステップ数とメモリ使用量を減らします。

foldl' (+) 0 [1,2,3]
-- = foldl (+) (1) [2,3]
-- = foldl (+) (3) [3]
-- = foldl (+) (6) []
-- = 6

厳格性

foldl'やHaskellの他の厳格評価の背後には、次のように定義されたseq関数があります。

seq :: a -> b -> b
seq a b = b

一見すると、ただaを捨てる関数だけのように見えますが、この関数はコンパイラレベルで定義されており、 bを返す前にaが必ず評価されるようにプログラムしてあります。seqを使って、次のようにfoldl'を定義できます。

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' _ z [] = z
foldl' f z (x:xs) =
  let z' = f z x in
  z' `seq` foldl' f z' xs

seqを使用することで、次の再帰呼び出しに進む前にz'が厳密に評価されます。 Haskellにはseqを使用して事前定義された他の便利な関数があります。

($) :: (a -> b) -> a -> b -- 遅延
($!) :: (a -> b) -> a -> b -- 厳格!
 
f $ x = f x
f $! x = x `seq` f x

上記の$!は多くの場面で役立ちますが、特にIOアクションで役立ちます。

action = do
  --- actions
  return $! f x

$!を使用することで、潜在的に大きなサンクを返すのを防ぐことができます。

銀の弾などない

この世には万能の解決策はないことを常に覚えておいてください。foldl'のような状況では厳格性が役立つことがありますが、 アルゴリズムのパフォーマンスに悪影響を与えることもあります。実際、厳格評価を使用するとコンパイラを混乱させることがあるので、 避けられない場合を除き、厳格性を使用しないことが推奨されます。インタープリターの代わりにコンパイラーを使用している場合、 ほとんどの厳格性の問題はコンパイラーによって自動的に解決され、foldlの問題も含まれるので、それほど心配する必要はありません。

リソース

• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #26 - Strictness, Thunks & seq. YouTube.