6

Is it possible to express the chainl1 combinator from Parsec not using the Monad instance defined by parsec?

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

2 に答える 2

5

はい、そうです：

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ます。

于 2011-10-10T23:39:32.373 に答える
0

醜いが同等のApplicative定義：

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

左側の引数をx明示的に右側に渡す代わりにop、この Applicative 形式 'chains'は、持ち上げられたコンビネータを介しopて右側の引数 (したがって ) に部分的に適用され、次に一番左のビアを結果の に適用します。flip <$> op <*> p(.)p(<**>)rest :: Alternative f => f (a -> a)

于 2011-10-11T12:30:06.043 に答える