10

Applicativeこのパーサーのインスタンスを実装する方法がわかりません:

newtype Parser m s a = Parser { getParser :: [s] -> m ([s], a) }

想定せずにMonad m。インスタンスは を想定するだけApplicative mでよいので、を想定するだけでよいと思っていました。私は最終的に次のようになりました：FunctorFunctor m

instance Functor m => Functor (Parser m s) where
  fmap f (Parser g) = Parser (fmap (fmap f) . g)


instance Monad m => Applicative (Parser m s) where
  pure a = Parser (\xs -> pure (xs, a))

  Parser f <*> Parser x = Parser h
    where
      h xs = f xs >>= \(ys, f') -> 
        x ys >>= \(zs, x') ->
        pure (zs, f' x')

どうすればいいですか？for を手で代用しよう>>=としましたが、 a -- を減らそうとしていつも行き詰まりました。joinこれには も必要ですMonad。

Parsecにも相談しましたが、それでもあまり役に立ちませんでした。

instance Applicative.Applicative (ParsecT s u m) where
    pure = return
    (<*>) = ap

この質問をする理由は、純粋に独学です。

4

2 に答える 2

12

不可能です。あなたの内部を見てくださいnewtype：

getParser :: [s] -> m ([s], a)

おそらく、 in[s]の入力に渡したいと思います。これはまさにとの違いです:yx <*> yMonad mApplicative m

  • ではMonad、ある計算の出力を別の計算の入力として使用できます。
  • ではApplicative、できません。

面白いトリックをすれば可能です：

Parser x <*> Parser y = Parser $
    \s -> (\(_, xv) (s', yv) -> (s', xv yv)) <$> x s <*> y s

ただし、これはほとんどの場合、必要な定義ではありません。これは、並列で解析xさyれるためです。

修正

  1. あなたParserTはApplicative非常に簡単にできます：

    newtype ParserT m s a = ParserT { runParser :: [s] -> m ([s], a) }
-- or, equvalently
newtype ParserT m s a = ParserT (StateT [s] m a)

instance Monad m => Applicative (ParserT m s) where
    ...

    インスタンスを定義しない限り、 のインスタンスでParserT m sはないことに注意してください。MonadMonad

  2. 残りの文字をパーサーの外に移動できます。

    newtype ParserT m s a = ParserT { runParser :: [s] -> ([s], m a) }

instance Applicative m => Applicative (ParserT m s) where
    ParserT x <*> ParserT y = ParserT $ \s ->
        let (s', x') = x s
            (s'', y') = y s'
        in x' <*> y'
    ...
于 2012-10-31T20:13:01.700 に答える
3

可能な限り Applicative を使用することを目指すための満点 - はるかにクリーンです。

見出し:パーサーは Applicative のままでもかまいませんが、可能性のある解析のコレクションは Monad に格納する必要があります。内部構造：モナドを使用。外部構造: 適用可能です。

m ([s],a)可能な解析の束を表すために使用しています。次の入力を解析するときは、既に解析されているものに依存する必要がありますがm、可能な解析が 1 つより少ないか複数ある可能性があるため、使用しています。あなたがやりたいと思って\([s],a) -> ...、それを使って新しいm ([s],a). そのプロセスはバインディングと呼ばれ、>>=または同等のものを使用するため、コンテナーは間違いなくモナドであり、エスケープはありません。

コンテナーにモナドを使用することは、それほど悪いことではありません。結局のところ、モナドは何かを保持しているコンテナーにすぎません。内部でモナドを使用することとモナドであることには違いがあります。内部でモナドを使用している間、パーサーは適用可能です。

モナド構文解析に対するアプリケーション構文解析の利点は何ですか? を参照してください。.

パーサーが適用可能である場合、それらはより単純であるため、理論的には、それらを組み合わせるときに、実装を保持する代わりに、パーサーが行うことに関する静的情報を保持することにより、いくつかの最適化を行うことができます。例えば、

string "Hello World!" <|> string "Hello Mum!"
== (++) <$> string "Hello " <*> (string "World" <|> string "Mum!")

2 番目のバージョンは、バックトラッキングを行わないため、最初のバージョンよりも優れています。

これをたくさん行うと、正規表現が実行前にコンパイルされ、グラフ (有限状態オートマトン) が作成され、それが可能な限り単純化され、非効率的なバックトラッキングの負荷全体が排除されるようになります。

于 2012-11-01T11:14:01.053 に答える