Можно ли выразить chainl1 с помощью аппликативного? - PullRequest
6 голосов
/ 11 октября 2011

Можно ли выразить комбинатор 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

Ответы [ 2 ]

5 голосов
/ 11 октября 2011

Да, это:

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 на foldl.

0 голосов
/ 11 октября 2011

Гадкий, но эквивалентный 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).

...