Haskell列表中元素的最長連續系列

Question

我是函數式編程和語言haskell的新手。我試圖根據謂詞函數確定列表中最長連續的一系列元素的長度。該功能看起來是這樣的：

longestSequence :: (a -> Bool) -> [Int] -> Int 

當我這樣稱呼它：

longestSequence (\x -> x >= 10) [1,44,33,22,2,3,55,66,66,77,88,99] 

應該給我的解決方案6。

我的解決辦法，直到卻又是：

longestSequence :: (a -> Bool) -> [a] -> Int 
longestSequence p [] = 0 
longestSequence p (x:xs) 
    | (p x) = 1 + (longestSequence p xs) 
    | otherwise = longestSequence p xs 

任何提示或如何解決這個問題的想法？

Answer 1

嘗試分解較小的子問題。對於這個例子，一般的策略可能是這樣的：

1. 轉換給定的列表爲[Bool]列表，其中的條目是True如果相應的條目滿足謂詞。這是寫功能(Int -> Bool) -> [Int] -> [Bool]
2. 組連續True和False值。那是寫一個函數[Bool] -> [[Bool]]。你可能想看看Data.List.group。
3. 篩選出False組：[[Bool]] -> [[Bool]]
4. 對於每個內部列表計數它們的長度。 [[Bool]] -> [Int]
5. 找出最大的長度：[Int] -> Int

然後你只需撰寫這些功能，和你做。對於1.和4.你會想使用功能map :: (a -> b) -> [a] -> [b]。如果你已經知道map，就使用它。如果你不這樣做，我會建議你自己寫。

我給出的一些函數類型簽名過於具體。也許儘量在一定程度上概括它們。

Answer 2

在警衛中，p x和otherwise部分都有問題。

(p x) = 1 + (longestSequence p xs)並不總是正確的，如果X的下一個元素不持有預測p，它不能被添加在當前最長序列比保持一個

長1

​​是不正確的

一個可能的解決辦法是保持最大長度和當前長度

longestSequence :: (a -> Bool) -> [a] -> Int 
longestSequence p x = ls x 0 0 
    where 
    ls [] mx cur = max mx cur 
    ls (x:xs) mx cur 
     | p x = ls xs mx (cur+1) 
     | otherwise = ls xs (max mx cur) 0 

Answer 3

您可以經常使用fold比遞歸簡單，該類別中我們希望使用scanl，它就像foldl一樣，只是它保留了整個列表。

下面的代碼循環遍歷列表，遞增與謂詞匹配的每個項目的計數。如果發現一個不匹配的數字，它會將計數重置爲零。最後，它找到最終的結果列表。

longestSequence p = maximum . scanl (\count x -> if (p x) then count + 1 else 0) 0 

對於[1,44,33,22,2,3,55,66,66,77,88,99]您的示例輸入和(\x -> x >= 10)謂詞，則scanl將產生的的輸出。取得這個列表的最大值給出6，你可以看到最大值出現在輸入的末尾，也是列表中謂詞不匹配的零。

順便說一句，我完全同意jpath關於將問題分解成小部分。我看到人們用fold解決類似的問題，用\count參數中的max計算用一個元組填充，但是這使得閱讀變得更加困難。順便說一句，這也是使像你一樣的單功能遞歸解決方案難以繞開頭的原因。太多需要一次跟蹤，因此很難看到在哪裏以及如何適應復位到零部分。