Блог

Можно ли выразить chainl1 комбинатор из Parsec, не используя экземпляр Monad, определенный parsec?

 chainl1 p op =
  do x <- p
     rest x
  where
    rest x = do f <- op
                y <- p
                rest (f x y)
          <|> return x
  

Да, это так:

 chainl1 p op = foldl (flip ($)) <$> p <*> many (flip <$> op <*> p)
  

Идея в том, что вы должны проанализировать p (op p)* и оценить его как (...(((p) op p) op p)...) .

Это может помочь немного расширить определение:

 chainl1 p op = foldl (x f -> f x) <$> p <*> many ((f y -> flip f y) <$> op <*> p)
  

Поскольку пары op и p анализируются, результаты применяются немедленно, но поскольку p это правильный операнд op , ему нужен flip .

Итак, тип результата many (flip <$> op <*> p) f [a -> a] равен . Затем этот список функций применяется слева направо к начальному значению p by foldl .

Уродливое, но эквивалентное Applicative определение:

 chainl1 p op =
    p <**>
    rest
  where
    rest = flip <$> op <*>
           p <**>
           pure (.) <*> rest
        <|> pure id
  

Вместо явной передачи аргумента левой стороны x в правую часть op , эта аппликативная форма «цепочки op » частично применяется к их аргументу правой стороны (следовательно flip <$> op <*> p ) через поднятый комбинатор (.) , а затем применяет крайний левый p путь (<**>) к результату rest :: Alternative f => f (a -> a) .