- A+

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(n*.

^{2})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.