如何在哈斯克尔的列表中获取最短列表

Question

这个函数，它接受列表列表并返回最短的列表（如果列表列表为空，则返回一个空列表）

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

最短 ：： [[a]]

-> [a]

我是Haskell的新手，任何帮助将不胜感激谢谢

Answer 1

前奏> ：m +数据列表
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 .

最后，我们需要使用该顺序来实际选择最小元素。执行该技巧的功能是 Data.List.minimumBy .

---

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

Answer 2

我想

扩展@leftaroundabout提出的解决方案。

Prelude Data.List Data.Function> minimumBy (compare `on` (map . const $ 1)) [[1..],[5..11],[3,4]]

与原始解决方案不同，这个解决方案绝对适用于无限列表。

Answer 3

shortest [y] = y    --base case: if there's only one element left, return it.
shortest (x:y:lst)  --extract the first two elements x, y from the list.  
    | length x > length y = *recursion*  
    | otherwise = *recursion*

您可以使用递归来解决此问题。我基本上为您列出了结构，但您应该考虑如何实现递归部分。请记住，递归发生在函数调用自身时。

提示：使用冒号将最短的元素连接回原始列表，以便您可以将其与列表中的下一个元素进行比较。

希望对您有所帮助！

Answer 4

首先，您需要从 Data.Ord 进行比较

import Data.Ord

然后给出最小值通过按长度比较的比较函数

minimumBy (comparing (length)) [[1,2,9],[3,4],[1,2,3,5]]