How can I get more than one list as an output of recursive function called on list of lists?-CodePudding

I am trying to use a recursive function that prints all lists that has the maximum length out of the lists ( could be one or more if they have the same length)

given an input such as :

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

the output should contain both the longest lists :

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

My following function prints only the first list: [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)

Note: I must used recuersion

CodePudding user response：

You can use accumulators to keep track of the thus far obtained longest item and the list of lists for this, so:

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

CodePudding user response：

I find your approach complicated in that you will accumulate the result at the beginning of the parameter, and it is necessary to work with it further.
Consider this solution, which accumulates the future result into a second auxiliary parameter.

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

Output:

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

This approach you can see in Haskell on the SO or in the standard libraries in this design:

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