問題理解非遞歸列表理解concat in haskell

Question

你好我目前正在爲考試而學習，並且在回答題目時遇到問題，因爲題目狀態，目標是使用理解列表創建一個非遞歸的concat函數，看的解決方案是：

concat3 :: [[a]] -> [a] 
concat3 xss = [x | xs <- xss, x <-xs] 

但我不明白爲什麼這樣的作品，任何幫助，將不勝感激。

Answer 1

列表理解箭頭(<-)可以被讀爲「in」，就像[x | xs <- xss, x <- xs]這樣讀取「x for xs in xss and x in xs」，它表示我們將list列表中的每個列表解壓到它的組成元素這有點像concat。

雖然有許多方法可以查看此。

---

機械，列表內涵轉化爲do符號

do xs <- xss 
    x <- xs 
    return x 

和do符號轉化爲(>>=)和(>>)

xss >>= \xs -> xs >>= \x -> return x 

然後(>>=)本身變成concatMap和return至(\x -> [x])當我們在列表上實例化它們時。

concatMap (\xs -> concatMap (\x -> [x]) xs) xxs 

，如果你想concatMap (\x -> [x])，你可能會看到它作爲越過名單，同時每個元素的單列表，然後串聯他們...這只是任何無所事事的複雜的方式。

concatMap id xss 

，並從concatMap定義，我們有

concat (map id xss) 

最後只（從仿函數法！或常識）

concat xss 

所以它不應該是不足爲奇的該功能就像concat那樣工作。

---

什麼解釋do符號，我們傾向於認爲語義在「名單單子」的時候？

do xs <- xss 
    x <- xs 
    return x 

在本質上，這可以被解讀爲「選擇非確定性來自我們的列表中，列出的成分列表中的一個，然後選擇非確定性從該列表中的內容之一 - 收集所有的可能性從這個程序「，這又導致了我們只是串聯的想法。

---

我們也可以採取一個幸運的對應關係從Control.Monad功能join

join    :: (Monad m) => m (m a) -> m a -- this looks `concat`-like! 
join x   = x >>= id 

如果我們考慮到內xs >>= \x -> return x然後用eta-conversion我們xs >>= return這僅僅是"right identity" monad law，幫助我們看到，

xss >>= \xs -> xs >>= \x -> return x 
=== 
xss >>= \xs -> xs >>= return 
=== 
xss >>= \xs -> xs 
=== 
xss >>= id 
=== 
join xss 

，然後我們可以查找如何instan tiate join在列表monad中，並參見join = concat。

---

所以有很多方式看到concat爲通過列表解析來實現，這取決於你想怎麼想的列表內涵。很大一部分是這些都是等價的，並且可以相互構建，以形成列表及其monad實例真正意義的基礎。

Answer 2

您可以將列表理解描繪爲嵌套循環。所以，

[ z | x <- list1, y <- list2 ] 

手段「爲list1每個x，爲list2每個y，產量z」，並將得到的名單全部產生價值的，以集合。請注意，在這裏，值得產生的值z首先在符號中出現。所以，如果我們有：

[ (x,y) | x <- [1,2], y <- [3,4,5] ] 

這上面說， 「在[1,2]每個x，爲[3,4,5]每個y，產量(x,y)」，因此，我們得到：

[ (1,3), (1,4), (1,5), -- when x = 1 
    (2,3), (2,4), (2,5) ] -- when x = 2 

配有列表助記符理解，我們可以閱讀您的concat3定義。

concat3 xss = [ x | xs <- xss, x <- xs ] 

我要重命名變量，使其更易於閱讀：

concat3 listOfLists = [ x | list <- listOfLists, x <- list ] 

現在，我們可以看這是「在listOfLists每個list，在list每個x，產生x 」。也就是說，從第一個列表中獲取所有元素，然後從第二個列表中獲取所有元素，依此類推，這對應於連接所有列表。

我用的命名不太可能在野外看到。通常使用「複數」名稱，以s結尾，表示用於表示列表的變量。發音xs作爲「exes」發音。把語言類比也許太過分了（但它仍然是常見的慣例），我們「列出雙倍列表」列表，xss。我通常不會發音，因爲「發音」聽起來太愚蠢了。所以你可以看到xss是一個列表的列表，而xs是一個列表，你可以幫助讀取這些密集的表達式。