Haskell(GHCi)の:printが面白い

Haskellって、変数に束縛されている値が「評価されている」と「されていない」の状態を持っていて、それがグローバルにあちこちから共有されているから「どれくらいの計算量で終わるか」みたいな議論になるとイメージが掴めなくて困っていた。確認する方法があればいいのになぁ、でも、ないんだろうなぁと、諦めていたが、GHCiである程度できることがわかった。面白いじゃんこれ。

まずこんなソースコードを用意してみる。これは「リストを結合した時点で前半のリストは評価されるのか否か」を実験するためのコード。以前議論になったときに、僕の主張としては「前半を評価しないでも『xsの先頭1個と「xsの残りとysを結合したもの」のcons』を返せば良い。きっとその実装になってるだろう」というものだったのだけど、今までは挙動を観察する方法を知らなかったので議論止まりだった。

xs = [1, 2, 3]
ys = [4, 5, 6]
zs = xs ++ ys

このファイルをtmp.hsという名前で保存し、GHCiから以下のコマンドを実行する。

:load tmp.hs
:print xs
:print ys
:print zs
seq zs ()
:print zs
:print xs
seq _t6 ()
:print xs
:print zs
seq _t11 ()
:print zs
seq _t12 ()
:print zs
:print xs

そうすると以下の様な出力が得られる。

Prelude> :load tmp.hs
[1 of 1] Compiling Main             ( tmp.hs, interpreted )
Ok, modules loaded: Main.
*Main> :print xs
xs = (_t1::[Integer])
*Main> :print ys
ys = (_t2::[Integer])
*Main> :print zs
zs = (_t3::[Integer])
*Main> seq zs ()
()
*Main> :print zs
zs = (_t4::Integer) : (_t5::[Integer])
*Main> :print xs
xs = [(_t6::Integer),(_t7::Integer),(_t8::Integer)]
*Main> seq _t6 ()
()
*Main> :print xs
xs = [1,(_t9::Integer),(_t10::Integer)]
*Main> :print zs
zs = 1 : (_t11::[Integer])
*Main> seq _t11 ()
()
*Main> :print zs
zs = 1 : (_t12::Integer) : (_t13::[Integer])
*Main> seq _t12 ()
()
*Main> :print zs
zs = 1 : 2 : (_t14::[Integer])
*Main> :print xs
xs = [1,2,(_t15::Integer)]

順に読んでみよう。:printは評価を強制せずに値を調べるコマンドだ。最初は「[Integer]型の値」という情報しかない。

*Main> :print xs
xs = (_t1::[Integer])
*Main> :print ys
ys = (_t2::[Integer])
*Main> :print zs
zs = (_t3::[Integer])

seqを使ってパターンマッチできる程度に評価してみよう。

*Main> seq zs ()
()
*Main> :print zs
zs = (_t4::Integer) : (_t5::[Integer])

zsは_t4と_t5のconsであることがわかった。

一方この時xsは3要素のリストであることまでわかっている。これがなんでなのかは知らない。高速化のために短いリストは内部的に連結リストではない形で持っているとか?教えて詳しい人!

*Main> :print xs
xs = [(_t6::Integer),(_t7::Integer),(_t8::Integer)]

さて、その先頭の_t6を評価してみると、それが1であることがわかる。

*Main> seq _t6 ()
()
*Main> :print xs
xs = [1,(_t9::Integer),(_t10::Integer)]

この時zsはどうなっているか。先頭が1であることがわかっている。

*Main> :print zs
zs = 1 : (_t11::[Integer])

ではconsの残り_t11をseqしてconsをバラし、リストの2番めの要素_t12をseqしよう。2番めの要素が2であることがわかる。

*Main> seq _t11 ()
()
*Main> :print zs
zs = 1 : (_t12::Integer) : (_t13::[Integer])
*Main> seq _t12 ()
()
*Main> :print zs
zs = 1 : 2 : (_t14::[Integer])

この時xsも2番めが2であることがわかっている。

*Main> :print xs
xs = [1,2,(_t15::Integer)]

まとめ

Haskellの:printはとても面白い。:traceも面白いんだけどそれについて書くのはまた今度。あと、なんでxsの長さが3であることがわかったのか教えてください詳しい人!

参考文献: 2.5. GHCiデバッガ

追記

「[Integer] でやった場合では数値の表現から多倍長整数のデータを作る組み込み処理の評価が遅延している」
なるほど!確かにIntならそのまま表示されますね!

Prelude> let xs = [1, 2, 3] :: [Int]
Prelude> :print xs
xs = [1,2,3]
Prelude> let xs = [1, 2, 3] :: [Integer]
Prelude> :print xs
xs = [(_t1::Integer),(_t2::Integer),(_t3::Integer)]
Prelude> let xs = [1, (1 + 1), 3] :: [Int]
Prelude> :print xs
xs = [1,(_t4::Int),3]