haskell - 在 2 维中喜结连理(原为 : tying the knot with a comonad)

Question

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

我想与源自 comonad 的数据结合起来

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

我无法解决的问题是，我需要引用我刚刚构建的东西，并且它被深埋在comonad中。我想真正确定圆圈实际上指向同一个重击。

解决这个问题的最佳方法是什么？那 comonad U a 是正确的选择吗？双向链表 data T a = T (Maybe (T a)) a (Maybe (T a)) 似乎会遇到同样的问题，但扩展到二维会更困难。

<小时/>

背景:我尝试实现codegolf's rat race在 haskell 。因此，由于计算耗时，我想通过 tying-the-know 来引用同一个 thunk。

回答

解决方案来自Cirdec's Answer 。它只是缺少一个我不想挤进评论的一小步。

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

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

其中第一个参数是构造我的 FullCell 的函数。 Circdec 的功能可以轻松调整。最后一步是将 comonad 重新引入:

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

Answer 1

可以从 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)