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


问题

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

我需要通过拉链访问它,我的焦点是一个字段(值可以这么说)。拉链应该支持这些动作 goDowngoUpgoLeft 和 goRight,每个都将焦点改变到指示方向的场地,以及 here,应返回当前焦点字段的值。

虽然这可以用一个 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

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

如上所述的表单上的数据类型如何在haskell中查找?它是否可以作为代数数据类型实现?

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


5610
2018-04-08 08:19


起源

你需要 访问 在 O(1) 时间也是? - Koterpillar
只有指示的动作需要一个 O(1) 执行时间处理时间。我不需要 O(1) 查找,如果这是你的意思。 - Undreren
一个相似的 题 有人问过。 - phg
读 我的答案中的价值是 O(1)但是写作是 O(sqrt(n))。我非常喜欢相关问题中的答案。 - Koterpillar
@phg - >链接中接受的答案也可以接受。我猜我的问题是重复的。 - Undreren


答案:


好吧,我很失望没有其他人对这个问题给出了“正确”的答案,因为我知道它存在,但我无法解释它。我的答案是基于 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)的顺序,如果你不环顾四周。

但这只是一个方面。再次出于某些原因,我不够聪明,无法解释将此扩展到两个维度id dead dead:

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以了解更多内容,特别是因为我不是最好的解释这些内容。


9
2018-04-09 04:39





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

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


1
2018-04-08 09:26



好吧,拉链的重点是能够访问焦点下的值 O(1) 时间。更新我的问题...... - Undreren
该 !! 列表上的操作不是 O(1), 它的 O(n)。从列表切换到 Vector 但是应该解决这个问题。 - Nikita Volkov
@NikitaVolkov即使有了 Vector 这无法更新O(1)中的聚焦值。 - Daniel Wagner