如何使用递归找到最大长度的列表？

Question

我正在尝试使用递归函数打印列表，该列表具有由我的以下代码产生的列表的最大长度：

allincreasing :: Ord a => [a] -> [[a]]
allincreasing =  map nub  . filter isSorted . subsequences

main = do
print $ allincreasing[3,2,6,4,5,1]

我需要将下面的输出传递给找到最大长度的递归函数：

[[],[3],[2],[6],[3,6],[2,6],[4],[3,4],[2,4],[5],[3,5],[2,5],[4,5],[3,4,5],[2,4,5],[1]]

基于我对这个问题答案的理解，我尝试使用以下代码来实现它，但我无法很好地实现递归部分。以下是我的尝试：

 longest :: Ord a => [[a]] -> [a]
 longest [y] = y    --base case: if there's only one element left, return it.
 longest (x:y:lst) --extract the first two elements x, y from the list.  
   | length x < length y = longest (y:lst)
   | otherwise  = x : (longest (y:lst))


  lis :: Ord a => [a]  -> a 
  lis = length . longest . allincreasing

注：我需要使用递归来解决最长递增序列的问题。

Answer 1

当您想跟踪存根以及递归时（就像到目前为止的最大列表一样...）可以使用累加器（您可以在此处阅读有关它们的信息...）：

由于评论请求而编辑：

module Main where
import Data.List

isSorted :: (Ord a) => [a] -> Bool
isSorted []       = True
isSorted [x]      = True
isSorted (x:y:xs) = x <= y && isSorted (y:xs)

allincreasing :: Ord a => [a] -> [[a]]
allincreasing =  map nub  . filter isSorted . subsequences

main :: IO ()
main = do

   
    let list = [3,2,6,4,5,1]
    print $ allincreasing list
    print $  longest $ allincreasing list



longest :: Ord a => [[a]] -> [a]
longest list = longest' list [] 
    where
        longest' [] acc = acc
        longest' (x:xs) [] = longest' xs x
        longest' (x:xs) acc 
            | length acc >= length x = longest' xs acc
            | length acc < length x = longest' xs x
        longest' _ _ = error "something went wrong..."