正格評価と遅延評価（詳細編）

さて基本編に続き詳細編です。
動作を確認しながら細かく見ていきます。


## Debug.Trace.trace

初めに`trace`関数を導入しておきます。

```hs
import Debug.Trace (trace)

trace :: String -> a -> a
```

こんな型の関数です。`trace`が評価されると、第一引数が標準エラー出力へ出力され、第二引数が返り値として返ります。

この`trace`関数が単なる関数だということに注意してください。デバッグ用とはいえ何も魔法は使われていません。IO以外で標準エラー出力へoutputすることから、内部ではunsafeな関数が使われていますが。魔法が使われていない、というのは評価順序に関してです。つまり、<b>`trace`自体が評価されなければ標準エラー出力への出力もありません。</b>

`trace "some string" 42`を`case`で評価してみます。

```hs
k :: IO ()
k = case (trace "heyhey!" 42) of
	42 -> putStrLn "なんかの疑問の答え"
```

結果は "heyhey!" という文字列が先に現れます。

`case`によって`trace`は評価され、42がその返り値です。
何が便利かといったら、<b>変数`x`の代わりに`trace "hey" x`を用いると</b>、

* `x`が評価されたときにのみ、文字列を出力する

ということです。
しばらくこの`trace`を用いて挙動を見ていきます。

## パターンの書き方と評価

さて`case`によってWHNFにまで評価されると何度も言ってきたわけですが、正確には少し異なります。
`case`を用いた時も、<b>必要な時のみWHNFまで評価される</b>、が正しいのです。
要するにパターンによっては評価が発生しないことがあります。

先ほどのcaseでの評価で、パターンを変数パターン`x`に変更してみます。

```hs
k' :: IO ()
k' = case (trace "heyhey!" 42) of
	x -> putStrLn "なんかの疑問の答え"
```

これを実行しても文字列"heyhey!"は出力されません。サンクで変数を束縛するだけなら、評価する必要がないからです。
リテラルパターンの`0`を使ってみます。

```hs
k'' :: IO ()
k'' = case (trace "heyhey!" 42) of
	0 -> putStrLn "0は自然数"
	_ -> putStrLn "_ワイルドカードパターン_"
```

この場合`trace ...`は評価されます。サンクを潰さないと`0`かどうか確かめられないからです。
ワイルドカードパターン`_`は任意の値にマッチします。つまりその場合は変数へのマッチと同様に評価は発生しません。

言語拡張BangPatternsを用いると、パターンマッチ時にWHNFまでの評価を強制することができます。

```hs
{-# LANGUAGE BangPatterns #-}

k''' :: IO ()
k''' = case (trace "heyhey!" 42) of
	!x -> putStrLn "変数パターン+Bang-pattens"
```

この場合`!`が付いたパターンではWHNFまでの評価が発生します。つまり"heyhey!"と表示されます。便利です。
言語拡張プラグマ`{-# LANGUAGE ... #-}`はファイル冒頭に記述してください。


## Leftmost outermost

今までの説明で、 `succ $ succ $ succ $ 42 :: Int` というサンクがWHNF評価時になんやかんやで`45`になることがわかります。もう少し詳細に見てみます。この三つの`succ`はどういう順番で評価されるのでしょうか？
`succ`にそれぞれ`trace`を仕込んで評価してみます。

```hs
l :: IO ()
l = do

	let succ1 x = trace "succ1" $ succ x
        succ2 x = trace "succ2" $ succ x
        succ3 x = trace "succ3" $ succ x

	case (succ1 $ succ2 $ succ3 42) of
		!_ -> return ()
```

結果は以下です:

```hs
ghci> l
succ1
succ2
succ3
```

一番外側の`succ`から評価されることがわかります。
正格評価では、関数呼び出しがネストしていたら一番内側から評価されていました。
遅延評価では、一番外側から評価されます。

この様な評価戦略は最左最外評価戦略と呼ばれます。実際GHCが行っている評価戦略はグラフ簡約(Graph Reduction)なので、もう少しスマートで複雑ではあるのですが、メンタルモデルとしては最左最外戦略としてもあまり問題ないと思います...問題があると思う型は御指摘の上スペースリークアドベントカレンダーに書いていただければ幸いです:)


## 特殊な関数`seq`

さてみんな大好き`seq`についてです。
`seq`はprimitiveとして提供されている関数の一つで、Core上では`case`に変換されるようです。要するに値をWHNFまで評価するための特殊な関数です。

```hs
seq :: a -> b -> b
```

`seq`が評価されると、第一引数をWHNFまで評価し、第二引数を（何もせずに）返します。

そしてこれは非常に重要なことですが、`seq`は<b>`seq`自体が評価されなければ何も機能しません</b>（`case`に変換されるとは言え、そう考えて構わないと思います）。
`seq`を適当に置いてみたけど発火しなくて一体どうなってるんだーと悩んだ方はそれなりにいるかもしれません。
`seq`は機能は特殊ですが、普通の関数同様に扱えばいいと覚えておいてください。


## モナド

モナドは命令型言語のstatementsの様に扱われます。その言及自体は正しいと思いますが、挙動を理解するためには一点覚えておく必要があります。

* 「アクションの評価」と「アクションの返り値の評価」は別

<b>追記: モナドに関しては次の日の記事に書き直しました</b>

## 簡単な例

最後に簡単な例を見ておきます。

```hs
main :: IO ()
main = do
	let succ1 x = trace "succ1" $ succ x
	    succ2 x = trace "succ2" $ succ x
	    succ3 x = trace "succ3" $ succ x
		thunkX = succ1 $ succ2 $ succ3 $ trace "thunkX" 5
	    thunkY = succ1 $ succ2 $ succ3 $ trace "thunkY" 42

	(x, y) <- return $ thunkX `seq` (thunkX, thunkY)

	print y
```

動作をイメージできるでしょうか。
出力結果は以下です(標準出力、エラー出力混ぜてます):

```
succ1
succ2
succ3
thunkX
succ1
succ2
succ3
thunkY
45
```

`(x, y)`のタプルのパターンマッチから、その右側のアクションが評価されます。
タプルの評価なので`x`, `y`はそれぞれ評価されないはずですが、`(<-)`の右側を評価するには`seq`を先に評価しなくてはなりません。よって`seq`の評価によって`thunkX`が評価されます。
`thunkX`は最左から`succ1`, `succ2`, `succ3`と順に評価され、最後に"thunkX"と出力され、8が`x`を束縛します。
その後`print`の要求から`thunkY`が評価され、最後に42に3を足した45が出力される、という流れです。


いろいろ書いてきましたが、そんなに複雑ではなく、少しのルールで説明できる様になっていることがわかると思います。

<del>明日はCoreとSTGに関して少し見ようかなと思います多分。</del>


## ツール

そういえばghciには :sprintや:stepといったコマンドが用意されています。
詳しくはheyhey Haskell本あたりを読んでください。