いろいろなパッケージから提供されている ListT モナド変換子の違いについて調べてみる

この記事は Haskell (その2) Advent Calendar 2017 の10日目の記事です。あけましておめでとうございます。 今回は ListT モナド変換子 について調べたことをまとめます。

hackage で検索をすると ListT と名の付くモナド変換子を提供しているパッケージは4つほど見つかります。

• Control.Monad.Trans.List - transformers パッケージ
• Control.Monad.List - mtl パッケージ
• ListT - list-t パッケージ
• Pipes - pipes パッケージ

このうち mtl パッケージで提供している ListT は transformers パッケージからインポートされているだけなので実装としては同一のものです。
また、pipes パッケージで提供されているものは Pipes と組み合わせて使うもののようで、単独で List モナドの変換子版というわけではなさそうです。

さらにさらに、 transformers パッケージの Control.Monad.Trans.List のドキュメント を見にいくとページ先頭に赤字で不穏な注釈が書かれています。

Deprecated: This transformer is invalid on most monads
(非推奨：このモナド変換子はほとんどのモナドに対して無効です)

非常に不穏ですね。

ただ、これだけの情報ではなぜ transformers パッケージの実装ではダメなのか、代わりに何を使えばいいのか分かりません。

ListT done right を読む

transformers パッケージの ListT について、ListT done right に詳しく書かれています。
要点をかいつまむと、

• 従来の ListT は過剰な正格性を課している
• 従来の ListT はいわゆるモナド変換子ではない。 m がモナドであっても ListT m がモナドになるとは限らない
• なので、上記の欠点を解消したバージョンの実装を提案する
• 新しい実装をさらに洗練させてパッケージにまとめたものが list-t である

というわけで、
TL;DR な方のために結論を書いておくと、transformers パッケージの実装はいろいろと間違っているので list-t パッケージの方を使おう ということみたいです。

テストプログラムで ListT を比べる

ListT done right には transformers パッケージの実装が正しく動かないことを示すテストのプログラムが挙げられています。
引用して、実際に実行出来るかたちにまとめてみました。パッケージ毎に結果を見てみましょう。今回は transformers と list-t を比べてみます。

github.com

いつものとおり全てのコードは GitHub に置いておきます。

1. Sum of squares - 平方和

整数 n を与えると二平方の和で n に等しくなる組を探すプログラムです。 例えば、 5 を与えると (1, 4) と (4, 1) が答えになります。

testSumOfSquares :: Int -> ListT IO (Int, Int)
testSumOfSquares n = do
    let squares = liftList . takeWhile (<= n) $ map (^ (2 :: Int)) [0 ..]
    x <- squares
    y <- squares
    lift $ print (x, y)
    guard $ x + y == n
    lift $ putStrLn "Sum of Squares."
    return (x, y)

runTestSumOfSquares :: Int -> IO (Int, Int)
runTestSumOfSquares = fmap fromJust . ListT.head . testSumOfSquares

これ自体、リスト内包表記などでシンプルに実装できそうな処理ですが、今回は ListT IO を使って平方和の探索の途中途中で標準出力を挟むようにしてあります。

さて、testSumOfSquares は全ての答えをリストで返してくれますが、もし答えが複数あってそのうち 最初の解だけ が必要なときにはどうでしょうか。
リストから最初の要素だけを取り出すことは簡単です。問題は 遅延評価のアイデアに従って最初の答えを得るために必要な IO アクションだけ実行されて欲しい という部分です。

では見てみましょう。

実行結果 : Control.Monad.Trans.List.ListT from transformers

ghci> FromTransformers.runTestSumOfSquares 5
(0,0)
(0,1)
(0,4)
(1,0)
(1,1)
(1,4)
Sum of Squares.
(4,0)
(4,1)
Sum of Squares.
(4,4)

(1,4)

候補となる全ての組 (0,0),(0,1),(0,4), ... ,(4,1),(4,4) をまとめて探索しつくしている様が見られます。
今回は候補となる組が有限なのでいいですが、候補となる組が無限リストで与えられた場合には上手く動作しないでしょう。

実行結果 : ListT.ListT from list-t

