5

この種の質問をするのは本当に嫌いですが、ここで知恵が尽きてしまいました。インクリメンタルパーサーを書いていますが、何らかの理由でファンクターインスタンスを実装する方法がわかりません。コードダンプは次のとおりです。

入力データ型

入力は、パーサーによってコルーチンに生成されたデータ型です。コルーチンと行末条件によって操作されている入力文字の現在のリストが含まれています

data Input a = S [a] Bool deriving (Show)

instance Functor Input where
    fmap g (S as x) = S (g <$> as) x

出力データ型

出力は、コルーチンによってパーサーに生成されるデータ型です。これは、Failed メッセージ、Done [b]、または Partial ([a] -> Output ab) のいずれかです。ここで、[a] はパーサーに戻された現在のバッファーです。

data Output a b = Fail String | Done [b] | Partial ([a] -> Output a b)

instance Functor (Output a) where
    fmap _ (Fail s)    = Fail s
    fmap g (Done bs)   = Done $ g <$> bs
    fmap g (Partial f) = Partial $ \as -> g <$> f as

パーサー

パーサーは [a] を受け取り、バッファー [a] をコルーチンに生成します。コルーチンは出力 ab を返します。

data ParserI a b = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b }

ファンクターの実装

次のように、関数 g をコルーチンに fmap するだけでよいようです。

instance Functor (ParserI a) where
    fmap g p = PP $ \as k -> runPi p as (\xs -> fmap g $ k xs)

しかし、それはチェックをタイプしません:

Couldn't match type `a1' with `b'
  `a1' is a rigid type variable bound by
       the type signature for
         fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b
       at Tests.hs:723:9
  `b' is a rigid type variable bound by
      the type signature for
        fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b
      at Tests.hs:723:9
Expected type: ParserI a b
  Actual type: ParserI a a1
4

1 に答える 1

11

Philip JF が宣言したように、instance Functor (ParserI a). 証明はファンクターの分散によって行われます — (数学的) ファンクターは、その引数のそれぞれについて、共変または反変のいずれかでなければなりません。通常の HaskellFunctorは常に共変であるため、

fmap :: (a -> b) -> (f a -> f b)`

HaskellのContravariantファンクタには、似たようなものがあります

contramap :: (b -> a) -> (f a -> f b)`

あなたの場合、bインデックスはParserI a b共変と反変の両方である必要があります。これを理解する簡単な方法は、共変の位置をいくつかの基本的なルールに関連付け、反変の位置を関連付けて構築すること+です。-

共変の位置は関数の結果であり、反変の位置は関数の入力です。したがって、type Func1 a b c = (a, b) -> chas a ~ -、b ~ -、およびのような型マッピングc ~ +。出力位置に関数がある場合は、すべての引数の分散に を掛けます+1。入力位置に関数がある場合は、すべての分散に を掛けます-1。したがって

type Func2 a b c = a -> (b -> c)

と同じ分散がありますFunc1が、

type Func3 a b c = (a -> b) -> c

a ~ 1、b ~ -1、およびがありc ~ 1ます。Outputこれらのルールを使用すると、のような分散があり、 が負の位置と正の位置の両方で使用されていることがOutput - +すぐにParserIわかります。OutputFunctor

しかし、 のような一般化がありContravariantます。関心のある特定の一般化はProfunctor(またはDifunctor時々見られる s) であり、次のようになります。

class Profunctor f where
  promap :: (a' -> a) -> (b -> b') -> (f a b -> f a' b')

その典型的な例は(->)

instance Profunctor (->) where
  promap f g orig = g . orig . f

Functorつまり、(通常のように) 後と前の両方で関数を「拡張」します。Profunctorしたがって、 sfは常にアリティ 2 の数学的関手であり、分散シグニチャ がありf - +ます。

したがって、ParserI少し一般化して、出力タイプを半分に分割する追加のパラメーターを存在させることで、それを にすることができますProfunctor。

data ParserIC a b b' = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b' }

instance Profunctor (ParserIC a) where
  promap before after (PP pi) = 
    PP $ \as k -> fmap after $ pi as (fmap before . k)

そして、あなたはそれをまとめることができます

type ParserI a b = ParserIC a b b

やや不便なマッピング機能を提供しますb

mapPi :: (c -> b) -> (b -> c) -> ParserI a b -> ParserI a c
mapPi = promap

これは、分散が双方向になるという負担を本当に痛感させます---双方向のマップが必要です!

于 2013-07-19T04:57:05.523 に答える