Reverse a list in haskell

Question

I am trying to reverse a list.

Following is my code:

reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) =  x:reverseList xs

What ends up happening is I end up getting the list back in same order. I even have a solution for how to reverse the list but I am trying to understand what I did wrong here ? I am very new to haskell so think I should focus on understanding more then I can solve more problems with ease. I know there are many solutions out there for this problem but I need more help in the understanding esp what I did wrong here in this code.

Answer 1

There are several ways to solve this problem in Haskell. The naive approach would be to use the concatenate function ++:

reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]

However, this will be really slow for large lists since Haskell lists are really singly linked lists, so in order to append an element you have to traverse the entire list. An alternative would be to keep up with the list you're building in a helper function:

reverseList = go []
    where
        go acc [] = acc
        go acc (x:xs) = go (x:acc) xs

However, this is really just the fold pattern:

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

But \acc x -> x : acc is just flip (:), so this can be written as

reverseList = foldl (flip (:)) []

However, the easiest way would probably be to just use the reverse function in Prelude.

I would like to point out that your type of reverseList :: [Int] -> [Int] could be generalized to :: [a] -> [a], you don't do anything special with the elements of the list, you're just building a new list with them.

Answer 2

You are separating the list into head and tail, but then re-assemble the list in the same order. Take the list [1, 2, 3] for example:

In the first call, x will be 1, and xs will be [2, 3]. Then you create a new list, consisting of x (so 1) at the front, followed by reverseList [2, 3].

Answer 3

There are several ways to solve this problem in Haskell. Here a solution with cons and last/init:

reverseList  [] = []
reverseList  xs = last xs : reverseList (init xs)

Or with foldl:

reverseList xs = foldl (\x y -> y:x) [] xs 

Answer 4

Basically the naive algorithm which uses appending

revList [] = []
revList (x:xs) = revList xs ++ [x]

is inefficient since appending is an O(n) operation where n is the length of the first (left) parameter of the ++ operator. So the revList function above turns out to be O(n(n-1)/2) ~ O(n^2).

So for such append heavy tasks there are the Difference List data type.

A difference list is just a list expressed as a function. What i mean is, a list like [1,2,3] when expressed in DList type would be \xs -> [1,2,3] ++ xs or in short ([1,2,3] ++)

type DList a = [a] -> [a]

toDList :: [a] -> DList a
toDList xs  = (xs ++ )

fromDList :: DList a -> [a]
fromDList f = f []

This is sort of cool because since DLists are functions we can append them by composition (.) operator and get a new DList. In other words toDList (xs ++ ys) == (toDList xs) . (toDList ys).

So how is this useful? By using nested function compositions we can reverse our list in a similar fashion to revList function but it will cost us much less. Only O(n) since every function composition is O(1).

revList' :: [a] -> DList a
revList' []     = toDList []
revList' (x:xs) = revList' xs . toDList [x]

Now that we have the reversed [a] in DList a type all we need to apply fromDList

fastReverse :: [a] -> [a]
fastReverse = fromDList . revList'

The Difference List data type is not as simple as i have shown above. It can have Monoid, Functor and MonadT instances. For more on this useful data type check Data.DList

Answer 5

Simple. use the built-in reverse function:

print (reverse [1,2,3,4,5]) -- [5,4,3,2,1]