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

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

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

-- mac