3

编辑：U2Graph最初的问题是“与comonad 打结”，但这里真正有帮助的是与来自cirdec打结的二维结。原始问题（直到 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

但是，当我尝试填写 for 时，我的大脑会遇到“发生检查” 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))似乎遇到了同样的问题，但将更难扩展到二维。

背景：我尝试在haskell中实现codegolf的老鼠赛跑。因此，由于计算耗时，我想通过 tying-the-know 引用相同的 thunk。

回答

解决方案来自Cirdec 的 Answer。它只是错过了我不想发表评论的一小步。

导致我的大脑遇到“发生检查”的原因是：要构建 aFullCell并在其领域打结，move我需要已经构建的U2Graph FullCell. 既然我已经说过了，这个要求很容易写成：

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

其中第一个参数是构造 my 的函数FullCell。Cirdec 的功能可以轻松调整。最后一步是将comonad带回来：

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

2 回答 2

3

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

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

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

在将 a 转换U2 a为 a之前U2Graph a，我们先来看看 a 的结构U2 a。我将分配外部列表为左右方向，内部列表为上下方向。AU2有一条贯穿数据的脊椎，焦点沿着脊椎的任意位置。每个子列表都可以垂直于脊椎滑动，以便专注于子列表上的特定点。使用中的 AU2可能如下所示。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)
于 2015-02-14T23:29:58.377 回答
2

使用. Comonad_ U我们将使用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)它构建了一个在每个位置保存上下文的结构。我们可以duplicate根据Comonad展开moveLeft和定义实例moveRight。

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. 我们为实例duplicate编写的将解决您的所有问题 - 我们根本不需要数据类型。你有一些函数，一个特定子类型的实例。ComonadUFullCelllimitTo5x5 :: 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

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

于 2015-02-14T18:52:54.920 回答