Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is (reverse . f . reverse) efficient?

Tags:

haskell

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?

like image 229
Snoqual Avatar asked Aug 22 '11 18:08

Snoqual


People also ask

What is the most efficient way to reverse an array?

Using Swapping Instead, we reverse the original array itself. In this method, we swap the elements of the array. The first element is swapped with the last element. The second element is swapped with the last but one element and so on.

Which data structure is efficient for reverse of a string?

The fastest way would be to use the reverse() method on the StringBuilder or StringBuffer classes :) You could also run half the array length and swap the chars, the checks involved slow things down probably. Save this answer.

What is the fastest way to reverse a string in Java?

By Using StringBuilder StringBuilder or StringBuffer class has an in-build method reverse() to reverse the characters in the string. This method replaces the sequence of the characters in reverse order. The reverse method is the static method that has the logic to reverse a string in Java.


2 Answers

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.

like image 139
hammar Avatar answered Nov 16 '22 04:11

hammar


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.

like image 31
wnoise Avatar answered Nov 16 '22 04:11

wnoise