Reversing a list in Haskell

Totally bored and jobless over this surprisingly silent weekend, I decided to revisit some of the Haskell programs that I had written when I took the Functional programming course during the previous year. While I was at it, I remembered this particular topic which struck me as interesting back then (..and it still is). So I am going to write about it despite the fact that it is something that would be covered by any basic Haskell textbook or tutorial. Well, that just goes to show how jobless I am!

The first time we were asked to reverse a list in Haskell, I did it using the extremely straightforward method I could think of.

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

What we are doing here is, given a list of the form (x:xs) where x is the element at the head of the list and xs is the tail of the list (which is again a list!). We recursively apply revList to the tail and then concatenate the result with the singleton list containing the head x.

Turns out this really bad way of reversing a list.

Let us analyse why.

One of the ways of looking at a Haskell list, say [x,y,z,w] is
x:(y:(z:(w:[]))), reflecting the head:tail pattern mentioned earlier.

Observe that to append the element x at the end of the reversed list, we concatenate the reversed list with the singleton list [x]. Now, the concatenation of two lists even in Haskell is at best a linear time operation. One could think of a way of concatenating lists as follows

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

Thus the concatenation operation would have to walk to through the first list at least once.

Let T_{rev}(n) represent the time taken to reverse the list of n  elements. Clearly T_{rev}(0) = 0. And suppose T_{concat}(n_1, n_2) = n_1 represent the time taken to concatenate two lists where the size of the first list is n_1 and the size of the second list is  n_2. From the code, we can set up the following equation:

T_{rev}(n) = T_{rev}(n-1) + T_{concat}(n-1,1)
T_{rev}(n) = T_{rev}(n-1) + n-1 which solves to
T_{rev}(n) = \frac{(n-1)(n-2)}{2}

Thus T_{rev}(n) is quadratic in n. This is hardly the time complexity we would have liked!

The reason for this is the fact that appending a single element to a list takes linear time proportional to the length of the list. This is due to the manner in which lists are internally represented in Haskell.

However, adding an element to the head of the list is a constant time operation. The code for doing this would look something like:

add_to_head :: Int -> [Int] -> [Int]
add_to_head x l = (x:l)

Thus, given a list (x:(y:(z:(w:[])))) appending, say an element v to the head would amount to storing the list as v:(x:(y:(z:(w:[])))). Thus we don’t have to worry about the length of the list. In this sense, the Haskell list is similar to a stack. Adding an element to the top or removing an element from the top is a constant time operation. But adding to the bottom requires popping out all the elements, pushing this new element, and pushing all the elements (ok, lists do better than that.)

So, we can make use of this fact to optimize revList so that the operation takes linear time proportional to the length of the list. And the optimization would involve same trick that is used in reversing a stack. i.e pop out the element at head of the stack, push it into another stack, and repeat this till the first stack is empty. This requires only linear time.

listRevFast :: [a] -> [a]
listRevFast l = _listRevFast l []
    where
        _listRevFast :: [a] -> [a] -> [a]
        _listRevFast [] l = l
        _listRevFast (x:xs) l = _listRevFast xs (x:l)

And this one, you can verify requires linear time since it accesses each element of the original list exactly once.

Advertisements

About gautshen

A jack of many trades of which , Linux Kernel Programming puts food on the table. Also pursuing his PhD in the area Theoretical Computer Science at the Chennai Mathematical Institute. Is an avid reader interested in the Hindu traditions and philosophy. Loves Bicycling and Good Music. Name is Ranjal Gautham Shenoy.
This entry was posted in academia, geek, grad school, programming, tech and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s