我怎么能得到一个以上的列表作为递归函数的输出称为列表的列表?

Question

我正在尝试使用一个递归函数，打印所有列表中具有最大长度的列表(如果它们具有相同的长度，可以是一个或多个)

给出如下输入:

[[],[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]]

输出应该包含两个最长的列表:

[3,4,5],[2,4,5]

下面的函数只打印第一个列表:[3,4,5]

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  = longest (x:lst)

注意:我必须使用回归

Answer 1

您可以使用累加器来跟踪到目前为止获得的最长项和列表的列表，因此:

longest :: [[a]] -> [[a]]
longest (x:xs) = go xs (length x) [x]
go [] _ ys = reverse ys
go (x:xs) n ys
| n' > n = go xs n' [x]
| n' == n = go xs n (x:ys)
| otherwise = go xs n ys
where n' = length x

Answer 2

我发现您的方法很复杂，因为您将在参数的开头累积结果，并且有必要进一步处理它。
考虑这个解决方案，它将未来的结果累积到第二个辅助参数中。

longest :: [[a]] -> [[a]]
longest lst = longest' lst [[]]
longest' :: [[a]]->[[a]]->[[a]] -- input, working state, output
longest' [] x = x --base case: if there's empty input return working state.
longest' (y:lst) x
| length (head x) < length y = longest' lst [y]
| length (head x) == length y = longest' lst (x++[y])
| otherwise = longest' lst x
inp = [[],[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]]
main = putStrLn $ show $ longest inp

输出:

[[3,4,5],[2,4,5]]

这种方法可以在Haskell的SO或标准库中看到:

longest lst = longest' lst [[]]
where 
longest' [] x = x --base case: if there's empty input return helper.
longest' (y:lst) x
| length (head x) < length y = longest' lst [y]
| length (head x) == length y = longest' lst (x++[y])
| otherwise = longest' lst x