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

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 2

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