Related Tags

arrays
communitycreator

How to reverse a list in Haskell

Algorithm

Haskell is a functional programming language where we can leverage recursion to reverse a list. This can be done by adding the first element ($x$) of the list at the end of the returning list, and calling the recursive function with the list ($xs$) that does not contain $x$.

Example

Lets look at an example where we will reverse the following list:

• ist = [1, 2, 3]

Iteration 1

• list = [1, 2, 3]

• x = 1

• xs = [2, 3]

returning_list = reverse_list(xs) ++ [1]


Iteration 2

• list = [2, 3]

• x = 2

• xs = [3]

returning_list = reverse_list(xs) ++ [2] ++ [1]


Iteration 3

• list = [3]

• x = 3

• xs = []

returning_list = reverse_list(xs) ++ [3] ++ [2] ++ [1]


Iteration 4

• list = []

• xs = []

returning_list = [] ++ [3] ++ [2] ++ [1]


Thus, the returning_list becomes = [3, 2, 1].

Code

The program below implements this algorithm in Haskell.

reverse_list :: [Int] -> [Int]
reverse_list = \list ->
case list of
[] -> []
x:xs -> reverse_list xs ++ [x]
main = print (reverse [1, 2, 3])`

RELATED TAGS

arrays
communitycreator

CONTRIBUTOR