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

[Felipe Lessa]

On Mon, May 24, 2010 at 04:47:50PM +0200, Daniel Fischer wrote:
> remLargest :: Ord a => [a] -> [a]
> remLargest [] = []
> remLargest [_] = []
> remLargest (x:xs) = go [] x xs
>   where
>     go post _ [] = reverse post
>     go post mx (y:ys)
>         | mx < y    =  mx : reverse post ++ go [] y ys
>         | otherwise = go (y:post) mx ys

Doesn't retain the order of the list:

  removeLargest (x:xs@(_:_)) = go x xs
    where
      go x []                  = []
      go x (x2:xs) | x < x2    = x  : go x2 xs
                   | otherwise = x2 : go x  xs
  removeLargest _ = []

Traverses only once, so it is O(n).

--
Felipe.