「プログラミングHaskell 第2版」１３章の「モナドパーサー」を読んでいますが、
以下の式がどう簡約されていき、最終的に[("1", "a")]と評価されているのか分からず、苦戦中。。
これ、どのような順序で式が評価されていってるのでしょう。。
>parse (some digit) "1a"
[("1","a")]以下の簡約の仕方だと、永遠に評価が終わらない。
-- many x = some x <|> pure []
-- some x = pure (:) <*> x <*> many x
parse (some digit) "1a"
parse (pure (:) <*> digit <*> many digit) "1a"
parse (pure (:) <*> digit <*> (some digit <|> pure [])) "1a"
parse (pure (:) <*> digit <*> ((pure (:) <*> digit <*> many digit) <|> pure [])) "1a"
…（以下略）
ちなみに、以下のコードを叩いてみたら、次の結果となったので、末尾の相互再帰(many/some)の部分は遅延評価されているように思えますが、具体的にどう簡約されていくのかが分からないです。。
>parse (some digit) (repeat 'a')
[] --これは直ちに結果（empty)を返す
>parse (some digit) (repeat '1')
*** Exception: stack overflow --スタックオーバーフローが発生
＜補足＞
上記の元となる実装は以下です。
newtype Parser a = Parser (String -> [(a, String)])
parse :: Parser a -> String -> [(a, String)]
parse (Parser p) inp = p inp
instance Alternative Parser where
empty = Parser (\inp -> [])
p <|> q = Parser (\inp -> case parse p inp of
[] -> parse q inp
[(a, out)] -> [(a, out)])
many x = some x <|> pure []
some x = pure (:) <*> x <*> many x
instance Functor Parser where
fmap f p = Parser (\inp -> case parse p inp of
[] -> []
[(a, out)] -> [(f a, out)])
instance Applicative Parser where
pure v = Parser (\inp -> [(v, inp)])
pf <*> pa = Parser (\inp -> case parse pf inp of
[] -> []
[(f, out)] -> parse (fmap f pa) out)
instance Monad Parser where
return = pure
p >>= f = Parser (\inp -> case parse p inp of
[] -> []
[(v, out)] -> parse (f v) out)
item :: Parser Char
item = Parser (\inp -> case inp of
[] -> []
(x:xs) -> [(x, xs)])
sat :: (Char -> Bool) -> Parser Char
sat p = do
x <- item
if p x then return x else empty
digit :: Parser Char
digit = sat isDigit