在 2 个维度上打结(即:用逗号打结)

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

我

无法解决的问题是，我需要参考我刚刚构建的东西，它被深深地埋藏在昏迷中。我想真正确定圆圈实际上指向同一个笨蛋。

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

---

背景：我尝试在哈斯克尔实现codegolf的老鼠赛跑。因此，对于捆绑知识，我想参考由于耗时的计算而相同的问题。

答

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

导致我的大脑遇到"发生检查"的是：要构建一个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)

Answer 1

可以从拉链构建图形，这样在图形上移动就不需要分配新的内存。如果您要保留结构中的多个指针，这可能是性能改进。

我们将从列表的拉链开始。

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构造函数。

为了将拉链转换为图形，我们从中间开始，然后从两侧开始。我们在图的已构建部分和图中尚未构建的部分之间系上递归结。

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)

结合我的其他答案，您可以使用以下方法构建U Int可见部分的图表

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

二维

最终，您希望构建一个 2D 字段。像我们为二维一维列表拉链所做的那样构建图形要棘手得多，并且通常需要强制O(n^2)内存遍历长度n的任意路径。

您计划使用Dan Piponi描述的二维列表拉链，因此我们将在此处重现它。

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可能看起来像是小便。+是外脊，垂直破折号|是内刺，*是结构的焦点。

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

每个内刺都是连续的——它不能有间隙。这意味着，如果我们考虑脊柱以外的位置，如果靠近脊柱的位置在该侧也有邻居，则它只能在左侧或右侧有一个邻居。这引起了我们将如何建立一个 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)

Answer 2

对于

U，使用Comonad实例，整个问题会更容易。我们将使用 comonad 的 Comonad 类。

{-# LANGUAGE DeriveFunctor #-}
import Data.List
import Control.Comonad
data U a = U [a] a [a]
    deriving (Functor)

除了Comonad方法之外，您还可以使用拉链做两件主要事情。您可以向左移动或向右移动。如果左侧或右侧没有剩余内容，则这两种方法都可能失败。

moveLeft :: U a -> Maybe (U a)
moveLeft (U (l:ls) h r) = Just $ U ls l (h:r)
moveLeft u              = Nothing
moveRight :: U a -> Maybe (U a)
moveRight (U l h (r:rs)) = Just $ U (h:l) r rs
moveRight u              = Nothing

Comonad有趣的部分是duplicate :: w a -> w (w a)它构建了一个在每个位置保存上下文的结构。我们可以根据展开moveLeft和moveRight来定义Comonad实例的duplicate。

instance Comonad U where
    extract (U _ here _) = here
    duplicate u = U (unfoldr (fmap dup . moveLeft) u) u (unfoldr (fmap dup . moveRight) u)
        where
            dup x = (x, x)

我们将解决您的tieKnot所暗示的问题。我们为U Comonad实例编写的duplicate将解决您的所有问题 - 我们根本不需要FullCell数据类型。你有一些函数limitTo5x5 :: U Int -> [[Int]]，一个特定子类型的实例 U a -> b 。

limitTo5x5 :: U Int -> [[Int]]
limitTo5x5 = undefined

如果我们首先duplicate U Int我们将有一个拉链，在每个位置固定完整的上下文。如果我们对此进行fmap limitTo5x5，我们将有一个拉链来固定结果

tieKnot :: U Int -> U [[Int]]
tieKnot = fmap limitTo5x5 . duplicate

fmap f . duplicate，这种模式是Comonad的对偶Monad绑定，>>=。在Comonad类中，它被称为 extend f = fmap f . duplicate .

tieKnot :: U Int -> U [[Int]]
tieKnot = extend limitTo5x5

现在是我们进行批判性观察的时候了。当我们在duplicate年建造外U时，我们只建造了一个U _ _ _ :: U (U a)。其中只有一个，它不需要递归引用其他任何东西。我们可以沿着所得的拉链自由地左右移动，而无需任何大笔费用。每次移动时，我们都需要分配一个U和一个列表缺点(:)，同时释放一个U和一个列表缺点。