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

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

4 голосов
/ 21 мая 2011

Я читаю Программирование В 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, но многие p, называемые many1 p, все, что many1 имеет в своем определении, это doнотации и снова имеет значение результата v и vs, когда возвращается рекурсивный вызов?Почему следующий фрагмент может вернуть [("123","abc")]? 

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

Ответы [ 3 ]

6 голосов
/ 21 мая 2011

Рекурсия останавливается на линии 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-нотации, которая простохороший синтаксис для следующего: 

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

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

2 голосов
/ 21 мая 2011

За последний вопрос: 

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

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

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

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

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

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

1 голос
/ 30 мая 2011

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

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

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

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

...