1

教育上の理由から、Parsecと同様の機能を実装しています。動機は、モナドマジックを使用せずに、ファンクター、アプリケーション、およびオルタナティブインスタンスを定義することです。FunctorとApplicativeのインスタンスは問題ありません。ただし、Alternativeで定義する<|>と、髪がほつれます。

newtype Parser t = Parser (String -> [(t, String)])

parse (Parser p) s = p s

instance Functor ....
instance Applicative ....

empty1 = Parser $ \s -> []

orp :: Parser t -> Parser t -> Parser t
-- orp :: (Eq t) => Parser t -> Parser t -> Parser t  -- this works too
p1 `orp` p2 = Parser $ \s -> let p1out = parse p1 s
                                 e     = parse empty1 s
                             in
                              if p1out == e
                              then parse p2 s
                              else p1out     

{- 
instance Alternative Parser where
  empty = Parser $ \s -> []

  (<|>) = orp -- fails to compile
-}

ghcは、orp`の署名Eqに追加しても、コンテキストから推測できないと文句を言います。Eq明らかに、インスタンス宣言に署名を追加して、それを適切に動作させることはできません。単相制限は役に立ちませんでした。多分私はそれがすべてをよく理解していない。

私は何が欠けていますか？実存的なタイプを探求する必要がありますか？それとも私は根本的な間違いを犯していますか？それともこれは不可能ですか？

4

2 に答える 2

4

を使用して空のリストと比較する代わりに、(==)パターンマッチする必要があります

orp :: Parser t -> Parser t -> Parser t
orp p1 p2 = Parser $ \s ->
    case parse p1 s of
      [] -> parse p2 s
      xs -> xs

型クラスの制約なしで同じ動作を実現するため、インスタンス宣言で使用できます。

于 2012-07-27T10:36:09.077 に答える
2

Daniel Fischer さんは具体的な修正を提案しました。抽象的な修正を提案したいと思います。その過程で、あなたがここで行ったことに気付いていないかもしれない設計上の決定を明らかにします (そして、あなたが間違った決定をしたことを主張します)。

Applicative functor が構成することはよく知られています。他の多くの種類のファンクターのペアリングが構成されることは、あまり知られていません (確かに私が発明したものではありません)。特に、代替ファンクターは、新しい代替ファンクターを生成するために、両側のファンクターと合成します。以下では、Haskell 構文を使用して、私の意味を説明します。私は無効なHaskell を書きます --混乱を避けるためtypeに代わりにnewtypeどこでも使用するためです -- しかし、後で有効な Haskell を導出するために無効な Haskell を使用します。

type (f :. g) a = f (g a) -- like in TypeCompose

-- (1)
instance (Applicative f, Alternative g) => Alternative (f :. g) where
    empty = pure empty
    x <|> y = liftA2 (<|>) x y

-- (2)
instance Alternative f => Alternative (f :. g) where
    empty = empty
    x <|> y = x <|> y

(これらのインスタンスは、非常に多く重複しています。)

意味的には、タイプを一連のタイプ合成として見ることができます:

-- (3)
type Parser = (String ->) :. [] :. (String,)

...ここで(String ->)、Applicative(4)[]のインスタンスであり、Alternative(5) のインスタンスであることがわかります。Alternativeこれは、上記のインスタンスとのセマンティック定義を結合することにより、 this からインスタンスを「読み取る」ことができるはずであることを意味Parserします。

empty :: Parser t
= -- (3)
empty :: (String ->) :. [] :. (String,)
= -- (1)
pure (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,))
= -- (4)
const (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,))
= -- (2) to use []'s empty rather than [] :. (String,)'s empty
const (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,))
= -- (5)
const [] :: (String ->) :. ([] :. (String,))

p <|> q :: Parser t -> Parser t -> Parser t
= -- (3)
p <|> q :: ... -> ... -> ((String ->) :. [] :. (String,))
= -- (1)
liftA2 (<|>) p q
= -- (4)
\s -> p s <|> q s
= -- (2) to use []'s <|> rather than [] :. (String,)'s <|>
\s -> p s <|> q s
= -- (5)
\s -> p s ++ q s

したがって、意味的には、 sに対して現在どのように動作しemptyたいのか、どのように動作するのかを知っています。残りの唯一のトリックは、適切な newtype コンストラクターとデコンストラクターをすべて追加することです。<|>Parser

instance Alternative Parser where
    empty = Parser (const [])
    Parser p <|> Parser q = Parser (\s -> p s ++ q s)

または、エキサイティングだと感じた場合は、よりオーバーロードされた構文で同じことを書くことができます。

instance Alternative Parser where
    empty = Parser (pure empty)
    Parser p <|> Parser q = Parser (liftA2 (<|>) p q)

のこの実装は、(<|>)実際には常にq!からのすべての結果を返すことに注意してください。あなたの定義では、失敗qしたときにのみパースを返すようになります。pこれは特に、成功した解析のリストが左寄りになることを意味します。上記のセマンティック駆動型の実装には、そのような偏りはありません。たとえ a の左側が(<|>)解析されたとしても、右側もその勝利について伝えることができます。そして、これは非常に自然なことだと思います。つまり、このインターフェースで構築されたパーサーは、成功したすべての解析を返すということです。

実際の違いは何ですか？上記のセマンティック定義はより堅牢であり、提案した定義はより効率的です。最初に「より堅牢」とは何かを見てみましょう。

常に正確に 1 文字を消費するパーサーを考えてみましょう (何を返すかは、この議論では重要ではありません)。

oneChar = Parser (\s -> case s of
    c:cs -> [((),cs)]
    _    -> [])

...そして、文字を消費せずに常に成功するパーサー:

epsilon = Parser (\s -> [((),s)]) -- you might recognize this as "pure ()"

では、このように 1 文字または 2 文字のパーサーを構成するとどうなるでしょうか。

oneOrTwo = (oneChar <|> epsilon) <* oneChar

oneOrTwoを使用して解析することを検討してください"a"。の定義により(<|>)、最初の部分はビットを解析するoneChar <|> epsilonために使用しようとしますoneCharが、これは成功するため、 は実行されずepsilon、 のような解析のリストが得られ[((),"")]ます。しかし、今度は 2 番目の部分が失敗します。解析する文字が 1 つも残っていません。の私の定義では、最初の部分は代わりに と の両方を(<|>)実行する両方の解析を試み、のような解析のリストを取得します。2 番目の部分は、そのリストの最初の要素で失敗しますが、2 番目の要素で成功し、解析全体が成功します。oneCharepsilon[((),""),((),"a")]

一方、定義は 2 つの理由でより効率的になる可能性があります。1 つ目は、入力の初期部分をより早く破棄できる (ガベージ コレクションとの相互作用が向上する) ことです。2 つ目は、バックトラッキング検索空間の大部分を削除できることです。 (検索に費やされるサイクルが少なくなります)。

このトレードオフはよく知られています。たとえば、Parsecは、 tryコンビネータを介して、your kind の代替 (入力が消費された場合に最初の引数にコミットする) と my kind (バックトラッキングを行う) の両方を提供します。

于 2012-07-27T19:02:02.037 に答える