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

[Daniel Fischer]

On Monday 24 May 2010 14:42:28, Nathan Huesken wrote:
> Hi,
>
> I want to remove the biggest element from a list:
>
> withoutBiggest (x:xs) =
>   withoutBiggestImpl (biggest x xs) [] (x:xs)
>     where
>       biggest :: (Ord a) => a -> [a] -> a
>       biggest big [] = big
>       biggest big (x:xs) =
>         if x > big then
>           biggest x xs
>         else
>           biggest big xs
>       withoutBiggestImpl :: (Eq a) => a -> [a] -> [a] -> [a]
>       withoutBiggestImpl big before (x:xs) =
>         if big == x then
>           before ++ xs
>         else
>           withoutBiggestImpl big (before ++ [x]) xs
>

Just to make sure, you are aware that this removes only the first 
occurrence of the largest element if there are several?


In that code, collecting the before-list is
a) unnecessary
b) inefficient
Re b), consider the list [1 .. n] for some large n.
Then you have

wBI n [] [1 .. n]
~> wBI n ([]++[1]) [2 .. n]
~> wBI n (([] ++ [1]) ++ [2]) [3 .. n]
~> wBI n ((([] ++ [1]) ++ [2]) ++ [3]) [4 .. n]
~> ...
~> wBI n ((...((([] ++ [1]) ++ [2]) ++ [3]) ...) ++ [n-1]) [n]
~> ((...((([] ++ [1]) ++ [2]) ++ [3]) ...) ++ [n-1])

And:
Prelude> let func :: Int -> Int; func n = last (foldl (\xs k -> xs ++ [k]) 
[] [1 .. n])
(0.00 secs, 524224 bytes)
Prelude> func 5000
5000
(0.44 secs, 351528996 bytes)
Prelude> func 10000
10000
(2.63 secs, 1404077120 bytes)
Prelude> func 20000
20000
(20.03 secs, 5613242020 bytes)

Ouch.

The short code to achieve the same is (as has been posted before)

import Data.List

withoutBiggest [] = []
withoutBiggets xs = delete (maximum xs) xs

That also traverses the list twice, but is much faster because it doesn't 
build a left-nested chain of (++)-applications.
Like your code, it requires the entire list to be in memory though.

If you need the elements in the original order (except the first occurrence 
of the maximum), you can't completely eliminate that memory requirement, 
though you can reduce it somewhat on average (ugly code, not more efficient 
than delete (maxumum xs) xs in general, worst case considerably slower).

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

>
> Works, but I am a little concerned that this is
> slower than needed, because the list has to be iterated twice.
>
> Can this be done faster?
>
> Regards,
> Nathan