IArrayの怠け度合い

Haskell unsafe Array Memoize

今日はちょっとしたメモ…

リストのレイジーな振舞い方は割りとはっきりとイメージできるのですが、ちょっと遊びでIArrayを使っていて遅延評価がどういった形で動いているのかが気になったので、ちょっと実験してみました。

IArray、つまりImmutableなArrayを作る方法はいくつかあるのですが、基本は配列に変換したいデータをリストとして渡す形になります。僕が気になったのは、リストはいつどどういった形で評価されるのかということですね…たとえば、

getContents :: IO String

などは、unsafeを使ってそれぞれの文字が必要になったときにIOを行うようになっています。getContentsで取得した文字列を配列に変換するとして、ファイルIOはいったいどの時点で起きるのでしょう？

ということで書いてみた実験コードはこんな感じ:

module Main where

import Data.Array.IArray
import Debug.Trace

data SqueakyList a = Sq a (SqueakyList a) | Nil

toSql :: [a] -> SqueakyList a
toSql [ ] = Nil
toSql (a:as) = Sq a $ toSql as

toLst :: SqueakyList a -> [a]
toLst Nil = [ ]
toLst (Sq a as) = trace "list" $ a : (toLst as)

squeak a = trace ("element" ++ (show a) ) a

str = "test"
strSq = map (squeak) str

print3rd :: Array Int Char -> IO ()
print3rd ar = trace "!2" $ print (ar ! 2)

ar :: Array Int Char
ar = arit $ toLst $ toSql $ map (squeak) str

arit :: [a] -> Array Int a
arit as = listArray (0, 3) as

main = do
	putStrLn "Test1"
	print3rd $ arit $ toLst $ toSql strSq
	putStrLn "Test2"
	print3rd $ arit $ toLst $ toSql strSq
	putStrLn "Test3"
	print $ take 2 $ assocs ar
	putStrLn "Test4"
	print $ assocs $ ar

リストの各要素が展開されていくのを見るためにSqueakyListという型を定義しました。これはリストの要素が展開されるたびにトレースを出すようになってます。ここはもっとシンプルなやり方もありそうですね…

そして、このコードの出力はこうなりました:

Test1
!2
list
list
list
list
element's'
's'
Test2
!2
list
list
list
list
's'
Test3
list
list
list
list
element't'
element'e'
[(0,'t'),(1,'e')]
Test4
element's'
element't'
[(0,'t'),(1,'e'),(2,'s'),(3,'t')]

さて、何がわかったかというと:
１．配列の生成に渡したリストは配列の要素への最初のアクセスが起きた時点で配列の生成に使われる部分はすべて展開される。ということで、getContentsの結果をそのまま配列の生成に使うと、必要なIOはすべて配列の要素に始めてアクセスする時点で起きるようです。これはTest1のトレースが!2の後にlistが４回立て続けに起きていることでわかりますね…

さらに、ほかにもわかったことがあります。
２．どうやらリストの各要素に格納されている値もボックス型になっているようで、値が評価されるのはどうやら配列の中のその要素がアクセスされた時点のようです。Test1では３文字目の's'を取り出すのにelementトレースが一つ出てますね…でも、Test2のほうではメモ化が効いているようでelementトレースが出ていません。ということで、メモ化はstrSqの内部で起きているということがいえそうですね。

３．さらにTest3とTest4を見てもメモ化の作用が見て取れますね。

ちなみにリストは今回のSqueakyListでもわかるようにHaskellの言語の範疇でで簡単に作ることができるのですが、配列のほうはどうもそうはいかないようですね。IArrayのコードをたどっていくと最終的にはコンパイラなのか、ランタイムなのかわかんないんですが、unsafeな配列生成内部関数が呼び出されているのがわかります。リンクリストよりも配列のほうがインプリメントが難しい言語というのも面白いですね…

きょうはこのへんで。
ではでは。