用箭头比较列表长度

Question

受比较列表长度的启发

如果我想在列表列表中找到最长的列表,最简单的方法可能是:

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

一种更有效的方法是预先计算长度:

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

现在,我想更进一步.对于正常情况,它可能没有效率,但你能用箭头解决这个问题吗？我的想法基本上是,同时逐步浏览所有列表,并继续踩到你超越每个列表的长度,除了最长的.

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

在前面(非常人为的)示例中,您只需要在每个列表中执行两个步骤,以确定列表[1..2^1000]是最长的,而无需确定所述列表的整个长度.我是对的,这可以用箭头完成吗？如果是这样,那怎么样？如果没有,那么为什么不,以及如何实施这种方法？

Answer 1

再仔细考虑一下，有一个更简单的解决方案，可以提供相同的性能特征。我们可以使用maximumBy惰性长度比较函数：

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

longest = maximumBy compareLength