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

[Markus Läll]

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!