『プログラミングHaskell』の関数型パーサーをStateTを使って書き直す

『プログラミングHaskell』の関数型パーサー(ソースコードはここの"Functional parsing library"、"Expression parser"からダウンロードできます)をStateTを使って書き直すと、次のようになります。

MyParser.hs

import Control.Monad.State
type Parser a = StateT String Maybe a
runParser = runStateT
parse :: Parser a -> String -> Maybe (a, String)
parse p inp = runParser p inp

item :: Parser Char
item = do x:xs <- get
          put xs
      return x

Parser aの定義から分かるようにモナドのインスタンスにするために、>>=を定義する必要はなくなります。

ここでテキストに合わせてparse p inp :: [(a, String)]になるようにtype Parser a = StateT String [a]にしてしまうと

ghci> parse nat "123"
[(123, ""), (12, "3"), (1, "23")]

になってしまいます。これは(+++) = mplusと定義されていることと、[]のmplusが(++)のシノニムになっているからで、実際に+++でリストの結合が起こっているところはmanyです。Maybeのmplusの定義は

Nothing `mplus` ys = ys
xs      `mplus` _  = xs

なので、今回の計算にちょうど合っています。あとはevalを次のように定義し直せば、正常に動作します。

MyParser.hs

eval :: String -> Int
eval xs = case (parse expr xs) of
            Just (n, "")  -> n
        Just (_, out) -> error ("unused input " ++ out)
        failure       -> error "invalid input"