[Haskell-beginners] Removing the biggest element from a list -
maybe slow?
Markus Läll
markus.l2ll at gmail.com
Tue May 25 11:30:25 EDT 2010
Here is an ugly one:
remLargest2 [] = []
remLargest2 (li:st) = if something_bigger_in_tail then (li:result) else result
where ismax [] previous = ([], False)
ismax (current:rest) previous =
case (current_is_bigger_than_previous,
but_something_even_bigger_in_tail) of
(True, True) -> (current:newRest, True)
(False, True) -> (current:newRest, True)
(False, False) -> (current:newRest, False)
(True, False) -> ( newRest, True) -- current
is the biggest, lets leave it out
where f = ismax rest
current_is_bigger_than_previous = current > previous
(newRest, but_something_even_bigger_in_tail) =
if current_is_bigger_than_previous then f current
else f previous
(result, something_bigger_in_tail) = ismax st li
Besides the long names, could this be done somehow shorter?
The idea of it is to carry the maximum in 'previous' and compare it
with every element when recursing the list. When recursion reaches the
end, it starts to return, and on every step it tells the previous step
if there was something bigger down it's road of recursion or not. This
way every step knows if to drop its 'current' element -- this drop
happens only once.
So the steps it takes are defenitely 2n, because it rolls out, and
then has to return all the way -- even to get the first element
(because for it theres the question: "drop it or not?").
The order-not-retaining functions thus far are faster, taking only n steps.
The performance of Daniels remLargest depends on the order of elements
in the list: best case is if the list is grows like (=<), so there's
no use of an accumulator and concatenation: worst case is when the
list is composed of strictly descending lists -- then the time it
takes is 3n (n for traversing the list, n for reversing all sublists
and n for concatenating).
Cool problem ;-)
And we should do tests!
More information about the Beginners
mailing list