functional programming - 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.