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

[Nathan Huesken]

On Mon, 24 May 2010 15:27:03 +0200
Lafras Uys <lafras at aims.ac.za> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> > 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
> > 
> > 
> > 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?
> 
> import Data.List
> init sort xs
> 
> or
> 
> import Data.List
> delete (maximum xs) xs

I see. I would think, the first solution takes still to much time
because it needs to sort the list.

Is "delete" a fast operation (O(1))? or does it internally traverse
the list?

Thanks!
Nathan