중요하지 않은 표현 유형에 대해 MuRef 인스턴스를 정의하는 방법은 무엇입니까?

Question

장난감 임베디드 언어를 고려

data Expr = 
    App Expr Expr 
    | Lam Pat Expr 
    | Case Expr [(Pat, Expr)] 

내가 data-reify를 사용하여 Expr 표현에서 암시 적 공유를 관찰합니다. MuRef 클래스

data ExprF e = 
    AppF e e 
    | LamF Pat e 
    | Case e [(Pat, e)] 

및 인스턴스 :이를 위해, 나는 프록시 노드를 그래프로 해당 형식이 필요합니다. 나는 App 및 Lam 생성자에 쉽게 mapDeRef에 대한 정의를 제공 할 수 있습니다,하지만 난 Case에 해당하는 정의를 처리하는 방법을 잘 모르겠어요 :

instance MuRef Expr where 
    type DeRef Expr = ExprF 
    mapDeRef f (App e0 e1) = AppF <$> f e0 <*> f e1 
    mapDeRef f (Lam p e) = LamF p <$> f e 
    mapDeRef f (Case e pes) = Case <$> f e <*> ? 

this question에 대한 답변으로 판단, 그것은 수도 그것과 같다 ExprF에 MuRef 인스턴스에 (Pat, Expr) 및 [(Pat, Expr)]과 같은 몇 가지 영리한 생성자를 추가하여이 문제를 해결할 수 있습니다. 나는 시도한다 :

data ExprF e = 
    AppF e e 
    | LamF Pat e 
    | Pair (Pat, e) 
    | CaseF e [(Pat, e)] 
    | Cons e e 
    | Nil 

instance MuRef (Pat, Expr) where 
    type DeRef (Pat, Expr) = ExprF 
    mapDeRef f (p, e)  = Pair <$> ((,) <$> pure p <*> f e) 

instance MuRef [(Pat, Expr)] where 
    type DeRef [(Pat, Expr)] = ExprF 
    mapDeRef _ []   = pure Nil 
    mapDeRef f (pe:pes)  = Cons <$> f pe <*> f pes 

그러나이 운이가 Case 바인딩 원래 mapDeRef에 온다 :

instance MuRef Expr where 
    ... 
    mapDeRef f (Case e pes) = Case <$> f e <*> f pes 

Could not deduce (u ~ [(Pat, u)]) 
from the context (Applicative f) 
    bound by the type signature for 
      mapDeRef :: Applicative f => 
         (forall b. (MuRef b, DeRef Expr ~ DeRef b) => b -> f u) 
         -> Expr -> f (DeRef Expr u) 

그것은 Case 패턴을 제대로 mapDeRef을 정의 할 수 있습니까? 간과 할 간단한 것이 있습니까?

Answer 1

인스턴스는 원래의 유형에 대해 정의 할 수 있습니다

:

{-# LANGUAGE TypeFamilies, TupleSections #-} 

import qualified Data.Traversable as T 
import Data.Reify 
import Control.Applicative 

data Expr = 
    App Expr Expr 
    | Lam Pat Expr 
    | Case Expr [(Pat, Expr)] 

data ExprF e = 
    AppF e e 
    | LamF Pat e 
    | CaseF e [(Pat, e)] 

data Pat -- placeholder 

instance MuRef Expr where 
    type DeRef Expr = ExprF 
    mapDeRef f (App e0 e1) = AppF <$> f e0 <*> f e1 
    mapDeRef f (Lam p e) = LamF p <$> f e 
    mapDeRef f (Case e pes) = CaseF <$> f e <*> T.traverse (\(pat, exp) -> (pat,) <$> f exp) pes 

난, 난 그냥 유형의 다음 인스턴스 정의에 작성 Data.Reify에 익숙하지 않다, 그래서 의미가 해당됩니다 있는지 확실하지 않습니다 여기에 원하는대로. 하지만 그 인스턴스는 확실히 할 수 있습니다.

사이드 참고 : lens 구현을 사용하여 정말 분명해진다 : 당신은`CaseF`에`CaseF 전자 e`를 변경하는 경우

import Control.Lens 
-- code omitted 
mapDeRef f (Case e pes) = CaseF <$> f e <*> (traverse . _2) f pes