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

On Tuesday 25 May 2010 10:21:01, Chaddaï Fouché wrote:

On Mon, May 24, 2010 at 4:01 PM, Daniel Fischer

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 )