Как найти все минимальные элементы в списке кортежей?

Question

Как мне найти все минимальные элементы в списке? Прямо сейчас у меня есть список кортежей, то есть

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

Так что я хочу вывод, который является всеми минимальными элементами списка, в новом списке. Например,

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

Я пытался

minimumBy (comparing fst) xs

, но это возвращает только первый минимальный элемент.

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')]

Answer 2

Вот решение, которое работает за один проход (большинство других ответов здесь делают два прохода: один для поиска минимального значения и один для его фильтрации), и не полагаются на то, как функции сортировки реализованы для обеспечения эффективности.

{-# 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] называется списком различий , он же списком Хьюза .

Answer 3

Oneliner. Ключ сортировки.

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')]

Answer 4

Вы пытались

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 нехорошо, так как произойдет ошибка на входе []. Вместо этого мы можем использовать опцию safe,

= 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 []
[]

edit: , благодаря лени, общая временная сложность окончательной версии все равно должна быть O (n) даже в худшем случае.

Answer 5

Вы можете сделать это тоже легко с помощью 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')]