问题
我一直在想如何在一段时间内有效地完成这项工作,但由于某种原因,我无法做到这一点。我需要建模一个矩形网格,其中每个字段包含一些数据。
我需要通过拉链访问它,我的焦点是一个字段(值可以这么说)。拉链应该支持这些动作 goDown
, goUp
, goLeft
和 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)
时间,以及阅读当前焦点的价值。
好吧,我很失望没有其他人对这个问题给出了“正确”的答案,因为我知道它存在,但我无法解释它。我的答案是基于 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以了解更多内容,特别是因为我不是最好的解释这些内容。
这可能不是你要问的,但我想听听为什么要先提出更好的答案。
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))
但是。