哪种代数模式适合这种类型的树？
Which Algebraic Pattern fits this type of tree?
我有一个谜题给你，
我设法编写了一些代码来使用递归方案来完成这些事情，但它非常混乱
这通常意味着我在某处错过了一个有用的抽象。
我正在为我的文本编辑器设计布局系统
Rasa;它以非常相似的方式使用拆分
方式为 Vim。我决定用树来描述分裂；你可以想象
它是一棵垂直或水平分割的二叉树， 'Views' 在
叶节点。 这个
图片
可能有帮助。
这是我的初始数据结构：
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 which 'closes' 通过删除匹配谓词的任何视图
将它们从树中移除并适当地重新组织相邻视图。fmap;我希望树成为仿函数，这样我就可以改变视图。
一些不错的功能：
- focusRight :: Tree View -> Tree View，当且仅当最近的水平连接时，将视图设置为活动
左侧视图处于活动状态
我正在寻找可以提供此功能的抽象或一组抽象
以干净的方式提供功能。到目前为止，这是我的思考过程：
起初我以为我有一个Monoid，身份是空树，并且
mappend 只会将另一个分支附加到树上，但这不起作用
因为我有两个操作：垂直追加和水平追加以及操作
当它们混合在一起时没有关联。
接下来我想 'Some of my operations depend on their context' 所以我可能有一个 Comonad。树的版本
我没有作为 co-monad 工作，因为我在分支上没有 extract 的值，所以我重组了我的树
像这样：
data Tree a = Node Direction [Tree a] a [Tree a]
deriving (Functor)
但这还是
没有根据节点内部的内容处理 'splitting' 节点的情况，这与签名 (View -> Tree View) ->
Tree View -> Tree View 相匹配，它与来自 Monad 的 bind 统一，所以也许我有一个 monad？我可以为
原始树定义，但无法为我的 Comonad 树版本弄明白。
有什么方法可以让我在这里两全其美吗？我用 Comonad/Monad 挖错树了吗？
基本上，我正在寻找一种优雅的方式来在我的数据结构上对这些功能进行建模。谢谢！
我会将您的类型表示为 monad 并使用 >>= 来处理 split。
{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free
data Direction = Hor | Vert
data TreeF a = TreeF Direction a a deriving Functor
type Tree a = Free TreeF a
至于close，我可能会用cata or para from recursion-schemes, since close seems to work bottom-up and require at most knowledge of node parents and siblings. You could also turn to Control.Lens.Plated。
顺便说一句，Free 已经有一个 Recursive 实例。 FreeF TreeF a 将是相应的代数。但是你说效果不是很好
直接使用 Free 和 FreeT 构造函数可能会很麻烦。也许一些模式同义词可以提供帮助。
我放弃了将其塞进评论的尝试。 Conor McBride has a whole talk and, with Sam Lindley, a big chunk of a paper, all about using monads to carve up 2D space. Since you asked for an elegant solution I feel compelled to give you a potted summary of their work, although I wouldn't necessarily advise building this into your codebase - I suspect it's probably simpler just to work with a library like 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 takes a tree with trees at its leaves and lets you walk all the way to the bottom without stopping for breath half way down. It may be helpful to think of Tree as a free monad, as @danidiaz has shown in . Or Kmett might say 你有一个非常简单的允许术语替换的语法，其 Var 被称为 Leaf.
无论如何，关键是您可以使用 >>= 通过逐渐砍掉树叶来种植树木。这里我有一个一维 UI（让我们暂时忘记 Direction）和一个包含 String 的单个 window，然后通过反复将其切成两半我结束了加上八个较小的 windows.
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|
（在现实生活中，您可能一次只切割一个 window，方法是在您的绑定函数中检查它的 ID，如果它不是您要查找的那个，则将其原封不动地返回。 )
问题是，Tree不了解物质space是一种有限而宝贵的资源这一事实。 fmap 允许您将 a 替换为 b，但如果 b 占用的空间比 space 多，则生成的结构将无法显示在屏幕上a 做到了！
ghci> fmap ("in" ++) myT
Leaf "incompleteshambles"
这在二维空间中变得更加严重，因为盒子可以相互推动并撕裂。如果中间 window 不小心调整了大小，我要么得到一个畸形的盒子，要么在中间有一个洞（取决于它在树上的位置）。
+-+-+-+ +-+-+-+ +-+-+ +-+
| | | | | | | | | | | | |
+-+-+-+ +-+-+-++-+ or, +-+-+--+-+
| | | | ----> | | | | perhaps | | | |
+-+-+-+ +-+-+-++-+ +-+-+--+-+
| | | | | | | | | | | | |
+-+-+-+ +-+-+-+ +-+-+ +-+
扩展 window 是一件非常合理的事情，但在现实世界中，它扩展到的 space 必须来自某个地方。你不能扩大一个 window 而不缩小另一个，反之亦然。这不是可以用 >>= 完成的那种操作，它在单个叶节点上执行局部替换；你需要查看 window 的兄弟姐妹才能知道谁在占用相邻的 space。
所以你不应该被允许使用 >>= 来调整内容的大小。 Lindley 和 McBride 的想法是教类型检查器如何将框组合在一起。使用类型级自然数和加法，
data Nat = Z | S Nat
type family n :+ m where
Z :+ m = m
S n :+ m = S (n :+ m)
他们处理按宽度和高度索引的内容。 （在论文中，他们使用表示为向量的向量的二维矩阵，但为了提高效率，您可能希望使用具有测量其大小的幻影类型的数组。）
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 的语义没有改变——它把一个二维对象放在一个 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)
如果您使用类型同义词 ~> 作为索引保留函数并翻转参数，您会得到类似于 =<< 用于常规 Monad 的东西，但带有不同种类的箭头。 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)
这就是索引集上的单子。 （更多内容在 Kleisli Arrows of Outrageous Fortune.) In the paper they build a bunch more infrastructure to support cropping and rearranging boxes, which would probably be useful to you building a UI. For efficiency you might also decide to track the currently focused window using a zipper，这是一个有趣的练习。顺便说一句，我认为 Hasochism 是对一般奇特类型的一个很好的介绍，而不仅仅是作为这个特定问题的解决方案。
*假设a的索引确实是其物理尺寸的准确度量
我有一个谜题给你，
我设法编写了一些代码来使用递归方案来完成这些事情，但它非常混乱 这通常意味着我在某处错过了一个有用的抽象。
我正在为我的文本编辑器设计布局系统
Rasa;它以非常相似的方式使用拆分
方式为 Vim。我决定用树来描述分裂；你可以想象
它是一棵垂直或水平分割的二叉树， 'Views' 在
叶节点。 这个
图片
可能有帮助。
这是我的初始数据结构：
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 Viewwhich 'closes' 通过删除匹配谓词的任何视图 将它们从树中移除并适当地重新组织相邻视图。fmap;我希望树成为仿函数，这样我就可以改变视图。
一些不错的功能：
- focusRight :: Tree View -> Tree View，当且仅当最近的水平连接时，将视图设置为活动
左侧视图处于活动状态
我正在寻找可以提供此功能的抽象或一组抽象 以干净的方式提供功能。到目前为止，这是我的思考过程：
起初我以为我有一个Monoid，身份是空树，并且
mappend 只会将另一个分支附加到树上，但这不起作用
因为我有两个操作：垂直追加和水平追加以及操作
当它们混合在一起时没有关联。
接下来我想 'Some of my operations depend on their context' 所以我可能有一个 Comonad。树的版本
我没有作为 co-monad 工作，因为我在分支上没有 extract 的值，所以我重组了我的树
像这样：
data Tree a = Node Direction [Tree a] a [Tree a]
deriving (Functor)
但这还是
没有根据节点内部的内容处理 'splitting' 节点的情况，这与签名 (View -> Tree View) ->
Tree View -> Tree View 相匹配，它与来自 Monad 的 bind 统一，所以也许我有一个 monad？我可以为
原始树定义，但无法为我的 Comonad 树版本弄明白。
有什么方法可以让我在这里两全其美吗？我用 Comonad/Monad 挖错树了吗？ 基本上，我正在寻找一种优雅的方式来在我的数据结构上对这些功能进行建模。谢谢！
我会将您的类型表示为 monad 并使用 >>= 来处理 split。
{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free
data Direction = Hor | Vert
data TreeF a = TreeF Direction a a deriving Functor
type Tree a = Free TreeF a
至于close，我可能会用cata or para from recursion-schemes, since close seems to work bottom-up and require at most knowledge of node parents and siblings. You could also turn to Control.Lens.Plated。
顺便说一句，Free 已经有一个 Recursive 实例。 FreeF TreeF a 将是相应的代数。但是你说效果不是很好
直接使用 Free 和 FreeT 构造函数可能会很麻烦。也许一些模式同义词可以提供帮助。
我放弃了将其塞进评论的尝试。 Conor McBride has a whole talk and, with Sam Lindley, a big chunk of a paper, all about using monads to carve up 2D space. Since you asked for an elegant solution I feel compelled to give you a potted summary of their work, although I wouldn't necessarily advise building this into your codebase - I suspect it's probably simpler just to work with a library like 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 takes a tree with trees at its leaves and lets you walk all the way to the bottom without stopping for breath half way down. It may be helpful to think of Tree as a free monad, as @danidiaz has shown in Var 被称为 Leaf.
无论如何，关键是您可以使用 >>= 通过逐渐砍掉树叶来种植树木。这里我有一个一维 UI（让我们暂时忘记 Direction）和一个包含 String 的单个 window，然后通过反复将其切成两半我结束了加上八个较小的 windows.
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|
（在现实生活中，您可能一次只切割一个 window，方法是在您的绑定函数中检查它的 ID，如果它不是您要查找的那个，则将其原封不动地返回。 )
问题是，Tree不了解物质space是一种有限而宝贵的资源这一事实。 fmap 允许您将 a 替换为 b，但如果 b 占用的空间比 space 多，则生成的结构将无法显示在屏幕上a 做到了！
ghci> fmap ("in" ++) myT
Leaf "incompleteshambles"
这在二维空间中变得更加严重，因为盒子可以相互推动并撕裂。如果中间 window 不小心调整了大小，我要么得到一个畸形的盒子，要么在中间有一个洞（取决于它在树上的位置）。
+-+-+-+ +-+-+-+ +-+-+ +-+
| | | | | | | | | | | | |
+-+-+-+ +-+-+-++-+ or, +-+-+--+-+
| | | | ----> | | | | perhaps | | | |
+-+-+-+ +-+-+-++-+ +-+-+--+-+
| | | | | | | | | | | | |
+-+-+-+ +-+-+-+ +-+-+ +-+
扩展 window 是一件非常合理的事情，但在现实世界中，它扩展到的 space 必须来自某个地方。你不能扩大一个 window 而不缩小另一个，反之亦然。这不是可以用 >>= 完成的那种操作，它在单个叶节点上执行局部替换；你需要查看 window 的兄弟姐妹才能知道谁在占用相邻的 space。
所以你不应该被允许使用 >>= 来调整内容的大小。 Lindley 和 McBride 的想法是教类型检查器如何将框组合在一起。使用类型级自然数和加法，
data Nat = Z | S Nat
type family n :+ m where
Z :+ m = m
S n :+ m = S (n :+ m)
他们处理按宽度和高度索引的内容。 （在论文中，他们使用表示为向量的向量的二维矩阵，但为了提高效率，您可能希望使用具有测量其大小的幻影类型的数组。）
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 的语义没有改变——它把一个二维对象放在一个 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)
如果您使用类型同义词 ~> 作为索引保留函数并翻转参数，您会得到类似于 =<< 用于常规 Monad 的东西，但带有不同种类的箭头。 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)
这就是索引集上的单子。 （更多内容在 Kleisli Arrows of Outrageous Fortune.) In the paper they build a bunch more infrastructure to support cropping and rearranging boxes, which would probably be useful to you building a UI. For efficiency you might also decide to track the currently focused window using a zipper，这是一个有趣的练习。顺便说一句，我认为 Hasochism 是对一般奇特类型的一个很好的介绍，而不仅仅是作为这个特定问题的解决方案。
*假设a的索引确实是其物理尺寸的准确度量