haskell - 在haskell中制作类似网格的数据类型

Question

问题

有一段时间我一直想知道如何有效地完成此操作，但由于某种原因我无法做到这一点。我需要建立一个矩形网格模型，其中每个字段都包含一些数据。

我需要通过 zipper 访问它，其中我的焦点是一个字段(可以说是值)。 zipper 应支持 goDown、goUp、goLeft 和 goRight 操作，每个操作都会将焦点更改为指示的方向，以及这里，它应该返回当前焦点下的字段的值。

虽然这可以通过 Map 来完成，但它的效率很低，因为改变焦点需要 log n 时间，n 是Map 中的元素数量，因为 Map 具有对数查找时间。

我需要在 O(1) 时间内执行指示的操作。

示例

出于说明目的，请查看下面的矩阵。括号内的数字是当前焦点。

1 (2) 3
4  5  6
7  8  9

如果我应用了goRight，我应该得到:

1  2 (3)
4  5  6
7  8  9

如果我现在这里申请，返回的值应该是3。

问题

上面解释的表单上的数据类型在 haskell 中看起来如何？它可以作为代数数据类型实现吗？

请记住，在所有四个方向上焦点的变化应该可以在 O(1) 时间内完成，并且可以读取当前焦点中的值。

Answer 1

好吧，我很失望，没有人对这个问题给出“正确”的答案，因为我知道它存在，但我无法很好地解释它。我的回答是基于http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html

首先，一个标准，即一维 zipper 可以是:

Data U x = U [x] x [x]

第一个元素是焦点“左”的所有元素的反向列表，然后是焦点元素，然后是焦点“右”的所有元素的列表。例如:

U [-1,-2,-3] 0 [1,2,3]

然后我们可以左右移动 zipper 。当我们冲出网格边缘时，你必须决定该怎么做。原始帖子只是假设了一个无限网格，以便将极端情况留给读者作为练习。

left  (U (a:as) x zs) = U as a (x:zs)
right (U as x (z:zs)) = U (x:as) z zs

现在所有看起来像容器的东西都应该是仿函数，所以:

instance Functor U where
  fmap f (U a x z) = U (map f a) (f x) (map f z)

在这一点上，我真的希望其他人能介入解释我要做什么以及为什么。我将使 U 成为 Control.Comonad 的实例。我能解释的最好的解释是，comonad 是一种由内而外的 monad。 Comonads 不是给你一个元素并要求你创建一个具有新值的容器 (>>=::Monad m => m a -> (a -> m b) -> m b)您可以获取整个结构，只询问属于焦点的值: (=>>)::Comonad w=>w a -> (w a -> b) -> w

因此使用comonad-3.0.2包中Control.Comonad的条款:

Instance Comonad U where
  -- extract :: U a -> a   -- called coreturn in the post
  extract (U _ x _) = x

  -- duplicate :: U a -> U (U a)  -- called cojoin in the post
  duplicate x = U (tail $ iterate left x) x (tail $ iterate right x)

重复给你一个 zipper zipper ，每个 zipper 比最后一个向左或向右移动一个元素。它看起来像是一个巨大的内存量，但 Haskell 很懒，实际的内存占用非常小，对于完整的集合来说约为 O(n)，如果你根本不环顾四周，则约为 O(1)。

但这只是一个维度。再次由于我不够聪明，无法解释将其扩展到二维的原因，这非常容易:

data U2 x = U2 (U(U x))

instance Functor U2 where
  fmap f (U2 y) = U2 $ fmap (fmap f) y

instance Comonad U2 where
  extract (U2 y) = extract (extract y)
  duplicate (U2 y) = fmap U2 $ U2 $ roll $ role y where
    iterate' f = tail . iterate f
    role x = U (iterate' (fmap left) x) x (iterate' (fmap right) x)

复制函数现在创建一个网格网格，每个网格都适当移动。所以

goLeft  u = let (U _ (U x _ _) _) = duplicate u in x
goRight u = let (U _ (U _ _ x) _) = duplicate u in x
goUp      = left  . duplicate
goDown    = right . duplicate
here      = extract

因为 Haskell 很懒，所有这些都是 O(1) 函数。更有趣的是，您可以在此处更改时间和内存的 O(1) 成本，并在计算中使用邻域单元。这使得实现像生命游戏细胞自动机一样简单

rule  (U2 (U
      (U (u0:_) u1 (u2:_):_)
      (U (u3:_) u4 (u5:_))
      (U (u6:_) u7 (u8:_):_))) =
         let n = length $ filter id [u0,u1,u2,u3,u5,u6,u7,u8] in
           u4 && (n==2 || n==3) || (not u4) && n==3

-- assume u is the original graph each step is
step u = u =>> rule

除了上面的博文之外，我建议在 Google 上搜索 Comonad 以了解更多信息，特别是因为我不是最擅长解释这些内容的人。