On Mon, May 24, 2010 at 09:27, Lafras Uys
<lafras@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-----