Невозможно понять взаимную рекурсию

Question

Я читаю Программирование В Haskell, в 8-й главе автор приводит пример написания парсеров. Полный источник здесь: http://www.cs.nott.ac.uk/~gmh/Parsing.lhs Я не могу понять следующую часть: many разрешает ноль или более приложений p, в то время как many1 требуется хотя бы одно успешное приложение:

many        ::    Parser a → Parser [a ]
many p      =     many1 p +++ return [ ]
many1       ::    Parser a → Parser [a ]
many1 p     = do v ← p
                 vs ← many p
                 return (v : vs)

Как происходит рекурсивный вызов

vs <- many p

vs это значение результата many p, но многие п называют many1 p, все many1 имеет в своем определении нотацию do и снова имеет значение результата v, а также vsкогда возвращается рекурсивный вызов? Почему следующий фрагмент может вернуться [("123","abc")]?

> parse (many digit) "123abc"
[("123", "abc")]

Answer 1

По последнему вопросу:

> parse (many digit) "123abc"
[("123", "abc")]

Означает, что синтаксический анализ прошел успешно, поскольку в списке ответов был возвращен хотя бы один результат. Парсеры Hutton всегда возвращают список - пустой список означает ошибку синтаксического анализа.

Результат ("123", "abc") означает, что синтаксический анализ нашел три цифры "123" и остановился на "a", который не является цифрой, поэтому "остальная часть ввода" - это "abc".

Обратите внимание, что many означает "как можно больше", а не "один или несколько". Если бы это был "один или несколько", вы бы получили такой результат:

[("1", "23abc"), ("12", "3abc"), ("123", "abc")]

Такое поведение не очень хорошо для детерминированного анализа, хотя иногда может потребоваться для анализа на естественном языке.

Answer 2

Рекурсия останавливается на v <- p линия. Монадическое поведение парсера будет просто распространять [] до конца вычисления, когда p не может быть проанализирован больше.

p >>= f =  P (\inp -> case parse p inp of
                        []        -> [] -- this line here does not call f
                        [(v,out)] -> parse (f v) out)

Вторая функция написана в do-notation, что является хорошим синтаксисом для следующего:

many1 p = p >>= (\v -> many p >>= (\vs -> return (v : vs)))

Если синтаксический анализ p производит пустой список [] функция \v -> many p >>= (\vs -> return (v : vs)) не будет вызван, остановка рекурсии.

Answer 3

Позвольте мне раздеть это до самых скелетов, чтобы понять, почему do-блоки могут быть неправильно поняты, если они читаются просто как императивный код. Рассмотрим этот фрагмент:

doStuff :: Maybe Int
doStuff = do
    a <- Nothing
    doStuff

Это выглядит как doStuff будет повторяться вечно, в конце концов, это определено, чтобы сделать последовательность вещей, заканчивающихся на doStuff, Но последовательность строк в do-block - это не просто последовательность операций, выполняемая по порядку. Если вы находитесь в точке do-блок, способ обработки остальной части блока определяется определением >>=, В моем примере второй аргумент >>= используется только если первый аргумент не Nothing, Таким образом, рекурсия никогда не происходит.

Нечто подобное может случиться во многих разных монадах. Ваш пример немного сложнее: когда больше нет способов что-то анализировать, материал после >>= игнорируется