非破壊Hash

ひさしぶりにParsecをいじってみた．

前回，(http://d.hatena.ne.jp/hoge1e3/20080129)

var a; a=3; var b; b=a+3;

というプログラムがあったときに，a や b にアドレスを割り付けたい，と言ったので，この部分の実装をやろうとした，が失敗．

 var a;  

という変数宣言を読ませる部分．ここで，
「a は アドレス 0 に割り当てる」
という処理をしたい．
その後，var b; がきたら
「b は アドレス 1 に割り当てる」
という処理をしたい．

Parsec には getState / setState があるから，状態にアドレスの連番とハッシュテーブル( 変数名 - アドレス ) をもたせたいと思って，次のように状態を定義し，

data ParserState = PStat Int (HashTable String Int) 
 -- HashTable は 標準のData.HashTable

変数宣言を解析する部分を次のようにした．

vardecl :: Parser Decl
vardecl = do { tok "var" 
             ; name <- symbol; tok ";"
             ; st <- getState  
             ; h <- (getSyms st) 
             ; update h name (getNum st)
             ; setState (PStat ((getNum st)+1) h )
             ; return $ VarDecl name (getNum st)
             } 

が，

Couldn't match expected type `GenParser Char ParserState t'
	   against inferred type `HashTable String Int'

これはdo文はdo文でもパーサのdo文だから，ここで IO を挟んだりはできない，ということらしい.

getState, setStateと馴染むためには，おそらくData.HashTableのようなIOベースのハッシュテーブルじゃなくて，非破壊的なハッシュテーブル，つまり

update :: Hash k v -> k -> v -> Hash k v

のように，
「もとのHash の内容にそっくりだけど，キーk に 値v を設定している点だけがちがう新しい Hash」
を返す，というメソッドがあればいいのに．

多分メモリを食うし速度も遅いからないのだろうか．