給定串列，將其分解為彼此相鄰的相同專案的串列：
[1,1,2,4,5,5]?[[1,1], [2], [4], [5,5]].
我需要使用遞回而不是高階函式來做到這一點。
這是我到目前為止所得到的
breakList :: [Int] -> [[Int]]
breakList [] = [[]]
breakList [x] = [[x]]
breakList (x:y:rest)
| x == y = [x] : breakList (y:rest)
| otherwise = [x] : breakList rest
但它不起作用。
uj5u.com熱心網友回復：
您可以檢查遞回呼叫結果的第一項是否具有相同的值。如果是這種情況，我們在該串列前面加上x，否則我們x以串列的唯一成員開始一個“新組” ，因此[x]：
breakList :: Eq a => [a] -> [[a]]
breakList [] = []
breakList [x] = [[x]] -- (1)
breakList (x:xs) -- (2)
| x == y = (x:ys) : yss -- (3)
| otherwise = [x] : ys : yss -- (4)
where ~(ys@(y:_):yss) = breakList xs -- (5)在這里我們首先計算尾遞回的結果，我們知道這將是非空的，因為(x:xs)(2) 中的模式只會在串列包含至少兩個專案時觸發（如果它只包含一個專案，那么 ( 1) 條款將觸發。
然后，我們可以將結果與模式~(ys@(y:_):yss)進行模式匹配，其中ys是結果的第一個子串列，y是該子串列的第一項，并且yss是已構造的其他組的串列（可能為空）。
因此，我們可以檢查x我們必須放入一個組中的專案y是否與第一個子組的第一個專案具有相同的值。如果是這種情況，我們將(x:ys) : yss用來構造一個新的 lsit，在其中我們在第一個子串列前面加上x(2)；如果不是這種情況，我們在子串列前面加上一個串列[x]來創建一個新組。
我們可以通過以下方式讓它變得更懶惰：
breakList :: Eq a => [a] -> [[a]]
breakList [] = []
breakList [x] = [[x]] -- (1)
breakList (x:xs@(y:_)) -- (2)
| x == y = (x:ys) : yss -- (3)
| otherwise = [x] : ys : yss -- (4)
where ~(ys:yss) = breakList xs -- (5)這也可以在每次相同物件的無限串列上作業：breakList (1 : 1 : 2 : 4 : 5: 5 : repeat 1))將產生[[1,1],[2],[4],[5,5],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, …
uj5u.com熱心網友回復：
這是一個替代解決方案，它在遍歷串列期間使用串列作為輔助資料結構。
這個輔助資料結構存盤了迄今為止的相等元素。對于每個新元素 (1) 我們檢查它是否等于輔助串列中的元素之一，如果是我們將其添加到該串列中，否則 (2) 我們輸出輔助串列作為結果并開始一個新的輔助串列列出這個新元素。在最后（3），我們簡單地輸出我們現在得到的輔助串列作為最終結果。
breakList :: [Int] -> [[Int]]
breakList [] = []
breakList (x:xs) = go [x] xs where
go ys [] = [ys] -- (3)
go ~ys@(y:_) (x:xs)
| x == y = go (x:ys) xs -- (1)
| otherwise = ys : go [x] xs -- (2)
如果您希望它穩定，即所有元素必須保持相同的順序（在整數的情況下這無關緊要，但對于其他資料型別可能如此），那么您必須反轉輸出串列：
breakList :: [Int] -> [[Int]]
breakList [] = []
breakList (x:xs) = go [x] xs where
go ys [] = [reverse ys]
go ~ys@(y:_) (x:xs)
| x == y = go (x:ys) xs
| otherwise = reverse ys : go [x] xs
該演算法還假設它==是可傳遞的，這在技術上不是必需的，但對于整數來說肯定是這種情況。雖然，如果==不是可傳遞的，您給出的規范是模棱兩可的，我們應該將每個新元素與哪個元素進行比較？組的第一個元素，還是前一個元素？無論如何，這可能不是您必須擔心的。
uj5u.com熱心網友回復：
這是group已經在做的。:) 顯然，它非常謙遜地定義為group (x:xs) = (x:ys) : group zs where (ys,zs) = span (x ==) xs.
當然，您被禁止使用 HOF，因此需要行內span. 并且它必須足夠懶惰，即盡可能早地生產盡可能少的輸入。
就像是
breakList :: [Int] -> [[Int]]
breakList [] = [[]]
breakList (x:ys) = (x:xs):r
where
(xs:r) = go x ys
go x (y:ys)
| x==y = ((y:a):b)
| otherwise = [] : ((y:a):b)
where (a:b) = go y ys
go _ [] = [[]]
所以我們有
> breakList $ [1,1,1,2,3,3,4]
[[1,1,1],[2],[3,3],[4]]
> take 1 . head . breakList $ repeat 1
[1]
> take 3 . head . breakList $ [1,1,1] undefined
[1,1,1]
似乎確實很懶惰。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/316821.html