이미 Functor 인 데이터 유형에 대해 'Fix'를 사용하는 재귀 체계는 무엇입니까?

Question

내 텍스트 편집기 Rasa에서 계속 작업 중입니다.

현재 뷰포트/스플릿 (vim 스플릿과 유사) 추적 시스템을 구축 중입니다. 그것은 나무로이 구조를 표현하기 위해 나에게 자연 듯 : 이것은 위대한 작품을

data Dir = Hor 
     | Vert 
     deriving (Show) 

data Window a = 
    Split Dir SplitInfo (Window a) (Window a) 
    | Single ViewInfo a 
    deriving (Show, Functor, Traversable, Foldable) 

, 내가 나무에 내 View의를 저장하고 내가 그들을 그들을 변경하는 동안/fmap 함수 통과 할 수 있습니다, 그것은 또한과 일 맥상 꽤 잘 렌즈 패키지!

저는 최근에 Recursion Schemes에 대해 학습 해 왔으며 트리가 재귀 적 데이터 구조이기 때문에 적절한 유스 케이스 인 것처럼 보입니다.

은 내가 Fixpoint의 버전을 구축 충분히 알아낼 관리 : 지금 펑터 인스턴스가 r에 의해 사용된다 그러나

data WindowF a r = 
    Split Dir SplitInfo r r 
    | Single ViewInfo a 
    deriving (Show, Functor) 

type Window a = Fix (WindowF a) 

을;

나는

deriving instance Functor Window 

의 몇 가지 변화를 시도했다 그러나 창 유형의 동의어이기 때문에 초크.

그리고 :

newtype Window a = Window (Fix (WindowF a)) deriving Functor 

그리고 너무 실패;

• Couldn't match kind ‘* -> *’ with ‘*’ 
    arising from the first field of ‘Window’ (type ‘Fix (WindowF a)’) 
• When deriving the instance for (Functor Window) 

1. a을 통해 트래버스/fmap 함수를 정의하는 것은 여전히 ​​가능합니까? 아니면 recursion-schemes 프리미티브를 사용하여 이러한 작업을 수행해야합니까? Bifunctor를 구현합니까? 인스턴스 구현은 어떻게 생겼을까요? 유형의

나머지 here이다, 나는 윈도우에 대한 적절한 펑터 인스턴스를 가지고 있지 않기 때문에 컴파일되지 않습니다 프로젝트 ...

감사합니다!

Answer 1

내가 더 나은 선택은 두 가지 데이터 유형을 정의하는 것입니다 결론에 도달 한 레슬링의 많은 후에는; (이 경우 Bifunctor) 및 Base, Recursive 및 인스턴스를 정의 할 수있는 재귀 Functor 데이터 유형이있는 표준 데이터 유형입니다. 여기

는 예는 다음과 같습니다 이제 정상과 같은 코드를 통해 당신의 기본 유형 (BiTree)를 사용할 수 있습니다

{-# language DeriveFunctor, DeriveTraversable, TypeFamilies #-} 

import Data.Typeable 
import Data.Bifunctor 
import Data.Functor.Foldable 

data BiTree b l = 
    Branch b (BiTree b l) (BiTree b l) 
    | Leaf l 
    deriving (Show, Typeable, Functor, Traversable, Foldable) 

instance Bifunctor BiTree where 
    bimap _ g (Leaf x) = Leaf (g x) 
    bimap f g (Branch b l r) = Branch (f b) (bimap f g l) (bimap f g r) 

data BiTreeF b l r = 
    BranchF b r r 
    | LeafF l 
    deriving (Show, Functor, Typeable) 

type instance Base (BiTree a b) = BiTreeF a b 
instance Recursive (BiTree a b) where 
    project (Leaf x) = LeafF x 
    project (Branch s l r) = BranchF s l r 

instance Corecursive (BiTree a b) where 
    embed (BranchF sp x xs) = Branch sp x xs 
    embed (LeafF x) = Leaf x 

; 당신이 재귀 방식을 사용하기로 결정 때 당신은 단순히 포장을 풀 때 생성자의 'F'버전을 사용할 것을 기억해야합니다

이

anyActiveWindows :: Window -> Bool 
anyActiveWindows = cata alg 
    where alg (LeafF vw) = vw^.active 
     alg (BranchF _ l r) = l || r 

참고하면 창 세트를 재건 끝날 경우 당신은 여전히거야 그 =의 오른쪽에있는 NON-F 버전을 사용하십시오.

내 시나리오에 대해 다음을 정의했으며 효과가 좋습니다. 나는 심지어 newtype은을 사용하지 않고 원하는대로 나는 Window 모두 Functor 및 Bifunctor있어 :

type Window = BiTree Split View 

data SplitRule = 
    Percentage Double 
    | FromStart Int 
    | FromEnd Int 
    deriving (Show) 

data Dir = Hor 
     | Vert 
     deriving (Show) 

data Split = Split 
    { _dir :: Dir 
    , _splitRule :: SplitRule 
    } deriving (Show) 

makeLenses ''Split 

data View = View 
    { _active :: Bool 
    , _bufIndex :: Int 
    } deriving (Show) 

makeLenses ''View 

Answer 2

예, 당신은 Data.Bifunctor.Fix에서 Fix의 버전을 사용하려면 :

newtype Fix p a = In { out :: p (Fix p a) a } 

instance Bifunctor p => Functor (Fix p) where 
    fmap f (In x) = In (bimap (fmap f) f x) 

당신은 일치하도록 WindowF 유형을 변경해야합니다 :

data WindowF r a = 
    Split Dir SplitInfo r r 
    | Single ViewInfo a 
    deriving (Show, Functor) 

instance Bifunctor WindowF where 
    bimap f _g (Split dir si x y) = Split dir si (f x) (f y) 
    bimap _f g (Single vi a) = Single vi (g a) 

newtype Window a = Window (Fix WindowF a) deriving Functor 

그것은이 함께 recursion-schemes를 사용하는 것이 가능 , 보조 유형과 함께 :

불행하게도, newtype은 포장 된 버전 Recursive을 정의하는 것은 조금 까다 롭습니다 :

newtype Window a = Window {getWindow :: Fix WindowF a} deriving (Functor) 
type instance Base (Window a) = Flip WindowF a 

instance Recursive (Window a) where 
    project = coerce #. project .# getWindow 
    cata = (. getWindow) #. cata