How to find all minimum elements in a list of tuples?

Question

How can I find all the minimum elements in a list? Right now I have a list of tuples, i.e.

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

So I want the output which is all the minimum elements of the list, in a new list. For example

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

I tried

minimumBy (comparing fst) xs

but that only returns the first minimum element.

Mamiemamma

You calculate the minimum, and then you filter the list. – Psychoneurotic

Answer 1

After you obtain the minimum of the first value, we can filter the list on these items. Because you here want to retrieve a list of minimum items, we can cover the empty list as well by returning an empty list:

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

For example:

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

Psychoneurotic

Answer 2

Oneliner. The key is sorting.

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

Honig

Sorting takes O(n lg n) time, which is significantly slower than O(n) achieved by the minimum/filter combination. – Adriaadriaens

@Adriaadriaens you're forgetting about the laziness. :) – Patman

How does laziness guarantee that sortOn can produce the minimum value(s) in o(n lg n) time? (Although, I can probably answer my own question if a spend more than two seconds thinking about which sorting algorithm is used...) – Adriaadriaens

@Adriaadriaens that used to be a hot topic. take k . sort is O(n) (for small ks) when sort is lazy (on-line), like mergesort. When the first (minimal) element is found, only O(n) comparisons have been made, and the rest of tree of comparisons is yet to be explored. so it's O(k*n) for take n, and for a small fixed k it's O(n). – Patman

@Adriaadriaens (correction: for take k). but here the k isn't fixed, you ask? well, if k was large, that means we had nearly-sorted input and the sort itself was O(n). – Patman

@Adriaadriaens WP says mergesort's best case (i.e. on sorted input) is still n log n. that would be a facepalm, BUT, GHC's implementation almost surely does runs discovery, and with that, it's still O(n)! – Patman

OK, looking at the implementation in hackage.haskell.org/package/base-4.12.0.0/docs/src/…, it looks like at the first level it sorts an arbitrary number of sorted sequences, rather than recursively merging exactly two sorted sequences, so it's easier to believe that the O(n) bound holds even if I haven't fully digested the algorithm yet. – Adriaadriaens

@Adriaadriaens that's what I referred to as "runs discovery" (it's even smarter, discovering also the descending ones and reversing them as it goes -- if they didn't change anything since the last time I looked). it is done in O(n), and so if we're left with just one (non-decreasing) run, to finish up the sorting is an O(1) operation. (it's O(n) in the worst case (no runs).) – Patman

Answer 3

Here's a solution that works in one pass (most other answers here do two passes: one to find the minimum value and one to filter on it), and doesn't rely on how the sorting functions are implemented to be efficient.

{-# 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 []

Note that the [a] -> [a] type I'm using here is called a difference list, aka a Hughes list.

Killick

Answer 4

You can do it easily too with 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)

with your example:

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

Moro

I would expect this to cause minfst xs to be recomputed at each step, which is needlessly expensive. I'd rather remove the argument, and use ... where minfst = minimum (map fst xs). – Prudi

in any case this is reimplementation of filter, and minimum . map fst is reimplementation of fst . minimumBy (comparing fst). – Patman

if you're already re-implementing stuff with foldr, you could go one extra step and fuse the finding of the minimum in, as well. one foldr to do the whole job. :) – Patman

Answer 5

You tried

minimumBy (comparing fst) xs

which can also be written as

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

This returns just the first element instead of the list of them, so just drop that extra head to get what you want:

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

Of course having head is no good since it'll error out on the [] input. Instead, we can use the safe option,

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

By the way any solution that calls minimum is also unsafe for the empty input list:

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

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

but takeWhile is safe:

> takeWhile undefined []
[]

edit: thanks to laziness, the overall time complexity of the final version should still be O(n) even in the worst case.

Patman

Is there a good reference for this fact, aside from linking to the implementation? – Adriaadriaens

it should be under "k largest" or something. – Patman

It's also a little disturbing that Data.OldList appears to have the option to use insertion sort for sortBy (based the value of USE_REPORT_PRELUDE), although there doesn't seem to be any mention of sorting in the Haskell report (1998 or 2010). – Adriaadriaens

very impressive answer – Moro