list - 如何在haskell的列表中获取最短列表

Question

此函数接受列表列表并返回最短的列表(如果列表列表为空，则返回空列表)

例如 最短 [[1,2,9],[3,4],[1,2,3,5]] 会返回 [3,4]

最短::[[a]] -> [a]

我是 haskell 的新手，我们将不胜感激 谢谢

Answer 1

Prelude> :m +Data.List
Prelude Data.List> :m +Data.Function
Prelude Data.List Data.Function> minimumBy (compare`on`length) [[1,2,9],[3,4],[1,2,3,5]]
[3,4]

它是如何工作的——嗯，minimum 是很明显的。但是我们不想按默认的字典顺序比较数字列表，而是想指定确切比较的属性——即长度。 compare`on`ᴘʀᴏᴘᴇʀᴛʏ 是一个简单易记的通用技巧，它使用

Data.Function.on :: (b->b->c) -> (a->b) -> a->a->c
compare :: Ord a => a -> a -> Ordering

所以 (compare`on`) 是 Ord b => (a->b) -> a->a->Ordering，即我们得到一个比较如果我们可以提供产生可比较属性的函数，则可以为任何数据类型创建函数。在我们的例子中，它是 length。

最后，我们需要使用该顺序来实际选择最小元素。起作用的函数 is Data.List.minimumBy .

---

请注意，此解决方案并不是很有效:它会对每个列表应用 length 多次。您不应该使用它来寻找数千个列表中的最短列表，每个列表都有数百个元素。当然存在更好的算法，但它们并不那么简单和简洁。