Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
22
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

正格評価と遅延評価(詳細編)

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

Debug.Trace.trace

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

import Debug.Trace (trace)

trace :: String -> a -> a

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

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

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

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

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

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

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

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

パターンの書き方と評価

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

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

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

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

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

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

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

{-# 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を仕込んで評価してみます。

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 ()

結果は以下です:

ghci> l
succ1
succ2
succ3

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

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

特殊な関数seq

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

seq :: a -> b -> b

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

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

モナド

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

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

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

簡単な例

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

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が出力される、という流れです。

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

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

ツール

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
22
Help us understand the problem. What are the problem?