二维打结（是：用一个 comonad 打结）

Question

编辑： 最初的问题是 "tying the knot with a comonad"，但真正有用的是 [=24= 中与 U2Graph 打结的二维结]. 原始问题（直到回答）：

我想与来自一个 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:

时，我的大脑遇到了 "occurs check"

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中。我想确定圆圈实际上指向同一个 thunk。

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

背景：我尝试在haskell中实现codegolf's rat race。因此，由于耗时的计算，我想通过绑定知识来引用同一个 thunk。

回答

解决方案来自。就是少了一步不想挤进评论。

导致我的大脑运行变成 "occurs check" 的原因是：要构造一个 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

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

的 Comonad class

{-# 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 class 中它被称为 extend f = fmap f . duplicate.

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

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

Answer 2

可以从 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 构造函数是明智的。

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

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

二维

最终你想要构建一个二维字段。像我们在二维中为一维列表拉链所做的那样构建一个图要复杂得多，通常需要强制 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 可能如下所示。 + 是外脊，竖线 | 是内脊，* 是结构的焦点。

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

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

二维打结（是：用一个 comonad 打结）

Tie-the-knot in 2 dimensions (was: tying the knot with a comonad)

haskell

comonad

tying-the-knot

回答

二维