On Mon, May 24, 2010 at 09:27, Lafras Uys
-----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@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- mac