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

[matthew coolbeth]

It is linear time, implemented roughly as below

delete z [] = []
delete z (x:xs) =  if x=z then delete z xs else x:(delete z xs)


On Mon, May 24, 2010 at 09:42, Nathan Huesken <haskell at lonely-star.org>wrote:

> 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
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 
mac
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100524/5d6000ee/attachment.html