haskell - 哪种代数模式适合这种类型的树？

Question

我有一个谜题给你

我设法编写了一些代码来使用递归方案来做这些事情，但它非常困惑
这通常意味着我在某处错过了有用的抽象。

我正在为我的文本编辑器设计一个布局系统
Rasa ;它以非常相似的方式使用拆分
方式作为 Vim。我决定用一棵树来描述 split ；你可以想象
它作为垂直或水平分割的二叉树，在
叶节点。 Thispicture
可能有帮助。

这是我的初始数据结构:

data Direction = Hor | Vert
data Tree a = 
  Branch Direction (Tree a) (Tree a)
  | Leaf a
  deriving (Functor)

我需要的一些操作是:

split :: (View -> Tree View) -> Tree View -> Tree View将节点(或不)水平或垂直拆分为两个节点(同时保持它们在
树)

close :: (View -> Bool) -> Tree View -> Tree View通过删除“关闭”与谓词匹配的任何 View
他们从树中正确地重新组织相邻的 View 。

fmap ;我希望树是一个仿函数，这样我就可以改变 View 。

一些不错的功能:
- focusRight :: Tree View -> Tree View , 当且仅当最近的水平连接 View 设置为事件 View
左侧 View 处于事件状态

我正在寻找一个抽象或一组抽象来提供这个
以简洁的方式实现功能。到目前为止，这是我的思考过程:

起初我以为我有一个 Monoid，身份是空树，而 mappend只会将另一个分支附加到树上，但这不起作用
因为我有两个操作:垂直追加和水平追加以及操作
当它们混合在一起时不具有关联性。

接下来我想“我的一些操作取决于它们的上下文”，所以我可能有一个 Comonad。树的版本
我没有作为联合单子(monad)工作，因为我没有 extract 的值(value)在一个分支上，所以我重组了我的树
像这样:

data Tree a = Node Direction [Tree a] a [Tree a]
    deriving (Functor)

但这仍然
没有处理根据节点内部的内容“拆分”节点的情况，这与签名 (View -> Tree View) ->
Tree View -> Tree View 匹配, 与 bind 统一来自 Monad，所以也许我有一个 monad？我可以为
原始树定义，但无法为我的 Comonad 树版本弄清楚。

有什么方法可以让我在这里两全其美吗？我是不是用 Comonad/Monad 挖错了树？
基本上，我正在寻找一种优雅的方法来在我的数据结构上对这些函数进行建模。谢谢!

如果想看完整代码，函数是 here并且当前树是 here .

Answer 1

我放弃了将其塞进评论中的尝试。 Conor McBride有一整条talk和 Sam Lindley 一起，一大块 paper ，所有关于使用 monad 来划分 2D 空间。既然你要求一个优雅的解决方案，我觉得有必要给你一个关于他们工作的总结，尽管我不一定建议将它构建到你的代码库中 - 我怀疑使用像 boxes 这样的库可能更简单。并通过手动错误处理手动启动剪切和调整大小逻辑。

您的第一个 Tree是朝着正确方向迈出的一步。我们可以写一个 Monad将树木嫁接在一起的实例:

instance Monad Tree where
    return = Leaf
    Leaf x >>= f = f x
    Branch d l r >>= f = Branch d (l >>= f) (r >>= f)

Tree 's join 拿一棵树，叶子上有树，让你一路走到底部，中途不停下来呼吸。想想 Tree 可能会有所帮助作为 free monad ，正如@danidiaz 在 an answer 中所示.或 Kmett might say你有一个非常简单的语法允许术语替换其 Var被称为 Leaf .

无论如何，关键是你可以使用 >>=通过逐渐砍掉树叶来种植树木。这里我有一个一维 UI(让我们暂时忘记 Direction)，其中有一个包含 String 的窗口。 ，通过反复将其切成两半，我最终得到了八个较小的窗口。

halve :: [a] -> Tree [a]
halve xs = let (l, r) = splitAt (length xs `div` 2) xs
         in Node (Leaf l) (Leaf r)

ghci> let myT = Leaf "completeshambles"
-- |completeshambles|
ghci> myT >>= halve
Node (Leaf "complete") (Leaf "shambles")
-- |complete|shambles|
ghci> myT >>= halve >>= halve
Node (Node (Leaf "comp") (Leaf "lete")) (Node (Leaf "sham") (Leaf "bles"))
-- |comp|lete|sham|bles|
ghci> myT >>= halve >>= halve >>= halve
Node (Node (Node (Leaf "co") (Leaf "mp")) (Node (Leaf "le") (Leaf "te"))) (Node (Node (Leaf "sh") (Leaf "am")) (Node (Leaf "bl") (Leaf "es")))
-- |co|mp|le|te|sh|am|bl|es|

(在现实生活中，您可能一次只剪切一个窗口，方法是在绑定(bind)函数中检查其 ID，如果它不是您要查找的窗口，则将其原封不动地返回。)

