이 점진적인 파서가 펑터인가, 만약 그렇다면`fmap`은 어떻게 구현 될까?

Question

나는 이런 종류의 질문을하는 것을 정말로 싫어하지만 나는 나의 지혜의 끝 부분에있다. 나는 점진적인 파서를 쓰고 있지만 어떤 이유로 펑터 인스턴스를 구현하는 방법을 알 수 없다.

입력이 코 루틴에 파서에 의해 산출 된 데이터 유형입니다

입력 데이터 형식 : 여기에 코드 덤프입니다. 그것은 입력 문자의 현재 목록

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

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

출력 데이터 타입

출력 파서를 코 루틴에 의해 산출 된 데이터 타입 코 루틴 및 광고 조건 단부에 의해 동작되는 것을 포함한다. 그것은 인 하나 완료 실패한 메시지, [B], 또는 부분 ([A] -> 출력 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]를 취하고

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

펑터 구현

,174 AB 출력을 다시 산출 버퍼 [A] 동시 루틴을 수득

내가 다음과 같은 코 루틴 위에 함수 g를 fmap 함수입니다해야 할 모든 것 같습니다 :

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

를하지만 확인 입력하지 않습니다 필립 JF 선언으로

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 

Answer 1

, 그것은 아니다 instance Functor (ParserI a) 일 수 있습니다. 증명은 펑터의 분산에 의해 진행됩니다. 모든 (수학적) 펑 터는 각 인수에 대해 공변 또는 반 차별이어야합니다. 일반 하스켈 Functor들

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

하스켈 Contravariant functors이 경우 유사한

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

이 이유입니다 항상 공변 있으며, ParserI a b에서 b 지수는 공변 및 contravariant 모두를 할 것이다. 이것을 알아내는 빠른 방법은 공역 위치를 +으로, 반의어를 -으로 바꾸고 몇 가지 기본 규칙을 만드는 것입니다.

공변 위치는 함수 결과이고, 반공립 값은 함수 입력입니다. 따라서 type Func1 a b c = (a, b) -> c과 같은 유형 매핑은 a ~ -, b ~ - 및 c ~ +입니다. 출력 위치에 함수이있는 경우 모든 인수 분산에 +1을 곱합니다. 입력이 위치에있는 경우 모든 분산을 -1으로 곱합니다.

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

가 a ~ 1, b ~ -1 및 c ~ 1을 갖는다 Func1로하지만

따라서

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

동일한 차이를 갖는다. 이 규칙을 사용하면 Output에 Output - +과 같은 차이가 있고 ParserI은 Output을 음수 및 양수 위치에서 모두 사용하므로 곧바로 Functor이 될 수 없습니다.

---

그러나 Contravariant과 같은 일반화가 있습니다. 관심의 특정 일반화 Profunctor (또는 가끔 볼 Difunctor들) 그래서

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 s f은 항상 분산 기호 f - + 인 아리 티 2의 수학적 펑터입니다.

따라서 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 

을 통해 약간 덜 편리한 매핑 기능을 제공 할 수 있습니다 방법 --- 양방향지도가 필요합니다!