Разрушение «Может быть (а, б)»
Своего рода продолжение моего последнего вопроса. Я прохожу курс Брента Йорги по Haskell и пытаюсь решить упражнение, в котором нам предлагается создать экземпляр Applicative для следующего типа:
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }
runParser анализирует строку и возвращает токен и оставшуюся строку. В этом случае p1 <*> p2 должен применить функцию, сгенерированную runParser p1, к токену, сгенерированному runParser p2 (применяется к тому, что осталось от строки после запуска runParser p1).
Пока у меня есть:
(Parser { runParser = run }) <*> (Parser { runParser = run' }) = Parser run''
where run'' s = (first <$> f) <*> (s' >>= run')
where f = fst <$> run s
s' = snd <$> run s
(first <$> f) <*> (s' >>= run') кажется мне довольно кратким, но вложенные where и странная деструктуризация run s выглядят «не так». Есть ли более приятный способ написать это?
Вы можете получить Applicative через StateT String Maybe, используя DerivingVia
Ответы 2
На мой взгляд, нет ничего постыдного в простоте, используя только базовое сопоставление с образцом, не слишком полагаясь на <*>, <$>, first и другие библиотечные функции.
Parser pF <*> Parser pX = Parser $ \s -> do
(f, s' ) <- pF s
(x, s'') <- pX s'
return (f x, s'')
Блок do выше находится в монаде Maybe.
Во-первых, позвольте мне немного переписать это, чтобы избежать сопоставления с образцом:
p <*> q = Parser run
where run s = (first <$> f) <*> (s' >>= runParser q)
where f = fst <$> runParser p s
s' = snd <$> runParser p s
Здесь я просто использовал метод доступа к полю runParser :: Parser a -> String -> Maybe (a, String) вместо прямого сопоставления с образцом для аргументов. Это считается более идиоматичным методом доступа к функциям newtyped в Haskell.
Далее, есть некоторые очевидные упрощения, которые можно сделать, в частности, встраивая некоторые функции:
p <*> q = Parser $ \s -> (first <$> f) <*> (s' >>= runParser q)
where
f = fst <$> runParser p s
s' = snd <$> runParser p s
(Обратите внимание, что s теперь нужно явно передать функциям в блоке where, чтобы они могли получить к нему доступ. Не волнуйтесь, я избавлюсь от этого через минуту.)
Одна запутанная вещь в этой реализации — это вложенные аппликативы и монады. Я немного перепишу этот раздел, чтобы сделать его более понятным:
p <*> q = Parser $ \s ->
let qResult = s' s >>= runParser q
in first <$> f s <*> qResult
where
f s = fst <$> runParser p s
s' s = snd <$> runParser p s
Далее, давайте избавимся от этих надоедливых определений f и s'. Мы можем сделать это, используя сопоставление с образцом. Путем сопоставления с образцом на выходе runParser p s мы можем получить прямой доступ к этим значениям:
p <*> q = Parser $ \s ->
case runParser p s of
Nothing -> Nothing
Just (f, s') ->
let qResult = runParser q s'
in first f <$> qOutput
(Обратите внимание, что, поскольку f и s' больше не находятся в Maybe, большая часть аппликативной и монадической сантехники, которая требовалась раньше, теперь не нужна. Один <$> все еще остается, поскольку runParser q s' все еще может выйти из строя).
Давайте немного перепишем это, встроив qResult:
p <*> q = Parser $ \s ->
case runParser p s of
Nothing -> Nothing
Just (f, s') -> first f <$> runParser q s'
Теперь обратите внимание на закономерность в этом коде. Это делает runParser p s, терпит неудачу, если это терпит неудачу; в противном случае он использует значение в другом вычислении, которое может завершиться ошибкой. Это просто звучит как монадическая последовательность! Итак, давайте перепишем это с помощью >>=:
p <*> q = Parser $ \s -> runParser p s >>= \(f, s') -> first f <$> runParser q s'
И, наконец, все это можно переписать в do-нотации для удобства чтения:
p <*> q = Parser $ \s -> do
(f, s') <- runParser p s
qResult <- runParser q s'
return $ first f qResult
Намного легче читать! И что делает эту версию особенно приятной, так это то, что легко увидеть, что происходит — запустить первый анализатор, получить его вывод и использовать его для запуска второго анализатора, а затем объединить результаты.
Отличный ответ, теперь я тоже, наконец, понимаю, для чего на самом деле хорош do.
@Peter Рад, что смог помочь! do действительно удивительно полезен, когда вы полностью понимаете, как это работает.
Небольшое примечание к стилю:
Parser { runParser = run }— довольно однозначный способ деструктурированияnewtype. Более привычным является просто вызовpили что-то в этом роде, а затем использованиеrunParser pдля доступа к функции внутри.