13

问题

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

我需要通过拉链访问它，我的焦点是一个字段（可以说是值）。拉链应支持、和动作goDown，每个动作将焦点更改为指定方向上的字段，以及，这应返回当前处于焦点下的字段的值。goUpgoLeftgoRighthere

虽然这可以用 a 来完成，但从某种意义上说，它是低效的，因为 a 具有对数查找时间Map，因此改变焦点需要log n时间，因为 a具有对数查找时间。nMapMap

我需要指示的行动及时工作O(1)。

例子

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

1 (2) 3
4  5  6
7  8  9

如果我申请goRight，我应该得到：

1  2 (3)
4  5  6
7  8  9

如果我here现在申请，返回的值应该是3.

问题

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

请记住，在所有四个方向上的焦点变化都应该及时可行O(1)，以及读取当前焦点的值。

4

2 回答 2

12

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

首先，一个标准，即一维拉链可以是：

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

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

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

然后我们可以左右移动拉链。当我们跑出网格边缘时，您必须决定要做什么。原始帖子只是假设了一个无限网格，因此将角落案例留给读者作为练习。

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

现在所有看起来像容器的东西都应该是 Functor，所以：

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

在这一点上，我真的希望其他人能够解释我将要做什么以及为什么。我将创建U一个Control.Comonad. 我能解释的最好的就是comonads是一种由内而外的monads。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)

duplicate 为您提供一个 Zipper of Zipper，每个 Zipper 向左或向右移动一个元素，然后是最后一个元素。这似乎是一个巨大的内存量，但 Haskell 是懒惰的，实际的内存占用非常小，如果你根本不环顾四周，整个集合的 O(n) 和 O(1) 的数量级。

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

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) 函数。更有趣的是，您可以更改here时间和内存的 O(1) 成本，并在计算中使用邻域单元。这使得实现像元game of life胞自动机一样简单

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 以了解更多信息，特别是因为我不擅长解释这些东西。

于 2013-04-09T04:39:54.187 回答
1

这可能不是您要问的，但我想先听听为什么要提出更好的答案。

data GridWithZipper a = GridWithZipper { grid :: [[a]]
                                       , gwzx :: Int
                                       , gwzy :: Int
                                       }

goLeft  gwz = gwz { gwzx = gwzx gwz - 1 }
goRight gwz = gwz { gwzx = gwzx gwz + 1 }
goUp    gwz = gwz { gwzy = gwzy gwz - 1 }
goDown  gwz = gwz { gwzy = gwzx gwz + 1 }

get gwz = grid gwz !! gwzx gwz !! gwzy gwz

所有的操作都很明显O(1)。

然而，所有的go操作都是O(1)，获取和设置O(sqrt(n))。

于 2013-04-08T09:26:34.327 回答