6

灵感来自比较列表长度

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

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]是最长的，而无需确定所述列表的整个长度。我可以用箭头来完成吗？如果是这样，那怎么办？如果不是，那为什么不呢？如何实施这种方法？

4

3 回答 3

4

好的，当我写这个问题时，我突然想到了一种实现这个的简单方法（没有箭头，嘘！）

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

除了这有问题......它会删除列表的第一部分并且不会恢复它！

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

需要更多簿记：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)

现在它起作用了。

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

但没有箭头。:( 如果它可以用箭头来完成，那么希望这个答案可以给你一个开始的地方。

于 2011-10-11T18:58:42.397 回答
3

这是我能想到的最直接的实现。不过，没有涉及箭头。

我保留了一个对列表，其中第一个元素是原始列表，第二个是剩余的尾部。如果我们只剩下一个列表，我们就完成了。否则，我们尝试取所有剩余列表的尾部，过滤掉那些为空的。如果还有一些，请继续。否则，它们都是相同的长度，我们随意选择第一个。

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]
于 2011-10-11T19:05:29.997 回答
3

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

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

longest = maximumBy compareLength
于 2011-10-11T20:59:17.117 回答