问题是， Tree不了解物理空间是一种有限且宝贵的资源。 fmap让您更换 a s 与 b s，但如果 b，生成的结构将无法显示在屏幕上s 比 a 占用更多空间做了!

ghci> fmap ("in" ++) myT
Leaf "incompleteshambles"

这在两个维度上变得更加严重，因为盒子可以相互插入并撕裂。如果中间窗口被意外调整大小，我会在中间得到一个畸形的盒子或一个洞(取决于它在树中的下落)。

+-+-+-+         +-+-+-+            +-+-+  +-+
| | | |         | | | |            | | |  | |
+-+-+-+         +-+-+-++-+   or,   +-+-+--+-+
| | | |  ---->  | |    | | perhaps | |    | |
+-+-+-+         +-+-+-++-+         +-+-+--+-+
| | | |         | | | |            | | |  | |
+-+-+-+         +-+-+-+            +-+-+  +-+

扩大 window 是一件非常合理的事情，但在现实世界中，它扩大到的空间必须来自某个地方。你不能在不缩小另一个窗口的情况下增加一个窗口，反之亦然。这不是可以用 >>= 完成的操作。 , 在单个叶节点执行局部替换；你需要查看一个窗口的兄弟节点才能知道谁占用了它相邻的空间。

所以你不应该被允许使用 >>=像这样调整内容的大小。 Lindley 和 McBride 的想法是教类型检查器如何将框对齐。使用类型级自然数和加法，

data Nat = Z | S Nat
type family n :+ m where
    Z :+ m = m
    S n :+ m = S (n :+ m)

它们处理按宽度和高度索引的内容。 (在论文中，他们使用表示为向量向量的 2D 矩阵，但为了提高效率，您可能希望使用具有 phantom 类型的数组来测量其大小。)

a, Box a :: (Nat, Nat) -> *
-- so Box :: ((Nat, Nat) -> *) -> (Nat, Nat) -> *

使用 Hor 并排放置两个盒子要求它们具有相同的高度，并使用 Ver 将它们放在彼此之上要求它们具有相同的宽度。

data Box a wh where
    Content :: a '(w, h) -> Box a '(w, h)
    Hor :: Box a '(w1, h) -> Box a '(w2, h) -> Box a '(w1 :+ w2, h)
    Ver :: Box a '(w, h1) -> Box a '(w, h2) -> Box a '(w, h1 :+ h2)

现在我们准备构建一个 monad 来将这些树嫁接在一起。 return的语义没有改变 - 它把一个 2D 对象放在 Box 中在其自己的。

return :: a wh -> Box a wh
return = Content

现在让我们想想 >>= .一般来说，一个盒子是由许多件 Content组成的。大小不一，以某种方式组合以产生更大的盒子。下面我有三块大小为 2x1、2x2 和 1x3 的内容组成了一个 3x3 的盒子。这个框看起来像 Hor (Ver (Content 2x1) (Content 2x2)) Content 1x3 .

 2x1
+--+-+
|  | |
+--+ |1x3
|  | |
|  | |
+--+-+
 2x2

而你， >>=的来电者，知道你的盒子的外部尺寸，你不知道组成它的各个内容块的尺寸。当你用 >>= 切割时，你怎么能期望保留内容的大小？ ?您必须编写一个函数来保留大小，而无需事先了解大小。

所以 >>=需要一个 Box已知大小 wh ，将其拆开以查找内容，使用保留您提供给它的内容的(未知)大小的函数对其进行处理*，然后将其重新组合在一起以生成具有相同大小的新框 wh .注意 rank-2 类型，反射(reflect)了 >>= 的调用者的事实。无法控制将调用延续的内容的维度。

(>>=) :: Box a wh -> (forall wh2. a wh2 -> Box b wh2) -> Box b wh
Content x >>= f = f x
Hor l r >>= f = Hor (l >>= f) (r >>= f)
Ver t b >>= f = Ver (t >>= f) (b >>= f)

如果您使用类型同义词 ~>对于保留索引的函数并翻转参数，你会得到类似 =<< 的东西。普通 Monad s，但带有不同类型的箭头。 Kleisli 的作品看起来也很漂亮。

type a ~> b = forall x. a x -> b x

return :: a ~> Box a
(=<<) :: (a ~> Box b) -> (Box a ~> Box b)
(>=>) :: (a ~> Box b) -> (b ~> Box c) -> (a ~> Box c)

所以这是索引集上的单子(monad)。 (更多在 Kleisli Arrows of Outrageous Fortune 中。)在 the paper他们构建了更多基础设施来支持裁剪和重新排列框，这可能对您构建 UI 很有用。为了提高效率，您可能还决定使用 zipper 跟踪当前聚焦的窗口。 ，这是一个有趣的练习。顺便说一句，我认为 Hasochism 是对一般花式类型的一个很好的介绍，而不仅仅是这个特定问题的解决方案。

*假设 a的索引确实是对其物理大小的准确度量