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

[matthew coolbeth]

On Mon, May 24, 2010 at 09:27, 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
>
> This is not linear time.  It also doesn't maintain the order of the list.


> or
>
> import Data.List
> delete (maximum xs) xs
>

I don't think you are going to do better than this.  Just by the nature of
the problem, you need to go through the list twice:   either forward
initially and then backward during the "return phase" of your function, or
twice forward with a pair of tail-recursive operations.  The suggestion
above does the latter and, I believe, achieves optimal expenditures of both
time and space.


>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
>
> iEYEARECAAYFAkv6fqcACgkQKUpCd+bV+ko55wCbB/AVbb9OhfGK5ObsAc4yxVFH
> YigAnjudQlhBThF2IvUOjXFknAxBHUnN
> =XuKY
> -----END PGP SIGNATURE-----
> _______________________________________________
> 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/d9bd1dd4/attachment.html