8

我有一个谜题给你

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

我正在为我的文本编辑器设计一个布局系统 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，当且仅当左侧最近的水平连接视图处于活动状态时，才将视图设置为活动状态

我正在寻找一种抽象或一组抽象，它们将以一种干净的方式提供此功能。到目前为止，这是我的思考过程：

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

接下来我想“我的一些操作取决于他们的上下文”，所以我可能有一个 Comonad。我拥有的树的版本不能作为共同单子工作，因为我extract在分支上没有价值，所以我像这样重组了我的树：

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

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

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

如果你想查看完整的代码，函数在这里，当前树在这里。

4

2 回答 2

6

我放弃了尝试将其塞进评论中。Conor McBride与 Sam Lindley进行了一场完整的演讲，以及一大篇论文，都是关于使用 monads 来划分 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'sjoin在其叶子上带有树木的树木，让您一路走到底部，而不必停下来呼吸一半。正如@danidiaz 在答案Tree中所显示的那样，将其视为免费的 monad可能会有所帮助。或者Kmett 可能会说您有一个非常简单的语法允许术语替换，其被称为.VarLeaf

无论如何，重点是您可以>>=通过逐步砍伐树叶来种植树木。在这里，我有一个一维 UI（让我们Direction暂时忘掉），其中包含一个包含 a 的窗口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，但如果s 占用的空间比s 多b，则生成的结构将不适合屏幕！ba

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)

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

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一个已知大小的 a 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)

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

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

于 2017-03-20T06:22:25.100 回答
1

我会将您的类型表示为 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，我可能会使用cataor parafrom recursion-schemes，因为close它似乎是自下而上的，并且最多需要节点父母和兄弟姐妹的知识。你也可以转向Control.Lens.Plated.

顺便说一句，Free已经有一个Recursive实例。FreeF TreeF a将是相应的代数。但你提到它的效果并不好。

直接使用Free和FreeT构造函数可能会很麻烦。也许一些模式同义词可以帮助。

于 2017-03-19T21:47:05.813 回答