Haskell列表中的錯誤 - Intersection

Question

這是一個小問題，我真的不知道我錯在哪裏。我需要創建一個函數來顯示兩個列表的交集（沒有庫和列表理解）。好吧，我做了這個，很簡單，但我犯了一個錯誤，導致函數只返回兩個列表中的第一個元素。我知道這是一個愚蠢的錯誤。有人可以幫助我嗎？

這是函數：誤差

inter :: [Int] -> [Int] -> [Int] 
inter [] _ = [] 
inter _ [] = [] 
inter (x:xs) (y:ys) | (x == y) = x:[] 
        | otherwise = inter xs ys 

例如：（兩個列表）[1,2,4] [1,3,4]

返回只[1]時的正確是：[1,4]

Answer 1

您正在同時迭代兩個列表並停止在第一個公共元素。您需要查看列表成員資格並在找到第一個匹配元素後繼續。我會建議使用elem功能：

inter (x:xs) ys | elem x ys = ... 
       | otherwise = inter xs ys 

你需要填寫...這裏，我故意留空白爲你找出你需要做什麼。

在你的功能發生了什麼事情發生的是它會看到

inter (1:2:4:[]) (1:3:4:[]) 

它將分配x = 1, y = 1, xs = 2:4:[], ys = 3:4:[]，然後計算x == y，其計算結果爲True，所以選擇分支，返回x : []。或[1]。此時函數返回。它永遠不會檢查2 == 3或4 == 4。

Answer 2

假設：一組是排序列表在這裏。

您的代碼的工作原理如下：

inter :: [Int] -> [Int] -> [Int] 
inter [] _ = [] 
inter _ [] = [] 
inter (x:xs) (y:ys) | (x == y) = x:[]   -- if x == y, we stop? 
        | otherwise = inter xs ys -- can we drop both elements? 

頭兩行指出，「從目前的名單之一是[]，我們回到[]」。到現在爲止還挺好。

然後下一條線與兩名警衛一起工作。鑑於我們發現兩個頭是相等的（x == y），我們只需返回*一個項目列表[x]。這是不正確的：有可能在兩個尾部xs和ys中，仍有兩組都是項目。第二個守衛也是不正確的：如果x不等於y，那並不意味着我們可以扔掉這兩個元素：有可能x仍然在尾部ys，或者y仍然在xs某處。

然而，我們可以通過這兩個列表進行排序的事實來獲得一個相當有效的解決方案。在這種情況下，我們可以簡單地放棄兩者中的最小者。因爲如果ys已排序且x < y，我們知道ys中的所有元素也將大於x。

所以，一個解決方案，我建議是：

inter :: [Int] -> [Int] -> [Int] 
inter [] _ = [] -- left list is empty, stop 
inter _ [] = [] -- right list is empty, stop 
inter xa@(x:xs) ya@(y:ys) | x == y = x : inter xs ys -- both head same, continue 
          | x < y = inter xs ya  -- left less, step left 
          | otherwise = inter xa ys -- right less, step right

的@是這裏的別名。 xa@(x:xs)意味着我們參考了整個列表xa和頭部x和尾部xs。

通常一個目標是儘可能在Haskell作爲通用：現在我們必須實施列表的inter有Int S，String S等不是很優雅。我們可以概括如下：

inter :: Ord a => [a] -> [a] -> [a] 
inter [] _ = [] 
inter _ [] = [] 
inter xa@(x:xs) ya@(y:ys) | x == y = x : inter xs ys 
          | x < y = inter xs ya 
          | otherwise = inter xa ys