On Mon, May 24, 2010 at 4:01 PM, Daniel Fischer
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ï