嵌套列表Haskell迭代

Question

我需要在Haskell中实现嵌套列表操作。

f :: [[String]] -> [[String]] 

我的输入是二维数组

[ [ ”A” , ”A” , ”A” ] 
, [ ”B” , ”B” , ”A” ] 
, [ ”A” , ”A” , ”B” ] ] 

我任意生成该列表。

A A A 
B B A 
A A B 

所以在我的实施中，我需要做以下工作。

• 如果位置有A，它有2个或多于2“B”的邻居，它会变成B.
• 如果位置具有B，并且它有2个或2个以上“B “邻居，它保持原样。
• 如果一个位置有B，它具有小于2“B”的邻居，将第1步我的表看起来像这样所以以后转向A.

。

B B A 
A B B 
B B A 

如果我要使用C或C++，我的算法将是这样的：

1. 让我输入的副本。

2. 在2for循环中遍历这两个列表，检查是否有语句改变位置，每当我要做出改变时，我都会改变第二个列表而不是第一个列表，以便遍历第一个列表不会影响其他的“A”和“B”。

3. 返回第二个列表。

问题是，在Haskell中，我无法使用迭代。我怎么解决这个问题？

Answer 1

正如我在评论中所述，递归是Haskell中的循环原语。然而，Haskell为我们提供了很多强大的功能来构建更多用户友好的抽象，而不是直接使用递归。正如@Lazersmoke所提到的那样，当您根据集合中的其他值（例如值的邻居）更新集合的每个单独值时，Comonad是一个很好的抽象。

在网络上有很多Comonad类的例子，但是很遗憾Monad黯然失色。所以这是我的尝试，甚至有点分数。

这将是一个很长的文章，所以让我从结果开始。这是从GHCi：

λ display example 
[[A,A,A],[B,B,A],[A,A,B]] 
λ display (transition example) 
[[B,B,A],[A,B,B],[B,B,A]] 

好的，现在让我们开始业务。一是一些行政的事情：

module Main where 
import Control.Comonad -- from the comonad package 

我要去尝试仔细解释每件作品，但大局观变得明显之前，可能需要一段时间。首先，我们将创建一个通常称为拉链的有趣数据结构，并为其实施Functor实例。

data U x = U [x] x [x] deriving Functor 

instance Functor U where 
    fmap f (U as x bs) = U (fmap f as) (f x) (fmap f bs) 

这个数据结构似乎并不特别。这就是我们如何使用U，使它变得很酷。由于Haskell是懒惰的，我们可以使用U构造函数来使用无限列表。例如，i1 = U [-1,-2..] 0 [1,2..]代表所有整数。尽管如此，这还不是全部。还有另外一条信息：中心点为0.我们也可以将所有整数表示为i2' = U [0,-1..] 1 [2,3..]。这些值几乎相同;他们只是移动一个。事实上，我们可以创造将一个变为另一个的功能。

rightU (U a b (c:cs)) = U (b:a) c cs 
leftU (U (a:as) b c) = U as a (b:c) 

正如你所看到的，我们可以幻灯片一个U向左或右只是通过重新排列元素。我们为U创建一个Show实例，然后验证rightU和leftU的工作。我们显然不能打印无限列表，所以我们只需从每一边取3个元素。

instance Show x => Show (U x) where 
    show (U as x bs) = (show . reverse . take 3) as ++ (show x) ++ (show . take 3) bs 

λ i1 
[-3,-2,-1]0[1,2,3] 
λ leftU i2 
[-3,-2,-1]0[1,2,3] 
λ i2 
[-2,-1,0]1[2,3,4] 
λ rightU i1 
[-2,-1,0]1[2,3,4] 

让我们回顾一下我们的最终目标。我们希望有一个数据结构，我们可以根据它的所有邻居更新每个值。让我们看看如何用我们的U数据结构来做到这一点。假设我们想用它的邻居的和来替换每个数字。首先，让我们写一个计算U的当前位置的邻居功能：

sumOfNeighbors :: U Int -> Int 
sumOfNeighbors (U (a:_) _ (b:_)) = a + b 

而只是为了验证它的工作原理：

λ sumOfNeighbors i1 
0 
λ sumOfNeighbors i2 
2 

不幸的是，这只是给了我们一个结果。我们希望将这个功能应用于每个可能的位置。那么U有Functor实例，所以我们可以用fmap这个函数来实现。如果我们的函数的类型为Int -> Int，但这实际上是U Int -> Int。但是如果我们可以将我们的U Int变成U (U Int)呢？然后fmap sumOfNeighbors会做我们想要的！

准备好一些初始级数据结构。我们将利用我们U Int并创建一个U (U Int)将这个样子：

-- not real Haskell. just for illustration 
U [leftU u, (leftU . leftU) u, (leftU . leftU . leftU) u..] u [rightU u, (rightU . rightU) u, (rightU . rightU . rightU) u..] 

的新U (U a)该中心是原U a。当我们向左滑动时，我们得到原来的U a向左滑动，并且同样向右滑动。换句话说，新U (U a)包含原始U a的所有左，右滑条下面是我们如何做到这一点：

duplicate :: U a -> U (U a) 
duplicate u = U lefts u rights 
    where lefts = tail $ iterate leftU u 
     rights = tail $ iterate rightU u 

