Elem如何使用單個元素

Question

問題是將連續的列表元素重複打包到子列表中。 我不明白怎麼elem正在與這裏的單個元素，

例如，

pack [1,1,2,2,3,4] 

然後x爲1和(head (pack xs))將爲1 試問：

1 `elem` 1 

elem是a -> [a] -> Bool的類型？

此外，請解釋遞歸。

pack :: (Eq a) => [a] -> [[a]] 
pack [] = [] 
pack [x] = [[x]] 
pack (x:xs) = if x `elem` (head (pack xs)) 
       then (x:(head (pack xs))):(tail (pack xs)) 
       else [x]:(pack xs) 

Answer 1

在你的榜樣，x將是1，但head (pack xs)是不 1.實際上，你可以從它的類型簽名看到的pack xs的類型必須爲[[Int]]（或至少[[a]]爲某種a）即列表的列表的數字，所以head (pack xs)的類型爲[Int]，而不是Int。不管它的價值是什麼，它不能是1。

如果還不清楚，請看較短的示例pack [1,2]。它將匹配pack (x:xs)與x=1和xs=[2]的模式，因此elem呼叫的右側將爲head (pack [2])。您可以驗證這相當於head [[2]]計算結果爲[2]，現在的表情：

1 `elem` [2] 

非常有意義。

請記住，即使head返回列表的第一個元素，Haskell允許列表的列表，列表的第一個元素是另一個列表。

編輯：爲了解釋遞歸，讓我們詳細地通過pack [1,1,2]的完整示例。每當我們試圖評估pack通話時間，我們將使用它，我的編號爲圖案的pack一個：

pack [] = []    -- #1 
pack [x] = [[x]]   -- #2 
pack (x:xs) = if x `elem` (head (pack xs)) -- #3 
       then (x:(head (pack xs))):(tail (pack xs)) 
       else [x]:(pack xs) 

當哈斯克爾試圖評估pack [1,1,2]，因爲[1,1,2]相當於（如果你不看不出爲什麼，請查看:運算符的定義，並在幾個示例中試用！），它將模式＃3與x=1和xs=[1,2]匹配。因此，Haskell可以使用模式＃3的右側對這個值進行評估，這些替換值爲x和xs。只是要完全清楚，這些替代的RHS看起來像下面，我們稱之爲「表達（A）」：

if 1 `elem` (head (pack [1,2])) 
then (1:(head (pack [1,2]))):(tail (pack [1,2])) 
else [1]:(pack [1,2]) 

確保你相信這是繼續之前的權利！現在，評估這個表達最困難的部分是弄清楚如何評估在幾個地方使用的pack [1,2]。所以，讓我們弄清楚Haskell如何評估pack [1,2]。同樣，因爲[1,2]相當於1:[2]（請檢查它！），這與模式＃3匹配x=1和xs=[2]。的模式＃3與這些替代的RHS是下面的，我們稱之爲「表達（B）」：

if 1 `elem` (head (pack [2])) 
then (1:(head (pack [2]))):(tail (pack [2])) 
else [1]:(pack [2]) 

評價表達（B），我們需要弄清楚的pack [2]值。這一次，這個表達式將模式＃2與x=2匹配。 （實際上，它也會與模式＃3匹配，x=2和xs=[]，但Haskell使用匹配的第一個模式，所以它從不考慮這種可能性。）將x=2代入模式＃2的RHS，我們得到以下等效值pack [2] ，我們稱之爲「表達式（C）」，儘管它很短，但可能不值得一個名字。

[[2]] 

考慮這一點，將其代回上式（B），我們實際上得到：

if 1 `elem` (head [[2]]) 
then (1:(head [[2]])):(tail [[2]]) 
else [1]:[[2]] 

所有我在這裏所做的替換pack [2]與[[2]]無處不在它出現，然後我刪除一些額外的括號並未改變含義。 if語句中的條件與1 `elem` [2]相同，該條件爲false，因此該值爲[1]:[[2]]，可將其重寫爲[[1],[2]]。 （再次檢查一下你是否看不到原因。）這就是表達式（B）的最終值，所以最終值爲pack [1,2]。現在，我們可以這個值代入到表達式（A）來獲得：

if 1 `elem` (head [[1],[2]]) 
then (1:(head [[1],[2]])):(tail [[1],[2]]) 
else [1]:[[1],[2]] 

現在，因爲head [[1],[2]]只是[1]，在if語句中的條件是1 `elem` [1]這是真的，那麼哈斯克爾評估由給定的部分then條款。這是醜陋的，但你應該能夠說服自己，它的價值是：

(1:(head [[1],[2]])):(tail [[1],[2]]) 
= (1:[1]):[[2]] 
= [1,1]:[[2]] 
= [[1,1],[2]] 

這是表達（A）的終值，當然那是的pack [1,1,2]價值，所以你可以看到，這一切都奏效了。

Answer 2

正如chi已經評論過的那樣，使用head和tail通常是有問題的和模糊的。在你的例子中，它也會產生一個巨大的性能問題，因爲在每個遞歸步驟中，你一次又一次地計算pack xs--除非編譯器介紹了一些非平凡的優化，這個指數複雜度很高！

我推薦以下而是使用case和警衛：

pack (x:xs) = case pack xs of 
    thisPack : packs 
    | x `elem` thisPack -> (x:thisPack) : packs 
    otherPacks   -> [x] : otherPacks