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.

One lesson to pick up from here is that, you can do `1:[2,3,4]` but you **cannot** do `[2,3,4]:1`. The leftmost item in this array construction instruction requires that item to be an element and not an array. This is how haskell's way in this case and a core notion that newbies like me find very important to internalize and get used to. — daparic, Aug 04 '18 at 00:44

score 69 · Answer 1 · answered Nov 10 '14 at 15:40

69

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.

answered Nov 10 '14 at 15:40

bheklilr

53,530
6
107
163

4

Just for completeness, the lazy form `foldl'` is even better. – Pierre R Nov 10 '14 at 21:58
1

@PierreR Don't you mean the strict form? And I'm aware of it, I just was avoiding mentioning the extra import and the differences between the two, it's something I've explained too many times on SO ;) – bheklilr Nov 10 '14 at 22:04
1

Yes ... strict of course. I have no doubt you knew about it. Your SO answers are such a valuable help. Thanks for taking the time. – Pierre R Nov 11 '14 at 09:23
1

Your solution is better than the solution which uses concatenation (`++`). That solution uses $O(n^2)$ time for the concatenations, and $O(n)$ stack space because each concatenation needs the result of the left part to evaluate to weak head normal form. Your solution runs in $O(n)$ stack space still, as the `foldl` necessarily builds up a thunk of size $O(n)$ to evaluate to weak head normal form. The better solution would indeed be to use the strict `foldl'`, as it can run in constant stack space in this case. – justinpc Jan 25 '19 at 12:10
@justinpc what's with the "$"s? – Sapphire_Brick Jun 04 '20 at 15:28
1

@Sapphire_Brick it's latex notation, it indicates a mathy formula, similar to backticks that indicate code. – bheklilr Jun 05 '20 at 02:45
In your example, what's the idea behind writing `reverseList = go [] \n...` instead of `reverseList (x:xs) = go [] (x:xs) \n...`? How does it work? – Kukuster Apr 08 '21 at 08:48
@Kukuster if `foo = bar z` then `foo xs = bar z xs`. – Will Ness Aug 31 '21 at 08:56

score 8 · Accepted Answer · edited Jul 06 '18 at 20:25

8

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].

edited Jul 06 '18 at 20:25

dfeuer

48,079
5
63
167

answered Nov 10 '14 at 15:33

Michael Kohl

66,324
14
138
158

My bad, sorry. Corrected. – Michael Kohl Nov 10 '14 at 15:42
am i not doing the same thing because when i take out head i am inserting head first like x:reverseList xs – user1010101 Nov 10 '14 at 18:23

Twistleton · Answer 3 · 2018-07-06T15:29:18.263

7

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

edited Jul 06 '18 at 15:29

answered Jul 06 '18 at 12:16

Twistleton

2,735
5
26
37

2

You present these as two alternatives, but only one is an efficient solution! You should probably explain why that is. – dfeuer Jul 06 '18 at 20:27
I'm upvoting this because being a newbie in Haskell, I arrived to the same solution using `last` and `init`. It may not be the most efficient, but it reinforced my understanding of Haskell. – daparic Aug 01 '18 at 21:16
The second alternative is actually no more efficient than the first alternative. The function `foldl` is strict in the list argument and recurses over it. This means that in order to evaluate its result to weak head normal form, the whole list must be traversed first. That is fine, but this traversal results in the building of a thunk whose size is proportional to the size of the list, the evaluation of which can result in a stack overflow. This is because `foldl` is not strict in the accumulated value. The thunk can be forced to WHNF by using `foldl'`, which is struct in the accumulated val. – justinpc Jan 25 '19 at 12:03
1

@justinpc, you are wrong on two counts. Your main mistake is thinking that the second is as bad as the first. In fact, the second takes *linear* time while the first takes *quadratic* time. If you don't believe me, try some tests with a million elements, printing `last . rev $ [1..10^6]` using each implementation of `reverse`. If you don't understand *why*, I can try to explain. The second thing is that if optimizations are enabled then GHC will definitely not build any excess thunks for the `foldl` implementation. – dfeuer Jun 18 '19 at 17:54

score 2 · Answer 4 · answered Jun 18 '19 at 13:53

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

not quite (even though not incorrect). each function composition is indeed O(1) but what guarantee do we have about how long it takes for the composed function to do its work? the full answer is [here](https://stackoverflow.com/a/13879693/849891). :) — Will Ness, Aug 31 '21 at 09:02

Sapphire_Brick · Answer 5 · 2021-02-25T22:51:39.750

2

Simple. use the built-in reverse function:

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

edited Feb 25 '21 at 22:51

answered Jan 01 '20 at 00:47

Sapphire_Brick

1,560
12
26

score 0 · Answer 6 · edited Apr 22 '22 at 19:23

0

The reverse function was defined with list comprehension in Haskell.

rev1::  [a] -> [a]
rev1 xs = [xs !! (length xs - a)  | (a,b) <- zip [1..] xs]

edited Apr 22 '22 at 19:23

Chris

26,361
5
21
42

answered Apr 22 '22 at 19:15

ibrahim uğur Yılmaz

1

Gabe Itch · Answer 7 · 2022-11-22T14:50:18.780

0

This reverse function works with an accumulator and foldl.

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

This one uses recursion.

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

edited Nov 22 '22 at 14:50

answered Nov 22 '22 at 14:48

Gabe Itch

1
1

Reverse a list in haskell

7 Answers7

Linked