Is (reverse . f . reverse) efficient?

Question

Many times I see functions which operate on the head of a list, e.g:

trimHead ('\n':xs) = xs
trimHead xs        = xs

then I see the the definition:

trimTail = reverse . trimHead . reverse

then I see:

trimBoth = trimHead . trimTail

They are clean, but are trimTail and trimBoth efficient? Is there a better way?

Answer 1

Consider this alternative implementation

trimTail2 [] = []
trimTail2 ['\n'] = []
trimTail2 (x:xs) = x : trimTail2 xs

trimBoth2 = trimHead . trimTail2

It's easy to confirm that trimTail and trimBoth require that the entire list be evaluated, while trimTail2 and trimBoth2 only evaluate as much of the list as is necessary.

*Main> head $ trimTail ('h':undefined)
*** Exception: Prelude.undefined
*Main> head $ trimBoth ('h':undefined)
*** Exception: Prelude.undefined
*Main> head $ trimTail2 ('h':undefined)
'h'
*Main> head $ trimBoth2 ('h':undefined)
'h'

This implies that your version is going to be less efficient if the whole result is not needed.

Answer 2

Assuming the whole list is to be evaluated (if you don't need the whole list, why are you trimming the end?), it's about half as efficient as you can get out of immutable lists, but it has the same asymptotic complexity O(n).

The new list requires at least:

1. You have to find the end: n pointer traversals.
2. You have to modify the end, and thus what points to the end, etc.: n cons of existing data with new pointers.

reverse . trimHead . reverse performs roughly twice this:

1. The first reverse performs n pointer traversals and n cons.
2. trimHead possibly performs 1 pointer traversal.
3. The second reverse performs n pointer traversals and n cons.

Is this worth worrying about? In some circumstances, maybe. Is the code too slow, and is this called a lot? In others, maybe not. Benchmark! The implementation with reverse is nice and easy to understand, and that's important.

There is a fairly natural recursive step-through-the-list solution, which will only evaluate as much of the output as is consumed, so in the case that you don't know whether you need the whole string, you can possibly save some evaluation.