Блог

Я читал эту статью о разборе монад, когда пытался реализовать довольно простой синтаксический анализатор строк в Haskell, а также получить лучшее представление об использовании монад. Ниже вы можете увидеть мой код, реализующий функции для сопоставления одного символа или целой строки. Это работает, как и ожидалось, но я наблюдал два странных поведения, которые не могу объяснить.

1. Я должен обрабатывать отдельные символы , в string противном случае анализатор будет возвращать только пустые списки. Если быть точным, если я удалю эту строку string [c] = do char c; return [c] , она больше не будет работать. Я ожидал, что string (c:s) с string (c:[]) этим все будет в порядке. В чем здесь может быть причина?
2. На мой взгляд, string определение должно быть эквивалентно string s = mapM char s тому, как оно создавало бы список [Parser Char] для каждого персонажа s и собирало результаты как Parser [Char] . Если я использую определение , основанное на mapM , программа застрянет в бесконечном цикле и ничего не напечатает. Есть ли что-то в ленивой оценке, чего мне здесь не хватает?

.

 module Main where

newtype Parser a = Parser { apply :: String->[(a, String)] }

instance Monad Parser where
    return a = Parser $ s -> [(a, s)]
    ma >>= k = Parser $ s -> concat [apply (k a) s' | (a, s') <- apply ma s]

instance Applicative Parser where
    pure = return
    mf <*> ma = do { f <- mf; f <

gt; ma; }
instance Functor Parser where

    fmap f ma = f <

gt; ma
empty :: Parser a

empty = Parser $ const []
anychar :: Parser Char

anychar = Parser f where

    f [] = []

    f (c:s) = [(c, s)]
satisfy :: (Char -> Bool) -> Parser Char

satisfy prop = do

    c <- anychar

    if prop c then return c

    else empty
char :: Char -> Parser Char

char c = satisfy (== c)
string :: String -> Parser String

string [] = empty

string [c] = do char c; return [c] --- if I remove this line, all results will be []

string (c:s) = do char c; string s; return (c:s)
main = do

    let s = "12345"

    print $ apply (string "123") s

    print $ apply (string "12") s

    print $ apply (string "1") s

    print $ apply (string []) s

 

пс. Я думаю, что название вопроса недостаточно наводит на размышления, пожалуйста, предложите отредактировать, если у вас есть идея получше.

1. Поскольку вы сделали string [] = empty это вместо string [] = return [] этого , вы не можете использовать его в качестве базового варианта для рекурсии, которая создает список.
2. fmap f ma = f <$> ma неверно, так <$> как определяется в терминах fmap . Если вы хотите определить fmap в терминах других ваших экземпляров, то сделайте fmap = liftA или fmap = liftM . Поскольку mapM используется fmap внутренне, но ваш оригинал string этого не сделал, эта проблема не возникла в вашем первом простом тесте.

 string [] = empty
 

означает: «Если вам нужно разобрать пустую строку, потерпите неудачу-ее вообще нельзя разобрать, независимо от того, какая строка ввода».

По сравнению,

 string [] = return ""
 

означает: «Если вам нужно проанализировать пустую строку, добейтесь успеха и верните пустую строку-ее всегда можно проанализировать, независимо от того, какая строка ввода».

Используя первое уравнение, при рекурсии в случае string (c:cs) , если вам нужно остановиться на одном символе ( string [c] ), так как при достижении нулевых символов запустится empty и приведет к сбою всего синтаксического анализатора.

Следовательно, вам нужно либо использовать это string [c] = return [c] уравнение, либо изменить базовый регистр «пустая строка», чтобы он был успешным. Возможно, последнее было бы более естественным.