On Monday 24 May 2010 14:42:28, Nathan Huesken wrote:
Hi,
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
Just to make sure, you are aware that this removes only the first occurrence of the largest element if there are several? In that code, collecting the before-list is a) unnecessary b) inefficient Re b), consider the list [1 .. n] for some large n. Then you have wBI n [] [1 .. n] ~> wBI n ([]++[1]) [2 .. n] ~> wBI n (([] ++ [1]) ++ [2]) [3 .. n] ~> wBI n ((([] ++ [1]) ++ [2]) ++ [3]) [4 .. n] ~> ... ~> wBI n ((...((([] ++ [1]) ++ [2]) ++ [3]) ...) ++ [n-1]) [n] ~> ((...((([] ++ [1]) ++ [2]) ++ [3]) ...) ++ [n-1]) And: Prelude> let func :: Int -> Int; func n = last (foldl (\xs k -> xs ++ [k]) [] [1 .. n]) (0.00 secs, 524224 bytes) Prelude> func 5000 5000 (0.44 secs, 351528996 bytes) Prelude> func 10000 10000 (2.63 secs, 1404077120 bytes) Prelude> func 20000 20000 (20.03 secs, 5613242020 bytes) Ouch. The short code to achieve the same is (as has been posted before) import Data.List withoutBiggest [] = [] withoutBiggets xs = delete (maximum xs) xs That also traverses the list twice, but is much faster because it doesn't build a left-nested chain of (++)-applications. Like your code, it requires the entire list to be in memory though. If you need the elements in the original order (except the first occurrence of the maximum), you can't completely eliminate that memory requirement, though you can reduce it somewhat on average (ugly code, not more efficient than delete (maxumum xs) xs in general, worst case considerably slower). If you don't need to retain the order, you can efficiently do it with one traversal. withoutLargest [] = [] withoutLargest (x:xs) = go x xs where go _ [] = [] go p (y:ys) | p < y = p : go y ys | otherwise = y : go p ys
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?
Regards, Nathan