Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Reverse a list in haskell

Tags:

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.

like image 807
user1010101 Avatar asked Nov 10 '14 15:11

user1010101


People also ask

How do you reverse a tuple in Haskell?

Wherever you have your code to form the list of tuples, encapsulate that code in a reverse function using brackets (reverse(code)) or reverse $ <code> and the result will be the reverse. Hope this helps!

What does Elem do in Haskell?

Elem Function This function is used to check whether the supplied list contains a specific element or not. Accordingly, it either returns a true or a false. The following code checks whether the supplied list of elements contains the value 786.

How do you remove the last element in a list in Haskell?

items. pop_back(); Removes last element from items, without returning anything.

What is last Haskell?

The last method gets the last element of a Haskel list. A Haskell list can be of any data type, a string of letters, an array of numbers, etc.


1 Answers

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.

like image 174
bheklilr Avatar answered Oct 26 '22 22:10

bheklilr