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

Lafras Uys lafras at aims.ac.za
Mon May 24 09:33:05 EDT 2010


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

>> 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

that should be,

import Data.List
init $ sort xs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkv6gBAACgkQKUpCd+bV+kq3aACfZFmIK3ChuVky9qWqLGYc2rrt
Np4An06oMtwCIu9pEYNumrX6N0Y5hFYn
=jKVY
-----END PGP SIGNATURE-----


More information about the Beginners mailing list