比较列表长度

Question

我有一份清单,让我们说:

import Data.List

xs = [[1,2], [1,2,3], [2,3]]

在这种情况下,我想获得包含最多项目的内部列表[1,2,3].

我试图使用maximumBy功能从Data.List库:

maximumBy (compare `on` length) xs

但是我收到以下错误: not in scope 'on'

任何人都可以告诉我出了什么问题,或者你有更好的方法来获取清单吗？

Answer 1

on在Data.Function中定义,因此您需要导入它.

另外,您也可以使用comparing从Data.Ord:

maximumBy (comparing length) xs

Answer 2

在使用maximumBy与comparing length或compare `on` length将做的工作就好了短名单,请注意,这不是一个非常有效的解决方案,如果列表很长,因为每次算法比较两个列表,它会重新计算它们的长度.

例如,如果我们有一个非常长的第一个列表,后面跟着许多短列表,使用maximumBy将非常慢,因为将在每个步骤重新计算第一个列表的长度.

> import Data.List
> import Data.Ord
> let xs = replicate 50000 'a' : replicate 50000 "b"
> maximumBy (comparing length) xs
<snip>
(16.09 secs, 98338680 bytes)

我们可以通过缓存列表的长度来获得更有效的解决方案:

> let longest xss = snd $ maximumBy (comparing fst) [(length xs, xs) | xs <- xss]
> longest xs
<snip>
(0.35 secs, 91547296 bytes)

当然,如果你的名单很小,这可能不会有很大的不同,但值得注意.