嵌套列表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填充了我們不關心的範圍內的東西，並且在考慮鄰居時忽略它。