ghci> FromListT.runTestSumOfSquares 5
(0,0)
(0,1)
(0,4)
(1,0)
(1,1)
(1,4)
Sum of Squares.

(1,4)

答えとなる最初の組 (1,4) が見つかった時点で、残りの IO アクションは実行されずに捨てられています。
こちらが望ましい動作ですね。

これは list-t パッケージが uncons :: ListT m a -> m (Maybe (a, ListT m a)) という関数を提供しているおかげです。
uncons は先頭の要素を得るのに必要な分だけ内側のモナドを実行します。

2. Grouping effects - 結合効果

今度は モナド則のうち結合則が破れる という例です。
モナドの結合則とは、

(m >>= f) >>= g == m >>= (\x -> f x >>= g)

のことです。

testGroupingEffects1 :: ListT IO Int
testGroupingEffects1 = do
    r <- liftIO $ newIORef 0
    (next r `mplus` next r >> next r `mplus` next r) >> next r `mplus` next r

runTestGroupingEffects1 :: IO [Int]
runTestGroupingEffects1 = toList testGroupingEffects1


testGroupingEffects2 :: ListT IO Int
testGroupingEffects2 = do
    r <- liftIO $ newIORef 0
    next r `mplus` next r >> (next r `mplus` next r >> next r `mplus` next r)

runTestGroupingEffects2 :: IO [Int]
runTestGroupingEffects2 = toList testGroupingEffects2


next :: IORef Int -> ListT IO Int
next r = liftIO $ do
    x <- readIORef r
    writeIORef r (x + 1)
    return x

本来であれば runTestGroupingEffects1 と runTestGroupingEffects2 の実行結果は等しくなるはずです。

実行結果 : Control.Monad.Trans.List.ListT from transformers

ghci> FromTransformers.runTestGroupingEffects1
[6,7,8,9,10,11,12,13]

ghci> FromTransformers.runTestGroupingEffects2
[4,5,6,7,10,11,12,13]

transformers パッケージの実装ではモナドの結合則が破れていることが確認できました。
これは m がモナドであっても ListT m がモナドになるとは限らない ということを意味します。

実行結果 : ListT.ListT from list-t

ghci> FromListT.runTestGroupingEffects1
[2,3,5,6,9,10,12,13]

ghci> FromListT.runTestGroupingEffects2
[2,3,5,6,9,10,12,13]

list-t の方は正しく動作しています。

3. Order of printing - 印字順

リスト操作の中でも頻繁に使うものの中にリストの結合 (++) があります。
ListT の結合は MonadPlus クラスの mplus メソッドで代用できますが、transformers パッケージの実装では mplus が正しく動かないという例です。

a, b, c :: ListT IO ()
[a, b, c] = map (liftIO . putChar) ['a', 'b', 'c']


testOrderOfPrinting1 :: ListT IO ()
testOrderOfPrinting1 = ((a `mplus` a) >> b) >> c

runTestOrderOfPrinting1 :: IO (Maybe ((), ListT IO ()))
runTestOrderOfPrinting1 = runListT' testOrderOfPrinting1


testOrderOfPrinting2 :: ListT IO ()
testOrderOfPrinting2 = (a `mplus` a) >> (b >> c)

runTestOrderOfPrinting2 :: IO (Maybe ((), ListT IO ()))
runTestOrderOfPrinting2 = runListT' testOrderOfPrinting2

testOrderOfPrinting1, testOrderOfPrinting2 とも、正しく実装されていれば [putChar 'a' >> putChar 'b' >> putChar 'c', putChar 'a' >> putChar 'b' >> putChar 'c'] みたいな IO アクションを生成してくれるはずです。

実行結果 : Control.Monad.Trans.List.ListT from transformers

ghci> FromTransformers.runTestOrderOfPrinting1
aabbcc

ghci> FromTransformers.runTestOrderOfPrinting2
aabcbc

リストを構成する時点で IO アクションが実行されてしまうためにこのような印字になってしまうようです。

実行結果 : ListT.ListT from list-t

ghci> FromListT.runTestOrderOfPrinting1
abc

ghci> FromListT.runTestOrderOfPrinting1
abc

