Comparing list length with arrows

Question

Inspired List Length Comparison

If I want to find the longest list in a list of lists, perhaps the easiest way:

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

A more efficient way would be to precompute the length:

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

Now I want to take it one step further. This may not be effective in ordinary cases, but can you solve this with the arrows ? My idea basically is to go through all the lists at the same time and continue to take a step until you exceed the length of each list except the longest.

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

In the previous (very far-fetched) example, you only need to perform two steps on each list to determine that the list [1..2^1000] is the longest, without having to determine the entire length of the specified list. Is it right that this can be done with arrows? If so, how? If not, then why not, and how can this approach be implemented?

Answer 1

Thinking about this yet, there is a much simpler solution that gives the same performance characteristics. We can simply use maximumBy with a function to compare lazy lengths:

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

Answer 2

OK, when I wrote the question, I understand a simple way to implement this (without arrows, boo!)

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

Except for this problem ... it discards the first part of the list and does not restore it!

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

More bookkeeping required: P

 longest xs = longest' $ map (\x -> (x,x)) xs longest' [] = error "it ambiguous" longest' [xs] = fst xs longest' xss = longest . filter (not . null . snd) . map (sndMap (drop 1)) $ xss sndMap f (x,y) = (x, fy) 

Now it works.

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

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

Answer 3

Here is the simplest implementation that I could think of. However, there were no arrows.

I keep a list of pairs where the first element is the original list and the second is the remaining tail. If we have only one list left, we are done. Otherwise, we will try to take the tail of all the other lists, filtering out those that are empty. If anyone else remains, continue. Otherwise, they have the same length, and we arbitrarily choose the first.

 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]