[Haskell-beginners] Removing the biggest element from a list - maybe slow?

[Chaddaï Fouché]

On Mon, May 24, 2010 at 4:01 PM, Daniel Fischer
<daniel.is.fischer at web.de> wrote:
> If you don't need to retain the order, you can efficiently do it with one
> traversal.
>
> withoutLargest [] = []
> withoutLargest (x:xs) = go x xs
>  where
>    go _ [] = []
>    go p (y:ys)
>      | p < y     = p : go y ys
>      | otherwise = y : go p ys
>

And to be explicit (Daniel implied that) this version is also much
more interesting from a memory point of view since it can start
producing the resulting list almost immediately, which means it can be
used as a filter in a lazy pipeline able to handle infinite or just
too big lists.

On the other hand, if you often need to perform this operation
(removal of the maximum) and don't care about the order, there are
much better data structures to do this, particularly the priority
queue. There are some good implementations of this on Hackage.

(NB : Many of those implementations only provide for removing the
minimum, but that only means that you have to change the definition of
minimum so that it be your maximum :
newtype FlipOrd a = FO a
instance (Ord a) => Ord (FO a) where
   compare (FO a) (FO b) = compare b a
)

-- 
Jedaï