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

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.