in Haskell ~ read.

Ways to reverse a list in Haskell

Reversing a link list is never an out-dated topic while doing interview. Here I just want to summarize a few ways to reverse a link list by using Haskell, and show some of important logic of functional programming.

Some remarks about Haskell's list type

A list in Haskell can be represented as:

data List a = EmptyList  
            | ListElement a (List a)

The EmptyList constructor is used to represent the end of the link list and the List a here can be viewed as a pointer to its next node.

Using recursive function

The instinct of such problem is to write a function to reverse the rest of the list given and append the first element at the end of the reversed list.

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

A way to boost this method in the imperative programming is that: since the ending of the new reversed list is the element that the first element points to, you can keep a record of that pointer and directly append it to the end of the list without actually go through the entire list to reduce the time cost to O(n).

Using built in high-order function

Haskell have built in type for list recursion, and we can inject some high-order function into the foldl and foldr to get the ideal list we want. Notice the difference between foldl and foldr's order of function combination so their high order function injected is slightly different.

reverse_foldr :: [a] -> [a]  
reverse_foldr s = foldr (\x xs -> xs ++ [x]) [] s 

reverse_foldl :: [a] -> [a]  
reverse_foldl s = foldl (\xs x -> x:xs) [] s  

Using two different pass styles

In functional programming, there is an important concept called "tail recursion", which means that the operation being done during each recursive function call is identical, so the compiler automatically optimize the code into a loop form that will takes no extra storage for the call stack. There are mainly two ways to perform the tail recursion: the accumulating pass style and the continuation pass style.

The main idea of the accumulating pass style is to put the partial result as the parameter of the function calls. As we can see from the example below:

reverse_APS :: [a] -> [a]  
reverse_APS s = reverse_APS_helper s []  
        reverse_APS_helper [] t = t
        reverse_APS_helper (x:xs) t = reverse_APS_helper xs (x:t)  

In this piece of code, t is just the parameter used as the accumulative parameter.

The continuation pass style is another way of performing tail recursion but in a much complex manner. From my perspective, what CPS does is to write an entire call stack in a continuation function, and such continuation will tell you what is needed to be done after each step of the recursion call.

reverse_CPS :: [a] -> [a]  
reverse_CPS s = reverse_CPS_helper id s  
        reverse_CPS_helper f [] = f []
        reverse_CPS_helper f (x:xs) = reverse_CPS_helper (
                \t -> f(t++[x])
            ) xs 

The f here is the continuation function. Although it might seem meaningless for packing the string concat into the function, the CPS style can perform much more difficult logic then we can imagine.

Using Y-combinator

The starting idea of the functional programming can be traced back to the idea of lambda calculus, which has the equal computability as the Turing Machine. Among all the techniques of the lambda calculus, one of the most interesting thing is that you can define a recursion of anonymous function by using a combinators such as the famous Y-combinator, which has the property of for given function f, Y(f)=f(Y(f)). In other words, Y-combinator can return the fixed point of any given function, which enables us to do the recursion. I'll discuss more about Y-combinator and lambda calculus in my later articles. Here is a small demo of using Y combinator to do the list reverse.

y f = f (y f)  
reverse_Y = y $ \f s -> case s of  
    [] -> []
    c:cs -> (f cs) ++ [c]
comments powered by Disqus