我们可以用duplicate写我们想要的功能：

extend :: (U a -> b) -> U a -> U b 
extend f = fmap f . duplicate 

让我们试试看。

λ extend sumOfNeighbors i1 
[-6,-4,-2]0[2,4,6] 

看起来像是有效的。这些函数名称，duplicate和extend不是任意选择的（至少我是这样）。这些功能是Comonad类型类的一部分。我们一直在为我们的U数据类型实施它。

class Functor w => Comonad w where 
    extract :: w a -> a 
    duplicate :: w a -> w (w a) 
    extend :: (w a -> b) -> w a -> w b 

唯一缺少的是extract这是平凡的U：

extract (U _ x _) = x 

它可能并不明显这个类是多么有用呢。我们继续前进，看看如何处理二维情况。我们可以用拉链拉链做2维。即，U (U a)左右移动内拉链，上下移动外拉链。

newtype V a = V { getV :: U (U a) } 

instance Functor V where 
    fmap f = V . (fmap . fmap) f . getV 

-- shift the 'outer' zipper 
up :: V a -> V a 
up = V . leftU . getV 

down :: V a -> V a 
down = V . rightU . getV 

-- shift the 'inner' zippers 
left :: V a -> V a 
left = V . fmap leftU .getV 

right :: V a -> V a 
right = V . fmap rightU . getV 

这里是Comonad看起来像V：

instance Comonad V where 
    extract = extract . extract . getV 
    duplicate = fmap V . V . dup . dup . getV 
    where dup u = U (lefts u) r (right u) 
      lefts u = tail $ iterate (fmap leftU) u 
      rights u = tail $ iterate (fmap rightU) u 

的extract功能是相当简单的;它只是通过两层拉链来挖掘当前值。另一方面，duplicate是一种怪物。忽略新类型V，其类型将是duplicate :: U (U a) -> U (U (U (U a)))。帮助函数dup的用途是添加一个U图层。它被调用两次。然后我们将其包装在V中以获得V (U (U a))。然后fmap V包裹内部U (U a)以产生结果V (V a)。

哦顺便说一句，如果你想知道extend在哪里，我们实际上并不需要写它。上面给出的定义是其默认值。

这是很多工作，但现在我们将能够轻松解决原始问题！看一下这个。我要做一个数据结构，其中包括您A和B价值观，也是我们不关心的值，C：

data Token = A | B | C deriving (Eq,Show) 

和这里的一些东西，使建筑和显示V容易。

-- a list of U's containing nothing but x's 
filled x = repeat $ U (repeat x) x (repeat x) 

type Triple a = (a,a,a) 

-- create a U with the middle values a, b, and c, and all the other values the defaulted to d 
toU :: a -> Triple a -> U a 
toU d (a,b,c) = U (a : repeat d) b (c : repeat d) 

-- create a V centered on the 9 given values and default all other values to d 
toV :: a -> Triple (Triple a) -> V a 
toV d (as, bs, cs) = V (U x y z) 
    where x = (toU d as) : filled d 
     y = toU d bs 
     z = (toU d cs) : filled d 

display :: Show a => V a -> [[a]] 
display v = fmap g [ [up . left, up, up . right] 
        , [left, id, right] 
        , [down . left, down , down . right] ] 
    where g = fmap (extract . ($ v)) 

这里的例子是什么样子：

example = toV C ((A,A,A) 
       ,(B,B,A) 
       ,(A,A,B)) 

而且规则由实施：

-- move into each neighboring position and get the value in that position 
neighbors :: V a -> [a] 
neighbors v = fmap (extract . ($ v)) positions 
    where positions = [ up . left 
        , up 
        , up . right 
        , left 
        , right 
        , down . left 
        , down 
        , down . right ] 

numberOfBs :: V Token -> Int 
numberOfBs = length . filter (==B) . neighbors 

rule :: V Token -> Token 
rule v = case extract v of 
    C -> C -- C's remain C's forever 
    _ -> if numberOfBs v >= 2 then B else A 

最后，我们可以使用extend申请rule每一个值：

transition = extend rule 

λ display (transition example) 
[[B,B,A],[A,B,B],[B,B,A]] 

虽然这条规则很无聊。一切都很快成为B的。

λ take 10 $ fmap display (iterate transition example) 
[[[A,A,A],[B,B,A],[A,A,B]],[[B,B,A],[A,B,B],[B,B,A]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,B,B],[B,B,B],[B,B,B]]] 

创建不同的规则很容易。

rule2 :: V Token -> Token 
rule2 v = case extract v of 
    C -> C 
    A -> if numberOfBs v >= 2 then B else A 
    B -> if numberOfBs v >= 4 then A else B 

λ take 10 $ fmap display (iterate (extend rule2) example) 
[[[A,A,A],[B,B,A],[A,A,B]],[[B,B,A],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]],[[B,A,B],[A,A,A],[B,A,B]],[[B,B,B],[B,B,B],[B,B,B]]] 

很酷，对吗？我想提到的最后一件事。你有没有注意到我们没有写任何特殊情况来处理边缘？由于数据结构是无限的，所以我们只是用值C填充了我们不关心的范围内的东西，并且在考虑邻居时忽略它。