¿Cómo encontrar todos los elementos mínimos en una lista de tuplas?

haskell minimum

Question

¿Cómo puedo encontrar todos los elementos mínimos en una lista? En este momento tengo una lista de tuplas, es decir

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

Entonces, quiero la salida que es todos los elementos mínimos de la lista, en una nueva lista. Por ejemplo

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

Lo intenté

minimumBy (comparing fst) xs

pero eso solo devuelve el primer elemento mínimo.

Answer 1

Aquí hay una solución que funciona en una pasada (la mayoría de las otras respuestas aquí hacen dos pasadas: una para encontrar el valor mínimo y otra para filtrarlo), y no se basa en cómo se implementan las funciones de clasificación para ser eficientes.

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

Tenga en cuenta que el tipo [a] -> [a] que estoy usando aquí se llama lista de diferencias , también conocida como lista de Hughes .

Answer 2

Después de obtener el mínimo del primer valor, podemos filtrar la lista en estos elementos. Debido a que aquí desea recuperar una lista de elementos mínimos, también podemos cubrir la lista vacía devolviendo una lista vacía:

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

Por ejemplo:

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

Answer 3

Intentaste

minimumBy (comparing fst) xs

que también se puede escribir como

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

Esto devuelve solo el primer elemento en lugar de la lista de ellos, así que simplemente suelte esa head extra para obtener lo que desea:

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

Por supuesto, tener head no es bueno ya que generará un error en la entrada [] . En cambio, podemos usar la opción segura,

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

Por cierto, cualquier solución que llame al minimum tampoco es segura para la lista de entrada vacía:

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

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

pero takeWhile es seguro:

> takeWhile undefined []
[]

editar: gracias a la pereza, la complejidad del tiempo general de la versión final debería ser O (n) incluso en el peor de los casos.

Answer 4

También puedes hacerlo fácilmente con 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)

con tu ejemplo:

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

Answer 5

Un trazador de líneas. La clave está ordenando.

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