I’m on the 5th problem of 99 haskell problems. The first attempt went something like this

rev :: [a] -> [a]
rev (x:xs) = rev xs ++ x
rev [] = []

Let’s analyze this one. Assume we call the function as

rev [1,2,3]

rev (x:xs) matches 1: [2,3], so we have rev [2,3] ++ 1. Similarly, we’ll have rev[3] ++ 2 ++ 1 and then finally rev [] ++ 3 ++ 2 ++ 1. The whole thing can be shown as

step 1: rev [1,2,3]
step 2: rev [2,3] ++ 1
step 3: rev [3] ++ 2 ++ 1
step 4: rev [] ++ 3 ++ 2 ++ 1

This gives

[] ++ 3 ++ 2 ++ 1

which is

[3, 2, 1]

Okay, moving forward. Next attempt at writing the function involves usage of foldl. So, here we go

rev xs = foldl (\acc x -> x : acc) [] xs

The foldl function takes the accumulator and an element from the list. The element is prepended onto the accumulator. Which goes like

rev [1,2,3]
step 1: acc = [], 1 : acc
step 2: acc = [1], 2 : acc
step 3: acc = [2,1] , 3 : acc
step 4: acc = [3,2,1]

and thus, we get [3,2,1] as result from this.

Now, notice the lambda function. The parameters on left and right are flipped, so why not use the flip function and take advantage of currying?

rev xs = foldl (flip (:)) [] xs

And finally, using point free notation, we can write

rev = foldl (flip (:)) []

Pretty nifty, eh.

### Like this:

Like Loading...

*Related*