いい感じですね。

4. Order of ListT []

これまでの例は全て ListT IO に関するものでした。
IO モナドを含まないシンプルな例でもモナドの結合則が破れることを示すために ListT [] の例が示してあります。

v :: Int -> ListT [] Int
v 0 = ListT [0, 1]
v 1 = ListT [[0], [1]]


runTestOrderOfListTList1 :: IO ()
runTestOrderOfListTList1 = print $ toList $ ((v >=> v) >=> v) 0

runTestOrderOfListTList2 :: IO ()
runTestOrderOfListTList2 = print $ toList $ (v >=> (v >=> v)) 0

なんだかややこしそうですが、 ((v >=> v) >=> v) 0 と (v >=> (v >=> v)) 0 が等しくなるかどうかを確かめるだけのプログラムです。

実行結果 : Control.Monad.Trans.List.ListT from transformers

ghci> FromTransformers.runTestOrderOfListTList1
[[0,1,0,0,1],[0,1,1,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1]]

ghci> FromTransformers.runTestOrderOfListTList2
[[0,1,0,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0,1],[0,1,1,0],[0,1,1,1]]

transformers パッケージの実装では結合則が破れていることを確かめられました。

実行結果 : ListT.ListT from list-t

ghci> FromListT.runTestOrderOfListTList1
[[1,0,0,1,0],[1,0,1,1,0],[0,0,1,0],[0,1,1,0],[1,0,1,0],[1,1,1,0]]

ghci> FromListT.runTestOrderOfListTList2
[[1,0,0,1,0],[1,0,1,1,0],[0,0,1,0],[0,1,1,0],[1,0,1,0],[1,1,1,0]]

バッチリですね。

まとめ

というわけで、 ListT done right に挙げられている例を実際のプログラムで確かめることができました。
また、 transformers と mtl の動作が全く同じになる事も確かめています。

さて、ここまできて確かめられていないこと、それは、

• list-t パッケージの実装なら全てのモナド m に対して ListT m がモナドになるの？

ということですね。こちらは追試が必要そうです。
(>>=) の実装から運算によって確かめられないかと思って手を動かしてみたのですが、私の運算力では無理でした。

どなたかご存知の方がいれば情報ください。

私からは以上です。

Haskell でλ計算のインタプリタを作っていこう ～ その3. プリティプリンタ

引き続き Mogul という名前のλ計算インタプリタを作っていこうと思います。
前回、パーザを書いたのでソースコードから抽象構文木を生成することができるようになりました。さっそく抽象構文木をいじくり回して何かしらの処理を実装したいところですが、今回はその前の下準備です。

ソースコード全体は GitHub に置いておきます。

github.com

抽象構文木は読みづらい

当たり前なんですが、素の抽象構文木は読みづらいです。例えば ^f x y.``fyx の抽象構文木はこれ。

Ident "f":^ (Ident "x" :^ (Ident "y" :^ (Var (Ident "f") :$ Var (Ident"y")):$ Var (Ident "x")))

実際、内部的にこのようなデータが扱われているとはいっても、デバッグ時にこれをそのまま読みたくない感じはじますよね。
というわけで前回、パーザを書いて文字列から抽象構文木を作ったので、今回は逆をやりましょう。プリティプリンタで抽象構文木を文字列に変換します。

プリティプリンタの要件

と云ってもそこまで難しいことをするつもりはありません。とにかく 文字列化 ができればいいだけです。 Mogul で扱っているいろいろなデータ型を良い感じに文字列化する pp :: a -> String を実装します。

関数 pp に求められる数少ない要件は以下の通り。

1. Expr, Func など様々なデータ型に対して動くようにする
2. 文字列化した後、再度 抽象構文木にパースすることが可能な、正しい Mogul コードを生成する
3. 余計なスペースを省いてコードの密度を高く保つ

というわけでやっていきましょう。

PPrintable クラス

関数 pp で様々なデータ型を文字列化したいので、型クラス PPrintable を定義して pp をそのクラスのメソッドにします。

class PPrintable a where
    prepara :: a -> [Token]
    pp      :: a -> String
    pp = render . prepara

この PPrintable クラス、なんだが Show クラスに似ていますよね。実際、役割はほぼ同じです。
ghci などでカジュアルにデータ型を表示するために show の動作はそのまま残しておきたいので、あえて Show インスタンスの独自定義はせずに別のクラスを用意します。

もう一つの特徴として prepara :: a -> [Token] によって一度データ型をトークンの列に変換している点が挙げられます。
Mogul の Expr 型は二分木に似た構造ですが、それをまず平坦な Token の列に変換します。そうすることで隣のトークンを読んで適切な位置にスペースを挿入することがやりやすくなります。

Token 型の定義はこんな感じ、

data Token = Backquote         -- "`"
           | Lambda            -- "^"
           | Dot               -- "."
           | Equal             -- "="
           | Symbol Text       -- 英小文字1文字からなるシンボル
           | LargeSymbol Text  -- 英数字2文字以上からなるシンボル
           | EOL               -- 行端
  deriving (Eq)

instance Show Token where
    show Backquote       = "`"
    show Lambda          = "^"
    show Dot             = "."
    show Equal           = "="
    show (Symbol s)      = unpack s
    show (LargeSymbol s) = unpack s
    show EOL             = "\n"

さて、 PPrintable クラスのメソッドの中でも pp にはデフォルトの定義があります。

pp = render . prepara

まず prepara :: PPrintable a => a -> [Token] を使ってトークンの列に変換して、その後に render :: [Token] -> String を使って文字列に変換します。
render の実装は以下のとおり、

render :: [Token] -> String
render []       = ""
render (s@(LargeSymbol _) : ps@(LargeSymbol _ : _))
                = show s <> " " <> render ps
render (s@(Symbol _) : ps@(LargeSymbol _ : _))
                = show s <> " " <> render ps
render (p : ps) = show p <> render ps

LargeSymbol と LargeSymbol が並んでいるとき、または Symbol と LargeSymbol が並んでいるときに限り間に1つのスペースを挿入しながら文字列として結合します。
それ以外の場合はただトークンを文字列に変換しながら並べていくだけです。

PPrintable クラスのインスタンス宣言

ではそれぞれのデータ型を PPrintable クラスのインスタンスにしていきます。対象となるのは Ident, Expr, Func, (Ident, Func), Context です。

