整數列表中最長的子序列的長度

Question

我想在功能性編程方面做得很好，所以我爲自己設定了一些任務。

我想確定在整數列表，其中，下一個元件是遞增的最長子序列的長度。

所以結果應該是

incsubseq [] ~?= 0, 
incsubseq [5] ~?= 1, 
incsubseq [1,2,3,5,6] ~?= 3, 
incsubseq [5,6,1,2,3] ~?= 3, 
incsubseq [5,6,1,4,3] ~?= 2, 
incsubseq [6,5,4,3,2,1] ~?= 1] 

我的嘗試是這樣的：

incsubseq :: [Int] -> Int 
incsubseq [] = 0 
incsubseq [_] = 1 
incsubseq (a:b) 
      | a == ((head b)-1) = 1 + (incsubseq b) 
      | a /= ((head b)-1) = (incsubseq b) 

但當然這僅適用於列表沒有一個較長的序列如[1,2,3，42] = ，但不適用於像列表[1,2，]這應該是3，但是NOT（這是2）！

我真的很感激你的幫助，因爲這個問題讓我發瘋，來自OO編程。

Answer 1

您可以使用稱爲累加器的技術來解決此問題：您可以調用一個函數以及在運行時修改的某些值。基本情況然後返回用這些累加器計算的函數的結果。

對於這個特定的問題，我們介紹兩個累加器：curi和maxi。 curi存儲當前序列的長度，並且maxi包含迄今爲止所見的最大遞增序列。

的基本情況是，當我們到達列表的末尾在這種情況下，我們返回maxi：

maxincsub [] curi maxi = maxi 

另一個基本情況是，當我們遇到的最後一個元素。在這種情況下，我們返回的最大的maxi和curi：

maxincsub [_] curi maxi = max curi maxi 

電感的情況是，當我們在列表中看到兩個元素：我們確定a1是否是a2的增量。如果是這樣，我們增加curi。如果不是這樣，我們設置curi回1，而是先設定maxi最大的maxi這遠不及curi：

maxincsub (a0:a1:as) curi maxi | a0+1 == a1 = maxincsub (a1:as) (curi+1) maxi 
           | otherwise = maxincsub (a1:as) 1 (max curi maxi) 

或者把他們放在一起：

maxincsub [] curi maxi = maxi 
maxincsub [_] curi maxi = max curi maxi 
maxincsub (a0:a1:as) curi maxi | a0+1 == a1 = maxincsub (a1:as) (curi+1) maxi 
           | otherwise = maxincsub (a1:as) 1 (max curi maxi) 

最後，我們需要綁定你功能incsubseq與我們的maxincsub設置初始值爲curi和maxi：

incsubseq :: [Int] -> Int 
incsubseq xs = maxincsub xs 1 0 

與給定的輸入Tetsting這給：

*Main> incsubseq [] 
0 
*Main> incsubseq [5] 
1 
*Main> incsubseq [1,2,3,4,5,6] 
6 
*Main> incsubseq [1,2,3,5,6] 
3 
*Main> incsubseq [5,6,1,2,3] 
3 
*Main> incsubseq [5,6,1,4,3] 
2 
*Main> incsubseq [6,5,4,3,2,1] 
1 

Answer 2

您同時解決太多的問題 - 我會嘗試打破這個問題倒更易懂的步驟

1. 創造一切在列表中
2. 序列創建自己的length S使用map
3. 找到一個新的列表長度

現在，第一部分是容易的，如果您的序列是從Data.List「的所有同樣的事情」，那麼group就足夠了，但這裏不是這種情況了，可惜groupBy (\x y -> x + 1 == y)這將是完全的10你在找什麼 - 不起作用（由於技術原因我不想擴大）。

所以首先你需要實現自己的groupBy'功能或「欺騙」，並期待here在那裏我得到

groupBy :: (a -> a -> Bool) -> [a] -> [[a]] 
groupBy rel []   = [] 
groupBy rel (x:xs)  = (x:ys) : groupBy rel zs 
    where (ys,zs) = groupByAux x xs 
     groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs) 
      where (ys,zs) = groupByAux x xs 
     groupByAux y xs = ([], xs)

，那麼你可以簡單地groupBy (\x y -> x + 1 == y) [1,2,100,101,102]

然後下一步應該是可以管理的。

注意：如果你想要最長的序列，你可以創建一個快捷方式並使用maximumBy (compare `on` length)。

完整的解決方案：

import Data.Function (on) 
import Data.List (maximum) 

longestLength :: [Int] -> Int 
longestLength xx = maximum $ map length $ groupBy' (\x y -> x + 1 == y) xx 

groupBy = ... -- see above 

Answer 3

可以使用摺疊功能這種遞歸函數。

這可能不是慣用的，但這裏是我使用foldl的版本。

incsubseq [] = 0 
incsubseq (x:xs) = (\(a,_,_)->a) $ foldl update (1,1,x) xs 
    where 
     update (maxn,n,h) x 
      | h+1 /= x  = (maxn, 1, x) 
      | n+1 > maxn = (n+1, n+1, x) 
      | otherwise  = (maxn, n+1, x)