在haskell中创建类似网格的数据类型

Question

问题

我一直在想如何在一段时间内有效地完成这项任务,但由于某种原因,我无法做到这一点.我需要建模一个矩形网格,其中每个字段包含一些数据.

我需要通过拉链访问它,我的焦点是一个字段(值可以这么说).拉链应该支持的动作goDown,goUp,goLeft和goRight,每个改变聚焦到字段中所指示的方向,以及here,其中应目前正在焦点返回字段的值.

虽然这可以用a来完成Map,但是在某种意义上,由于具有对数查找时间,因此改变焦点需要花费log n时间,n即元素的数量,这是低效的.MapMap

我需要指示的行动及时发挥作用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)及时的,以及读取当前焦点的值.

Answer 1

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

首先,一个标准,即1d拉链可以是:

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是一种由内到外的monad.(>>= :: Monad m => m a -> (a -> m b) -> m b)Comonads 不是给你一个元素并要求你创建一个具有新值的容器,而是为你提供整个结构,并且只询问属于焦点的值:(=>>) :: 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)

复制品为您提供拉链拉链,每个拉链左或右移动一个元素,然后是最后一个元素.它似乎是一个巨大的内存,但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)函数.更有趣的是,您可以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以了解更多内容,特别是因为我不是最好的解释这些内容.

Answer 2

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

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))。