{-# LANGUAGE FlexibleInstances #-}

instance PPrintable Ident where
    prepara = (:[]) . symbol

instance PPrintable Expr where
    prepara = flatten []

instance PPrintable Func where
    prepara = prepara . body

instance PPrintable (Ident, Func) where
    prepara (v, f) = symbol v : Equal : prepara f

instance PPrintable Context where
    prepara = Data.Map.foldrWithKey (\v f cont -> prepara (v, f) <> (EOL : cont)) []

PPrintable (Ident, Func) に対するインスタンス宣言をする際には FlexibleInstances 拡張 を有効にする必要があります。

補助関数 symbol, body, flatten の定義は以下の通り、

-- | symbol (Ident "x"  ) => Symbol "x"
-- | symbol (Ident "FOO") => LargeSymbol "FOO"
symbol :: Ident -> Token
symbol v@(Ident x)
    | isUniIdent v = Symbol x
    | otherwise    = LargeSymbol x

-- | body (Func [Ident "x", Ident "y"] (Var (Ident "y") :$ Var (Ident "x")))
-- |   => Ident "x" :^ Ident "y" :^ Var (Ident "y") :$ Var (Ident "x")
body :: Func -> Expr
body (Func vs e) = foldr (:^) e vs

flatten :: [Token] -> Expr -> [Token]
flatten acc (e :$ e') = Backquote : flatten (flatten acc e') e
flatten acc (x :^ e)  = Lambda : symbol x : Dot : flatten acc e
flatten acc (Var x)   = symbol x : acc

大きな木構造を平坦なリストに変換するという意味で flatten は特に重要です。第1引数はただのアキュムレータなので余り気にする必要はありません。 flatten [] :: Expr -> [Token] をトークンの列を得る目的で使っています。
Expr 以外のデータ型は再帰も含まないシンプルなものなので、よしなにトークン列に変換してあげれば大丈夫でしょう。

使ってみる

という訳で pp を使っていくつかの式を文字列化してみます。

ghci> let Right e = parse expr "" "^xyz.``xz`yz"
ghci> e
Ident "x" :^ (Ident "y" :^ (Ident "z" :^ (Var (Ident "x") :$ Var (Ident "z")) :$ (Var (Ident "y") :$ Var (Ident "z"))))
ghci> pp e
"^x.^y.^z.``xz`yz"

ghci> Right e = parse expr "" "``x `FOO BAR y"
gchi> e
(Var (Ident "x") :$ (Var (Ident "FOO") :$ Var (Ident "BAR"))) :$ Var (Ident "y")
ghci> pp e
"``x`FOO BARy"

ghci> let Right e = parse def "" "````Jxyzw = ``xy``xwz"
ghci> e
(Ident "J",Func {args = [Ident "x",Ident "y",Ident "z",Ident "w"], bareExpr = (Var (Ident "x") :$ Var (Ident "y")) :$ ((Var (Ident "x") :$ Var (Ident "w")) :$ Var (Ident "z"))})
ghci> pp e
"J=^x.^y.^z.^w.``xy``xwz"

pp のおかげで確実に可読性が向上いていますね。良い感じです。

まとめ

というわけで可読性確保のために、云うほど pretty でもないプリティプリンタを書きました。
次回は Expr 型に ド・ブラン・インデックス の概念を取り入れてみようかと思います。

私からは以上です。

Haskellでλ計算のインタプリタを作っていこう ～ その2. パーザ

引き続き Mogul という名前のλ計算インタプリタを作っていこうと思います。
前回、λ式を表現するデータ型を定義したので、今回はパーザを書きます。ソースコードを読ませて抽象構文木を生成するところまでです。

ソースコード全体は GitHub に置いておきます。

github.com

Mogul の構文

パーザを書くにあたってまずは構文を決めなければいけません。
Mogul の構成要素で重要なのは 変数, 関数抽象, 関数適用 そして 関数定義 です。ぞれぞれ以下のような構文にしようと思います。

変数

変数の構成要素として許される文字は 英数字 + アンダースコア _ です。
ただし、英小文字は必ず1文字で一つの変数として解釈されます。英大文字, 数字, アンダースコアは複数連なっていればまとめて一つの変数だと解釈されます。

いくつかの例を挙げましょう、
a や x や FOO や FOO_2 は全て正しい変数名と解釈されます。

xy と書いた場合、これは二つの変数 x と y が連続したものだと解釈されます。同様に Foo は三つの変数 F, o, o が連続したものだと解釈されます。

驚くべきことに(?)、_ や 42 なども変数名として正しいと解釈されます。
常識的なプログラミング言語では 42 と書くと整数リテラルだと解釈されるでしょう。しかし幸か不幸かλ計算の世界に整数などというものは存在しません。なので 42 のように整数っぽく見えるものでも変数名として許してしまいます。

関数抽象

関数抽象は をほぼそのまま書けるようにします。唯一の違いは λ の代わりに ^ を使うことです。

^x.M

と書くと、 のことだと解釈されます。

また、λ計算の世界には1変数関数しか存在しないので、複数の引数をもとに計算を行いたい場合には、

という感じで カリー化 を行います。
もちろん Mogul でも全ての関数は1変数関数として扱われますが、ネストした関数抽象のために以下のような糖衣構文を許すことにします。

^x y z.M

これは ^x.^y.^z.M と書いたのと同じように解釈されます。

関数適用

前回の記事でも宣言したとおり、関数適用には Unlambda 記法を採用します。
すなわち x に y を適用するときは、バッククォート ` を使って

`xy

と書くことにします。

関数定義

関数定義の構文はこうです、

FLIP = ^f.^x.^y.``f y x

左辺に関数名、右辺に関数の本体を置き、左辺と右辺をイコール = でつなぎます。
また、左辺に 仮引数 を伴った書き方も許すことにします。

```FLIP f x y = ``f y x

または間を取った以下のような書き方も正しいです。

`FLIP f = ^x.^y.``f y x

実はこれら三つの書き方には別の意味を持たせようと思っています。前回の記事にも出た アリティ(項数) の概念です。
ひとまず今は 仮引数を左辺に置くか右辺に置くかによって別の構文木を生成させる ということだけ頭の片隅に置いてもらえれば大丈夫です。

コメント

ついでに、Mogul ではラインコメントを書けるようにします。
コメントとして扱われるのは # から行末までです。Python や Ruby と同じですね。

# 引数の適用順を入れ替える
`FLIP f = ^x.^y. ``f y x  # この部分はコメントです

ブロックコメント(複数行コメント)はありません。

BNF

というわけで、Mogul の構文を BNF で書き下すと、

# 識別子
<lower>            ::= "a" | ... | "z"
<upper>            ::= "A" | ... | "Z"
<digit>            ::= "0" | ... | "9"
<identifier>       ::= <lower> | (<upper> | <digit> | "_")+

# λ式
<var>              ::= <identifier>
<lambda>           ::= "^" (<identifier>)+ "." <expr>
<apply>            ::= "`" <expr> <expr>
<expr>             ::= <var> | <lambda> | <apply>

# 関数定義
<func_name>        ::= <identifier>
<param>            ::= <identifier>
<ident_and_params> ::= <func_name> | "`" <ident_and_params> <param>
<def>              ::= <ident_and_params> "=" <expr> EOL

# コンテキスト (関数定義の組)
<context>          ::= (<def>)*

このようになりますね。

これをもとにパーザを書いていきましょう。

使用するライブラリ

パーザコンビネータのライブラリとして、おなじみの parsec3 を使います。
Applicative スタイルで行を節約しながら書けるのがいい感じです。

今回は Text 型のストリームを読みながら抽象構文木に変換していくので、 Text.Parsec.Text をインポートします。

パーザを書く

書いていきましょう。

識別子

-- | 識別子
ident :: Parser Ident
ident = ident' <|> ident''

ident' :: Parser Ident
ident' = Ident . singleton <$> lower

ident'' :: Parser Ident
ident'' = Ident . pack <$> many1 (upper <|> digit <|> char '_')

途中に登場している singleton や pack は、それぞれ Data.Text.singleton と Data.Text.pack です。

λ式

λ式は 変数, 関数抽象, 関数適用 の組み合わせで再帰的に定義されるので、それをそのままコードに落とし込みます。

-- | λ式
expr :: Parser Expr
expr = apply <|> lambda <|> var

-- | 変数
var :: Parser Expr
var = Var <$> ident

-- | 関数抽象
lambda :: Parser Expr
lambda = do
    token $ char '^'
    v  <- token ident
    vs <- many $ token ident
    token $ char '.'
    e  <- token expr
    return $ mkLambda (v:vs) e
  where
    mkLambda vs e = foldr (:^) e vs

-- | 関数適用
apply :: Parser Expr
apply = do
    token $ char '`'
    e  <- token expr
    e' <- token expr
    return $ e :$ e'

実はここでも Unlambda 記法を採用することのメリットが発揮されていて。Unlambda 記法だと var と lambda と apply の動作が互いに排他になります。なので Text.Parsec.Prim.try を使う必要がなくなって、コードがシンプルになり、頭の中で動作も追いやすくなってます。

関数定義

このパートでは関数名(Ident)と無名関数(Func)のタプルを取り出すことがゴールです。

-- | 関数定義の左辺部 "```f x y z" の形だけを許す
defFunc :: Parser (Ident, [Ident])
defFunc = defFunc' <|> do
    funcName <- token ident
    return (funcName, [])

defFunc' :: Parser (Ident, [Ident])
defFunc' = do
    token $ char '`'
    (funcName, args) <- token defFunc
    arg <- token ident
    return (funcName, arg:args)

-- | 関数定義
def :: Parser (Ident, Func)
def = do
    (funcName, reversedArgs) <- token defFunc
    token $ char '='
    e <- token expr
    spaces'
    skipMany lineComment
    void endOfLine <|> eof
    return (funcName, Func (reverse reversedArgs) e)

def の do 構文の中でなんだか汚いことやってますね。
関数定義は複数行に渡ってもよくて、かつ、どこかの行末で終わるはずで、さらに、ここでついでにラインコメントを読み飛ばそうとしているのでめっちゃ汚くなってます。

この部分を見通しよくするには、まずソースコードを lexer に通してコメントを読み飛ばしながらトークン列に変換して、次の段階でトークン列を parser に通して抽象構文木に変換するような実装にすればいいはずです。
が、この部分以外は lexer と parser に分けるまでもないくらいにシンプルなので作り込むのが面倒なんですよね。

ま、ちゃんと動いてますよ。一応テストも書いているし。

コンテキスト

コンテキストとは複数の関数定義の集まりです。
実装上では関数名(Ident)と無名関数(Func)の Map になっています。

-- | コンテキスト (関数定義の組)
context :: Parser Context
context = Map.fromList <$> many1 def

def が関数名と無名関数のタプルを返すようにしたので、many1 で複数個取ってきてから Data.Map.fromList に食わせるだけですね。

ここで many ではなく many1 を使った理由としては、...不明です。
ここなんで敢えて many1 を使っているんだろう。これだと空の文字列を読ませたときにパースエラーになりますね。このコード書いたのがざっくり2年前なので意図を忘れました。ここは後々書き換えるかも知れません。

使ってみる

実際にパーザにコードを読ませて抽象構文木を作ってみましょう。

ghci> parse expr "" "``skk"
Right ((Var (Ident "s") :$ Var (Ident "k")) :$ Var (Ident "k"))

ghci> parse expr "" "^xy.`yx"
Right (Ident "x" :^ (Ident "y" :^ Var (Ident "y") :$ Var (Ident "x")))

ghci> parse expr "" "````s`k`sika^x.`xx"
Right ((((Var (Ident "s") :$ (Var (Ident "k") :$ (Var (Ident "s") :$ Var (Ident "i")))) :$ Var (Ident "k")) :$ Var (Ident "a")) :$ (Ident "x" :^ Var (Ident "x") :$ Var (Ident "x")))

いい感じですね。

関数定義のほうも試してみます。

ghci> parse def "" "I = ^x.x"
Right ( Ident "I"
      , Func {
            args     = []
          , bareExpr = Ident "x" :^ Var (Ident "x")
      })

読みやすいように整形してみました。
ちゃんと 関数名 Ident "I" と 無名関数 Func {args = [], bareExpr = Ident "x" :^ Var (Ident "x")} のタプルが返ってきてますね。

仮引数を左辺に置くか右辺に置くかによって別の構文木を生成させる と云ってた件、試してみます。

ghci> parse def "" "FLIP = ^f.^x.^y.``f y x"
Right ( Ident "FLIP"
      , Func {
            args     = []
          , bareExpr = Ident "f" :^ (Ident "x" :^ (Ident "y" :^ (Var (Ident "f") :$ Var (Ident "y")) :$ Var (Ident "x")))
      })

ghci> parse def "" "```FLIP f x y = ``f y x"
Right ( Ident "FLIP"
      , Func {
            args     = [Ident "f",Ident "x",Ident "y"],
            bareExpr = (Var (Ident "f") :$ Var (Ident "y")) :$ Var (Ident "x")
      })

ghci> parse def "" "`FLIP f = ^x.^y.``f y x"
Right ( Ident "FLIP"
      , Func {
            args     = [Ident "f"]
          , bareExpr = Ident "x" :^ (Ident "y" :^ (Var (Ident "f") :$ Var (Ident "y")) :$ Var (Ident "x"))
      })

関数定義の左辺に置いた仮引数は Func 型の args フィールドの中で保持しています。
今のところの狙いは 左辺にいくつの仮引数が置かれていたかデータ型覚えておくこと です。

まとめ

Mogul の構文を整理しつつ、対応するパーザを書いてきました。
今回見せたパーザは何度も書き直しつつ洗練させてきたものなので少しは読みやすく書けてるんじゃないかと自負しております。

ソースコードを読んで抽象構文木を作れるようになったので、次回は プリティプリンタ を書いて抽象構文木をうまく印字できるようにします。

私からは以上です。