haskell - 在 2 维中打结(是 : tying the knot with a comonad)

编辑:最初的问题是“用 comonad 打结”，但这里真正有帮助的是与 cirdec 中的 U2Graph 打结的二维结。原始问题(直到Anwser):

我想用来自共子的数据打结

data U a = U [a] a [a]

到更丰富的数据结构

data FullCell = FullCell {
   vision   :: [[Int]],
   move     :: Int -> Maybe FullCell -- tie the knot here!
}

带功能

tieKnot :: U Int -> U FullCell

但是，当我尝试填写 undefined 时，我的大脑遇到了“发生检查”:

tieKnot :: U Int -> U FullCell
tieKnot u = u =>> (\z -> FullCell {
      vision = limitTo5x5 z,
      move = move'
})  where
         move'   1  = Just undefined -- tie the knot to neighbor here
         move' (-1) = Just undefined -- ...
         move'   _  = Nothing
         limitTo5x5 = undefined -- not of interest, but the cause why a comonad is used

我无法解决的问题是，我需要引用我刚刚构建的东西，它深埋在一个共子中。我想确定圆圈实际上指向同一个 thunk。

解决它的最佳方法是什么？那个 comonad U a 是要走的路吗？双向链表 data T a = T (Maybe (T a)) a (Maybe (T a)) 似乎遇到了同样的问题，但扩展到二维会困难得多。

背景:我尝试在 haskell 中实现 codegolf's rat race。因此，由于耗时的计算，我想引用同一个 thunk。

回答

解决方案来自 Cirdec's Answer 。它只是错过了我不想挤进评论中的一小步。

导致我的大脑遇到“发生检查”的原因是:要构建 FullCell 并在其字段 move 上打结，我需要已经构建的 U2Graph FullCell 。既然我说了，需求很容易写成:

toU2Graph :: (U2Graph b -> a -> b) -> U2 a -> U2Graph b

其中第一个参数是构造我的 FullCell 的函数。 Cirdec 的功能可以很容易地适应。最后一步是将 comonad 带回来:

toU2GraphW :: (U2Graph b -> U2 a -> b) -> U2 a -> U2Graph b
toU2GraphW f u = toU2Graph f (duplicate u)

最佳答案

可以从 zipper 构建图形，以便在图形上移动不需要分配新内存。如果您要保留多个指向结构的指针，这可以提高性能。

我们将从列表的 zipper 开始。

data U a = U [a] a [a]

相应的图保存对左右节点的引用(如果存在)。

data UGraph a = UGraph {
    _left :: Maybe (UGraph a),
    _here :: a,
    _right :: Maybe (UGraph a)
    }

这种结构的任何实例都应遵守以下定律，即先往一个方向然后再返回另一个方向，您将回到起点。

_right >=> _left  == \x -> (_right >=> const (return x)) x
_left  >=> _right == \x -> (_left  >=> const (return x)) x

UGraph 数据类型不强制执行此操作，因此将其放在模块中而不导出 UGraph 构造函数是明智的。

要将 zipper 转换为图形，我们从中间开始，然后从两侧开始。我们在图中已经构建的部分和图中尚未构建的部分之间建立递归结。

toUGraph :: U a -> UGraph a
toUGraph (U ls h rs) = g
    where
        g = UGraph (build ugraph' g ls) h (build UGraph g rs)
        ugraph' r h l = UGraph l h r
        build _ _    []          = Nothing
        build f prev (here:next) = Just g
            where
                g = f (Just prev) here (build f g next)

结合 my other answer ，您可以构建 U Int 可见部分的图形

tieKnot :: U Int -> UGraph [[Int]]
tieKnot = toUGraph . extend limitTo5x5

二维

最终你想建立一个二维字段。像我们在二维中为一维列表 zipper 所做的那样构建图要复杂得多，通常需要强制 O(n^2) 内存遍历长度为 n 的任意路径。

您计划使用 two-dimensional list zipper Dan Piponi described ，因此我们将在此处重现它。

data U2 a = U2 (U (U a))

我们可能很想为 U2 制作一个直接模拟的图表

data U2Graph a = U2Graph (UGraph (UGraph a))

这具有相当复杂的结构。相反，我们将做一些更简单的事情。对应于 U2 的图节点将保存对四个基本方向中每个方向上相邻节点的引用，如果这些节点存在的话。

data U2Graph a = U2Graph {
    _down2  :: Maybe (U2Graph a),
    _left2  :: Maybe (U2Graph a),
    _here2  :: a,
    _right2 :: Maybe (U2Graph a),
    _up2    :: Maybe (U2Graph a)
    }

U2Graph 的实例应该遵守我们为 UGraph 定义的相同的双向迭代器定律。同样，该结构本身并不强制执行这些法律，因此 U2Graph 构造函数可能不应该公开。

_right2 >=> _left2  == \x -> (_right2 >=> const (return x)) x
_left2  >=> _right2 == \x -> (_left2  >=> const (return x)) x
_up2    >=> _down2  == \x -> (_up2    >=> const (return x)) x
_down2  >=> _up2    == \x -> (_down2  >=> const (return x)) x

在我们将 U2 a 转换为 U2Graph a 之前，让我们看一下 U2 a 的结构。我要将外部列表分配为左右方向，将内部列表分配为上下方向。 U2 有一条贯穿数据的脊椎，焦点位于沿脊椎的任何位置。每个子列表都可以垂直于脊椎滑动，以便它专注于子列表上的特定点。使用中的 U2 可能看起来像以下内容。 + s 是外脊，垂直破折号 | 是内脊，* 是结构的焦点。

|
||
|||   ||
|||| |||| |
+++*++++++++
 |||||| ||
  ||||
   ||

每个内刺都是连续的——它不能有间隙。这意味着，如果我们正在考虑远离脊柱的位置，则只有在靠近脊柱的位置也有该侧的邻居时，它才能在左侧或右侧有一个邻居。这导致了我们将如何构建 U2Graph 。我们将沿着外脊建立左右连接，递归引用回到焦点，就像我们在 toUGraph 中所做的那样。我们将沿着内脊建立上下连接，递归引用回到脊椎，就像我们在 toUGraph 中所做的那样。要从内部脊椎上的节点建立到左侧和右侧的连接，我们将向外部脊椎靠近一步，在该节点向侧面移动，然后在相邻的内部脊椎上远离外部脊椎移动一步.

toU2Graph :: U2 a -> U2Graph a
toU2Graph (U2 (U ls (U ds h us) rs)) = g
    where
        g = U2Graph (build u2down g ds) (build u2left g ls) h (build u2right g rs) (build u2up g us)
        build f _    []          = Nothing
        build f prev (here:next) = Just g
            where
                g = f (Just prev) here (build f g next)
        u2up   d h u = U2Graph d (d >>= _left2 >>= _up2  ) h (d >>= _right2 >>= _up2  ) u
        u2down u h d = U2Graph d (u >>= _left2 >>= _down2) h (u >>= _right2 >>= _down2) u
        u2left r (U ds h us) l = g
            where
                g = U2Graph (build u2down g ds) l h r (build u2up g us)
        u2right l (U ds h us) r = g
            where
                g = U2Graph (build u2down g ds) l h r (build u2up g us)

关于haskell - 在 2 维中打结(是 : tying the knot with a comonad)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28516819/