構文木に情報を追加したいときにFix使うとちょっと楽だよっていう話。 例えば data Term = Var String | Lam String Term | App Term Termみたいなデータの各ノードにIdを振りたいとする。 ナイーブにやると data ITerm = IVar Int String | ILam Int String…

導入 以下のBNF*1は足し算とlet式からなる式を表す。 <digit> ::= [0-9] <alphabet> ::= [a-zA-Z] <int> ::= <digit> | <digit><int> <id> ::= <alphabet> | <id> <expr> ::= <int> | <id> | '(' <expr> ')' | "let" <id> '=' <expr> "in" <expr> | <expr> '+' <expr>さて、この文法には２つの曖昧性がある。一つは足し算の結合性、もう一つはlet式と足し算の優先順位の曖昧</expr></expr></expr></expr></id></expr></id></int></expr></id></alphabet></id></int></digit></digit></int></alphabet></digit>…