如何在元组列表中找到所有最小元素？

Question

如何找到列表中的所有最小元素？目前我有一个元组列表，例如：

[(10,'a'),(5,'b'),(1,'c'),(8,'d'),(1,'e')]

我希望你能够将列表中的所有最小元素放入一个新列表中进行输出。例如：

 [(1,'c'),(1,'e')]

我尝试过

minimumBy (comparing fst) xs

但这只返回第一个最小元素。

- llamaro25

---

你先计算最小值，然后再筛选列表。 - Willem Van Onsem

Answer 1

在获取第一个值的最小值后，我们可以根据这些项筛选列表。因为您想要检索最小项的列表，所以我们可以通过返回空列表来处理空列表：

minimumsFst :: Ord a => [(a, b)] -> [(a, b)]
minimumsFst [] = []
minimumsFst xs = filter ((==) minfst . fst) xs
    where minfst = minimum (map fst xs)

例如：

Prelude> minimumsFst [(10,'a'),(5,'b'),(1,'c'),(8,'d'),(1,'e')]
[(1,'c'),(1,'e')]

- Willem Van Onsem

Answer 2

一句话总结，关键是排序。

Prelude Data.List> let a = [(1,'c'),(2,'b'),(1,'w')]
Prelude Data.List> (\xs@((m,_):_) -> takeWhile ((== m) . fst ) xs) . sortOn fst $ a
[(1,'c'),(1,'w')]

- user933161

---

排序需要O(n lg n)的时间，这比最小值/过滤器组合实现的O(n)要慢得多。 - chepner

@chepner，你忘记了懒惰性。 :) - Will Ness

懒惰如何保证sortOn能够在O(n lg n)的时间内产生最小值？（虽然，如果我花费超过两秒钟思考使用了哪种排序算法，我可能可以回答自己的问题...） - chepner

@chepner WP说归并排序的最佳情况（即在已排序的输入上）仍然是n log n。这可能会让人感到尴尬，但是GHC的实现几乎肯定会运行发现，并且使用它，它仍然是O(n)! - Will Ness

好的，看一下 https://hackage.haskell.org/package/base-4.12.0.0/docs/src/Data.OldList.html 上面的实现，它似乎在第一层对任意数量的排序序列进行排序，而不是递归地合并两个已排序的序列，因此更容易相信即使我还没有完全消化算法， O(n)的边界仍然成立。 - chepner

Answer 3

这里有一个一次通过的解决方案（大多数其他答案都需要两次通过：一次查找最小值，一次过滤），并且不依赖于排序函数的实现方式来提高效率。

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Foldable (foldl')

minimumsBy :: forall a. (a -> a -> Ordering) -> [a] -> [a]
minimumsBy _ [] = []
minimumsBy f (x:xs) = postprocess $ foldl' go (x, id) xs
  where
    go :: (a, [a] -> [a]) -> a -> (a, [a] -> [a])
    go acc@(x, xs) y = case f x y of
      LT -> acc
      EQ -> (x, xs . (y:))
      GT -> (y, id)
    postprocess :: (a, [a] -> [a]) -> [a]
    postprocess (x, xs) = x:xs []

请注意，这里使用的[a] -> [a]类型被称为差异列表，也称为Hughes列表。

- Joseph Sible-Reinstate Monica

Answer 4

你也可以通过 foldr 轻松地实现这个功能：

minimumsFst :: Ord a => [(a, b)] -> [(a, b)]
minimumsFst xs = go (minfst xs) xs
  where
  go mn ls = foldr (\(x, y) rs -> if (x ==  mn) then (x,y) : rs else rs) [] xs
  minfst ls = minimum (map fst ls)

使用您的示例：

   minimumsFst [(10,'a'),(5,'b'),(1,'c'),(8,'d'),(1,'e')]
=> [(1,'c'),(1,'e')]

- developer_hatch

---

我预计这会导致 minfst xs 在每一步都被重新计算，这是不必要的昂贵操作。我宁愿删除该参数，并使用 ... where minfst = minimum (map fst xs)。 - chi

无论如何，这都是过滤器的重新实现，而 minimum . map fst 是 fst . minimumBy (comparing fst) 的重新实现。 - Will Ness

如果你已经在使用foldr重新实现代码，你可以再进一步将查找最小值也融合进去。只需一个foldr就能完成整个任务。 :) - Will Ness

Answer 5

你进行了尝试

。

minimumBy (comparing fst) xs

这也可以写成

= head . sortBy (comparing fst) $ xs
= head . sortOn fst $ xs
= head . head . group . sortOn fst $ xs
= head . head . groupBy ((==) `on` fst) . sortOn fst $ xs

这只返回第一个元素而不是它们的列表，因此只需删除额外的 head 即可获得所需结果。

=        head . groupBy ((==) `on` fst) . sortOn fst $ xs

当然，使用head是不好的，因为它会在输入[]时出错。相反，我们可以使用安全选项。

= concat . take 1 . groupBy ((==) `on` fst) . sortOn fst $ xs

顺便提一下，任何调用minimum的解决方案对于空输入列表也是不安全的：

> head []
*** Exception: Prelude.head: empty list

> minimum []
*** Exception: Prelude.minimum: empty list

但是takeWhile是安全的:

> takeWhile undefined []
[]

编辑：由于懒惰，最终版本的总时间复杂度即使在最坏情况下仍应为O(n)。

- Will Ness

---

除了链接到实现之外，是否有关于这个事实的好参考资料？ - chepner

应该将翻译后的文本放在“k largest”或类似位置。 - Will Ness

还有一点令人不安的是，Data.OldList似乎有使用插入排序进行sortBy操作的选项（基于USE_REPORT_PRELUDE的值），尽管在Haskell报告（1998或2010）中似乎没有提到排序。 - chepner

非常出色的答案。 - developer_hatch