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

[Daniel Fischer]

On Tuesday 25 May 2010 10:21:01, Chaddaï Fouché wrote:
> 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.

Yes. Very much yes.
Unless you need to perform this operation really 
often but never (or almost never) need to insert new values. 
Then sortBy (flip compare) once and repeatedly tail afterwards may be 
even better than a priority queue.

>
> (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
> )