Efficient string swapping in Haskell

  • A+
Category:Languages

I'm trying to solve a problem for a functional programming exercise in Haskell. I have to implement a function such that, given a string with an even number of characters, the function returns the same string with character pairs swapped.

Like this:

"helloworld" -> "ehllworodl"

This is my current implementation:

swap :: String -> String swap s = swapRec s ""   where     swapRec :: String -> String -> String     swapRec [] result       = result     swapRec (x:y:xs) result = swapRec xs (result++[y]++[x]) 

My function returns the correct results, however the programming exercise is timed, and It seems like my code is running too slowly.

Is there something I could do to make my code run faster, or I am following the wrong approach to the problem ?

 


Yes. If you use (++) :: [a] -> [a] -> [a], then this takes linear time in the number of elements of the first list you want to concatenate. Since result can be large, this will result in a ineffeciency: the algorithm is then O(n2).

You however do not need to construct the result with an accumulator. You can return a list, and do the processing of the remaining elements with a recursive call, like:

swap :: [a] -> [a] swap [] = [] swap [x] = [x] swap (x:y:xs) = y : x : swap xs

The above also uncovered a problem with the implementation: if the list had an odd length, then the function would have crashed. Here in the second case, we handle a list with one element by returning that list (perhaps you need to modify this according to the specifications).

Furthermore here we can benefit of Haskell's laziness: if we have a large list, want to pass it through the swap function, but are only interested in the first five elements, then we will not calculate the entire list.

We can also process all kinds of list with the above function: a list of numbers, of strings, etc.

Note that (++) itself is not inherently bad: if you need to concatenate, it is of course the most efficient way to do this. The problem is that you here in every recursive step will concatenate again, and the left list is growing each time.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: