Comparing list length with arrows

Question

Inspired by Comparing list length

If I want to find the longest list in a list of lists, the simplest way is probably:

longestList :: [[a]] -> [a]
longestList = maximumBy (comparing length)

A more efficient way would be to precompute the lengths:

longest :: [[a]] -> [a]
longest xss = snd $ maximumBy (comparing fst) [(length xs, xs) | xs <- xss]

Now, I want to take it one step further. It may not be more efficient for normal cases, but can you solve this using arrows? My idea is basically, step through all of the lists simultaneously, and keep stepping until you've overstepped the length of every list except the longest.

longest [[1],[1],[1..2^1000],[1],[1]]

In the forgoing (very contrived) example, you would only have to take two steps through each list in order to determine that the list [1..2^1000] is the longest, without ever needing to determine the entire length of said list. Am I right that this can be done with arrows? If so, then how? If not, then why not, and how could this approach be implemented?

Answer 1

Thinking about this some more, there is a far simpler solution which gives the same performance characteristics. We can just use maximumBy with a lazy length comparison function:

compareLength [] [] = EQ
compareLength _  [] = GT
compareLength [] _  = LT
compareLength (_:xs) (_:ys) = compareLength xs ys

longest = maximumBy compareLength

Answer 2

OK, as I was writing the question, it dawned on me a simple way to implement this (without arrows, boo!)

longest [] = error "it's ambiguous"
longest [xs] = xs
longest xss = longest . filter (not . null) . map (drop 1) $ xss

Except this has a problem...it drops the first part of the list and doesn't recover it!

> take 3 $ longest [[1],[1],[1..2^1000],[1]]
[2,3,4]

Needs more bookkeeping :P

longest xs = longest' $ map (\x -> (x,x)) xs

longest' []   = error "it's ambiguous"
longest' [xs] = fst xs
longest' xss  = longest . filter (not . null . snd) . map (sndMap (drop 1)) $ xss

sndMap f (x,y) = (x, f y)

Now it works.

> take 3 $ longest [[1],[1],[1..2^1000],[1]]
[1,2,3]

But no arrows. :( If it can be done with arrows, then hopefully this answer can give you someplace to start.

Answer 3

Here's the most straightforward implementation I could think of. No arrows involved, though.

I keep a list of pairs where the first element is the original list, and the second is the remaining tail. If we only have one list left, we're done. Otherwise we try taking the tail of all the remaining lists, filtering out those who are empty. If some still remain, keep going. Otherwise, they are all the same length and we arbitrarily pick the first one.

longest []  = error "longest: empty list"
longest xss = go [(xs, xs) | xs <- xss]
  where go [(xs, _)] = xs
        go xss | null xss' = fst . head $ xss
               | otherwise = go xss'
               where xss' = [(xs, ys) | (xs, (_:ys)) <- xss]