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

Question

我有一个谜题,

我设法编写了一些使用递归方案来做这些事情的代码,但它非常混乱,这通常意味着我在某个地方错过了一个有用的抽象.

我正在为我的文本编辑器设计一个布局系统 Rasa; 它使用与Vim非常相似的方式进行拆分.我决定使用树来描述分裂; 您可以将它想象为垂直或水平分割的二叉树,在叶节点处具有"视图".这张照片 可能有帮助.

这是我的初始数据结构:

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 通过从树中删除它们并正确地重新组织相邻视图来"关闭"与谓词匹配的任何视图.
• fmap; 我希望树能成为一个仿函数,所以我可以改变观点.

一些很好的功能: - focusRight :: Tree View -> Tree View,当且仅当左边最近的水平连接视图WAS处于活动状态时,才将视图设置为活动状态

我正在寻找一个抽象或一组抽象,以一种干净的方式提供这种功能.到目前为止,这是我的思考过程:

起初我以为我有一个Monoid,标识是空树, mappend只是将另一个分支附加到树上,但这不起作用,因为我有两个操作:垂直追加和水平追加,操作不是关联的当他们混在一起的时候.

接下来我想'我的一些操作取决于他们的背景'所以我可能有一个Comonad.我拥有的树的版本不能作为共同monad工作,因为我没有extract分支上的值,所以我重构了我的树,如下所示:

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

但是这仍然没有处理根据里面的东西"拆分"节点的情况,这与签名相匹配(View -> Tree View) -> Tree View -> Tree View,这与bindMonad 统一,所以也许我有一个monad？我可以为原始的Tree定义实现monad,但无法弄清楚我的Comonad树版本.

有没有办法让我在这里得到两全其美？我是用Comonad/Monad挖出错误的树吗？基本上我正在寻找一种优雅的方法来在我的数据结构上建模这些函数.谢谢!

如果要查看完整代码,则函数位于此处,当前树位于此处.

Answer 1

我放弃了试图把它塞进评论中.康纳麦克布赖德(Conor McBride)有一个完整的演讲,与山姆林德利(Sam Lindley),一大堆论文,都是关于使用单子来雕刻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的join发生与树木树的叶子,让你走一路底部不必停止呼吸一半一路下滑.正如@danidiaz在答案中所表明的那样,将其Tree视为一个自由的单子可能会有所帮助.或者Kmett可能会说你有一个非常简单的语法允许术语替换被称为.VarLeaf

无论如何,重点是你可以>>=通过逐步砍伐树叶来种植树木.在这里,我有一个一维的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|

(在现实生活中,你可能只是一次切割一个窗口,通过在绑定函数中检查它的ID并且如果它不是你正在寻找的那个,则保持不变.)

问题是,Tree不了解物理空间是有限和宝贵的资源这一事实.fmap让你用as 代替s b,但是如果bs占用的空间比as 多,那么结果结构将不适合屏幕!

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

这在两个方面变得更加严重,因为盒子可以相互推动并撕裂.如果中间窗口被意外调整大小,我会得到一个畸形的盒子或中间的一个洞(取决于树的下落).

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

扩展窗口是一件非常合理的事情,但在现实世界中,它扩展到的空间必须来自某个地方.你不能在不缩小另一个窗口的情况下成长一个窗口,反之亦然.这不是可以完成的那种操作>>=,它在各个叶节点上执行局部替换; 你需要看一个窗口的兄弟姐妹,知道谁占用了它旁边的空间.

因此,您不应该被允许使用>>=这样的内容来调整大小.Lindley和McBride的想法是教类型检查器如何将盒子拼接在一起.使用类型级自然数和加法,

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

它们使用由宽度和高度索引的内容.(在论文中,他们使用表示为矢量矢量的2D矩阵,但为了提高效率,您可能希望使用一个测量其大小的幻像类型的数组.)

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类型,反映了调用者>>=无法控制将继续调用内容的维度的事实.

(>>=) :: 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)

如果你使用~>索引保留函数的类型同义词并翻转参数,你得到的东西看起来就像=<<普通的Monads,但是有一种不同的箭头.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)

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

^{*假设a指数确实是其物理尺寸的准确度量}