Рекурсивные схемы, использующие `Fix` для типа данных, который уже является Functor?

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 с в дереве, а затем я могу траверсировать/БПМЖ над ними, чтобы изменить их, это также согласуется с объектив пакет довольно хорошо!

В последнее время я узнал о Recursion Schemes, и кажется, что это подходящий прецедент для них, поскольку дерево является рекурсивной структурой данных.

мне удалось понять это достаточно хорошо, чтобы построить из версии Fixpoint:

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

type Window a = Fix (WindowF a) 

Однако теперь экземпляр Functor используется вверх по r;

Я попробовал несколько вариантов

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? Или мне нужно делать эти операции с помощью примитивов recursion-schemes? Я использую Bifunctor? Как выглядит реализация экземпляра?

Остальные типов here, проект не компилируется, потому что не имеет надлежащий экземпляр Functor для Window ...

Спасибо !!

Answer 1

После много борьбы я пришел к выводу, что лучший выбором является определение двух типов данных; стандартный тип данных, который имеет нужные свойства (в данном случае Bifunctor) и тип данных рекурсивного функтора, для которого вы можете определить Base, Recursive и Corecursive экземпляров для.

Вот как это выглядит:

{-# 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 

Теперь вы можете использовать базовый тип (BiTree) на протяжении всего кода, как нормальный; и когда вы решили использовать схему рекурсии вам просто нужно помнить, что при распаковке вы использовать версии «F» конструкторах:

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

Обратите внимание, что если вы в конечном итоге восстановление набор окон вы будете по-прежнему используйте версии NON-F с правой стороны от =.

Я определил следующее для своего сценария, и он отлично работает; У меня как Functor и Bifunctor для Window как я хотел, даже используя NewType:

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

Да, вы хотите использовать версию Fix из Data.Bifunctor.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 с этим , а также вспомогательный тип:

import Data.Functor.Foldable hiding (Fix (..)) 
import Data.Profunctor.Unsafe 
import Data.Coerce 

newtype Flip p a b = Flip {unFlip :: p b a} 

instance Bifunctor p => Bifunctor (Flip p) where 
    bimap f g (Flip x) = Flip (bimap g f x) 

instance Bifunctor p => Functor (Flip p a) where 
    fmap = coerce (first :: (x -> y) -> p x a -> p y a) 
    :: forall x y . (x -> y) -> Flip p a x -> Flip p a y 

type instance Base (Fix p a) = Flip p a 
instance Bifunctor p => Recursive (Fix p a) where 
    project = Flip #. out 
    cata f = f . Flip . first (cata f) . out 

К сожалению, определение 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