以列表的列表，併產生所有變體用一個元素取代

Question

我有類型字符的二維地圖：

type Row = [Char] 
type Mappy = [Row] 

我想編寫一個函數，需要一個Mappy，如：

[['o','o'],['o','o']] 

併產生所有Mappy s的一個單一的 'O' 元件與替換的列表的 'i'：

[ [['i','o'],['o','o']] 
, [['o','i'],['o','o']] 
, [['o','o'],['i','o']] 
, [['o','o'],['o','i']] 
] 

以下是我嘗試過的方法：我想我需要使用地圖功能，因爲我需要遍歷每個元素，但我不知道如何執行，因爲地圖功能沒有跟蹤它的位置工作。

type Row = [Char] 
type Mappy = [Row] 

func :: Mappy -> [Mappy] 
func a = map (map someFunc a) a 

someFunc :: Mappy -> Char -> Mappy 
someFunc a b = if b == "o" 
       then undefined 
       else a 

顯然，我應該改變undefined，但我不知道如何。提前致謝。

Answer 1

拉鍊很棒，並且有一個有趣的博客文章 實施Conway's Game of Life using zippers and comonads in Haskell。在另一個 的手上，如果這仍然是你第一週學習Haskell，你可能想要在週四保存Comonads吧？

這是另一種使用簡單遞歸和列表 理解並且沒有複雜的Haskell功能的方法。

首先，假設我們有一個真棒功能：

varyOne :: (a -> [a]) -> [a] -> [[a]] 
varyOne = undefined 

的作品如下。給定一個函數f產生零個或 更多的元素a的變型，函數調用varyOne f xs 生成列表xs，從服用導致的所有變體 正好xs一個元素，說x在列表的中間，和更換它與f x給出的所有 變體。

此功能令人驚訝地靈活。它可以產生從由恆定強制替換元件產生的所有變體的列表：

> varyOne (\x -> [3]) [1,2,3,4] 
[[3,2,3,4],[1,3,3,4],[1,2,3,4],[1,2,3,3]] 

通過爲一個特定的值和變體的其他值的空列表返回一個單變體中，它可以生成所有的變體與'i'替換'o'同時抑制「變體」，其中沒有更換是可能的：

> let varyRow = varyOne (\c -> if c == 'o' then ['i'] else []) 
> varyRow "ooxo" 
["ioxo","oixo","ooxi"] 

和，因爲varyRow本身產生行的變體，它可以用varyOne可以用於產生表，其中一個特定的變體行已取代其可能的變體：

> varyOne varyRow ["ooo","oox","ooo"] 
[["ioo","oox","ooo"],["oio","oox","ooo"],["ooi","oox","ooo"], 
["ooo","iox","ooo"],["ooo","oix","ooo"], 
["ooo","oox","ioo"],["ooo","oox","oio"],["ooo","oox","ooi"]] 

事實證明，這真棒功能是非常容易寫：

varyOne :: (a -> [a]) -> [a] -> [[a]] 
varyOne f (x:xs) 
    = [y:xs | y <- f x] ++ [x:ys | ys <- varyOne f xs] 
varyOne _ []  = [] 

第一個列表理解產生當前元素的所有變種。第二個列表理解生成的變體涉及使用遞歸調用varyOne更改當前元素的權限。

鑑於varyOne，我們可以這樣定義：

replaceOne :: Char -> Char -> Mappy -> [Mappy] 
replaceOne old new = varyOne (varyOne rep1) 
    where rep1 x = if x == old then [new] else [] 

和：

> replaceOne 'o' 'i' ["ooo","oox","ooo"] 
[["ioo","oox","ooo"],["oio","oox","ooo"],["ooi","oox","ooo"] 
,["ooo","iox","ooo"],["ooo","oix","ooo"] 
,["ooo","oox","ioo"],["ooo","oox","oio"],["ooo","oox","ooi"]] 

可能是你正在尋找的功能。

如果你願意無條件與i更換一個單一的元素，不管是什麼老的因素是，那麼這將工作：

> varyOne (varyOne (const ['i'])) ["ooo","oox","ooo"] 
[["ioo","oox","ooo"],["oio","oox","ooo"],["ooi","oox","ooo"] 
,["ooo","iox","ooo"],["ooo","oix","ooo"],["ooo","ooi","ooo"] 
,["ooo","oox","ioo"],["ooo","oox","oio"],["ooo","oox","ooi"]] 

Answer 2

你想要什麼，年輕的BaasBartMans，是一個拉鍊。

data Zipper a = Zipper [a] a [a] 

ofList :: [a] -> Maybe (Zipper a) 
ofList [] = Nothing 
ofList (a:as) = Just (Zipper [] a as) 

拉鍊給你在列表中的位置的情況下，所以你 可以很容易地修改它們一次一個，前進或後退和這樣。

我們可以從拉鍊恢復列表：

instance Foldable Zipper where 
    foldr f c (Zipper ls a rs) = foldl' (flip f) (f a (foldr f c rs)) ls 

我們可以同時修改每個位置在拉鍊：

instance Functor Zipper where 
    fmap f (Zipper ls a rs) = Zipper (fmap f ls) (f a) (fmap f rs) 

或者只是聚焦元素：

here :: Functor f => (a -> f a) -> Zipper a -> f (Zipper a) 
here f (Zipper ls a rs) = fmap (\a' -> Zipper ls a' rs) (f a) 

並且作爲Zipper是Comonad，我們可以修改每個元素T：

instance Comonad Zipper where 
    extract (Zipper _ a _) = a 
    extend f z@(Zipper ls a rs) = Zipper ls' a' rs' where 
    a' = f z 
    ls' = unfoldr (fmap (\z' -> (f z', z')) . goLeft) z 
    rs' = unfoldr (fmap (\z' -> (f z', z')) . goRight) z 

利用這一點，我們可以構建修改上下文中的列表中的每個元素的功能：

λ everywhere (\a -> [a+1]) [10,20,30] 
[[11,20,30] 
,[10,21,30] 
,[10,20,31]] 

和嵌套表：這對於簡單的列表作品

everywhere :: Alternative f => (a -> f a) -> [a] -> f [a] 
everywhere f as = case ofList as of 
    Nothing -> pure [] 
    Just z -> asum $ extend (fmap toList . here f) z 

：

λ everywhere (everywhere (\a -> [a+1])) [[10], [20,20], [30,30,30]] 
[[[11],[20,20],[30,30,30]] 
,[[10],[21,20],[30,30,30]] 
,[[10],[20,21],[30,30,30]] 
,[[10],[20,20],[31,30,30]] 
,[[10],[20,20],[30,31,30]] 
,[[10],[20,20],[30,30,31]]]