Haskellのseqについて

Haskellの計算は遅延評価なので,気軽にループを書くとスペースリークに悩まされることがある. 人はseqを使えというが, 初心者からするとその挙動が結構トリッキーで何度も苦しめられた.

ので,整理してみる.

小手調べ

まずは評価戦略の整理から.:sprintコマンドで評価済みの値を表示できる.

何もしなければ一切評価されない.

GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> x = [1, 2, 3] :: [Int]
Prelude> :sprint x
x = _

必要な部分だけが評価されていく. 今回はGHCiの画面表示で評価をコントロールする.

Prelude> last x
3
Prelude> :sprint x
x = [_,_,3]

ちょっとしたトラップ.各要素は前の要素+1で生成されるので,最後を評価する過程で途中も評価されている.

Prelude> x = [1 .. 10] :: [Int]
Prelude> last x
10
Prelude> :sprint x
x = [1,2,3,4,5,6,7,8,9,10]

seq関数

seq a bは値としてはbを返すが,評価戦略としてaの評価をbの評価の前に挟むことができる.

Prelude> x = 1 :: Int
Prelude> seq x ()
()
Prelude> :sprint x
x = 1 -- 直接表示せずともseq越しにxが評価される

「前に挟む」というのがポイントで,seq a b自体が評価されなければaは(ましてやbも)評価されない.seq a bをコード上に書くだけではaを評価できないことに注意しよう*1

Prelude> x = 1 :: Int
Prelude> _ = seq x () -- 代入するだけで評価はしないでおく
Prelude> :sprint x
x = _ --- 評価されていない

二つ目の注意点.seqの評価は浅い. 代数的データ型のインスタンスはコンストラクタまでしか評価されない*2

Prelude> x = [1, 2, 3] :: [Int]
Prelude> seq x ()
()
Prelude> :sprint x
x = _ : _ -- Listの場合は`(_:_)`か`[]`なのかが判明する

深く評価するには

深く評価する際にはdeepseqというライブラリ(関数名でもある)を使うと良さそう.

Prelude Control.DeepSeq> x = [1, 2, 3] :: [Int]
Prelude Control.DeepSeq> deepseq x ()
()
Prelude Control.DeepSeq> :sprint x
x = [1,2,3]

役に立つかはわからないが,深めのseqを自分で書くこともできる.

eval :: [a] -> ()
eval [] = ()
eval (x:xs) = x `seq` eval xs

この場合,evalの返り値を評価すれば、引数のリストを深さ1まで評価できる.

Prelude> x = [[1, 2], [3, 4], [5, 6]] :: [[Int]]
Prelude> eval x
()
Prelude> :sprint x
x = [(_ : _),(_ : _),(_ : _)]  -- 途中まで評価されている

以上.

*1:ただの関数にはそんなことはできない(と思う).マクロの範疇である.

*2:より一般にはweak head normal form (WHNF)まで評価される,らしいが意味はよくわかっていない.