在已经是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)

效果很好，我将Views 存储在树中，然后可以在它们上遍历/ fmap来更改它们，这也与镜头包很好地吻合！

我最近一直在学习递归方案，这似乎是一个合适的用例，因为树是递归的数据结构。

我设法弄清楚了，以构建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

但是它很令人吃惊，因为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. 还有可能定义fmap / traverse over a吗？还是我需要使用递归方案原语进行这些操作？我要实现Bifunctor吗？实例实现是什么样的？

其他类型在这里，项目无法编译，因为我没有适用于Window的适当的Functor实例...

谢谢！！

Answer 1

经过一番努力，我得出的结论是，更好的选择是定义两种数据类型；Base具有您想要的属性的标准数据类型（在本例中为 Bifunctor）和您可以为其定义和实例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

请注意，如果您最终重建一组窗口，您仍将使用=.

我已经为我的场景定义了以下内容，效果很好；我已经得到了我想要的Functor和Bifunctorfor Window，甚至没有使用新类型：

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