評価戦略

このページでは，Haskell における式の評価戦略について説明します．

1. 遅延評価とは

Haskell は，遅延評価（lazy evaluation）と呼ばれる評価方式を基本としています． 遅延評価は非正格評価（non-strict evaluation）の一種であり，次のような評価方式を言います．

  • 式の評価はできるだけ先延ばしにする．

  • 評価する必要のない式は評価しない．

ここで，if 式をラッピングした次のような関数 if' を考えてみます．

if' b x y = if b then x else y

式 if' (1 < 2) (3 * 4) (5 * 6) の評価は，正格と非正格で次のように異なります．

-- 正格評価
if' (1 < 2) (3 * 4) (5 * 6)
= if' True 12 30                   -- 引数をすべて評価する
= if True then 12 else 30
= 12

-- 非正格評価
if' (1 < 2) (3 * 4) (5 * 6)
= if 1 < 2 then 3 * 4 else 5 * 6   -- 引数を評価しないまま関数定義を展開
= if True then 3 * 4 else 5 * 6
= 3 * 4                            -- 5 * 6 は評価されない
= 12

Haskell で無限リストに関数を適用してもプログラムが終了することは，遅延評価によって説明できます．

take 3 [1..]
= 1 : take 2 [2..]
= 1 : 2 : take 1 [3..]
= 1 : 2 : 3 : take 0 [4..]
= 1 : 2 : 3 : []
= [1, 2, 3]

2. 正格評価の利用

Haskell で正格評価を行うには，関数 seq :: a -> b -> b を用います． 式 x `seq` y は，式 x を評価した後に式 y を評価します．

次のプログラムは，if 式をラッピングした関数 if'（非正格）と if''（正格）を定義したものです．

-- 非正格
if'  b x y = if b then x else y

-- 正格
if'' b x y = b `seq` x `seq` y `seq` if b then x else y


main = do print $ if'  True 1 (1 `div` 0)  -- 出力: 1
          print $ if'' True 1 (1 `div` 0)  -- 例外発生

また，右辺を即時評価する演算子として $! 演算子が定義されています．

($!) :: (a -> b) -> a -> b
f $! x = x `seq` f x

$! 演算子は $ 演算子のバリアントで，次のような違いがあります．

square x = x * x

-- $ 演算子を使用
square $ square $ 1 + 2
= square $ square (1 + 2)
= square (square (1 + 2))
= (square (1 + 2)) * (square (1 + 2))
= ((1 + 2) * (1 + 2)) * ((1 + 2) * (1 + 2))
= 81

-- $! 演算子を使用
square $! square $! 1 + 2
= square $! square 3
= square $! 3 * 3
= square $! 9
= 9 * 9
= 81

3. 正格性フラグ

Haskell ではデータ構造も遅延性を持つため，フィールドは必要になるまで評価されません． フィールドを正格評価するには，data 宣言において正格性フラグ ! を用います．

次のプログラムは，タプルを模した型 Tuple（非正格）と Tuple'（正格）を定義したものです．

data Tuple  a b = T  a  b   -- 非正格
data Tuple' a b = T' !a !b  -- 正格

first  (T  x y) = x
first' (T' x y) = x

main = do print $ first  $ T  'a' (1 `div` 0)  -- 出力: 'a'
          print $ first' $ T' 'a' (1 `div` 0)  -- 例外発生