Reverse a list in haskell

haskell reverse list foldl
haskell list
haskell reverse list implementation
haskell reverse list recursively
reverse (string haskell)
foldl haskell
palindrome haskell
haskell rest of list

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.

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

Haskell : reverse, Module: Prelude. Function: reverse. Type: [a] -> [a]. Description: creates a new string from the original one with items in the reverse order. Related:� Reversing a link list is never an out-dated topic while doing interview. Here I just want to summarize a few ways to reverse a link list by using Haskell, and show some of important logic of functional programming. Some remarks about Haskell's list type. A list in Haskell can be represented as:

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.

Ways to reverse a list in Haskell, Here I just want to summarize a few ways to reverse a link list by using Haskell, and show some of important logic of functional programming. The union function returns the list union of the two lists. For example, >>> "dog" `union` "cow" "dogcw" Duplicates, and elements of the first list, are removed from the the second list, but if the first list contains duplicates, so will the result. It is a special case of unionBy, which allows the programmer to supply their own equality test.

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 

Reversing a list in Haskell, The first time we were asked to reverse a list in Haskell, I did it using the extremely straightforward method I could think of. revList :: [a] -> [a] Dim ItemList As New List(Of String)(New String() {"one", "two", "three"}) ItemList.Reverse() For Each item In ItemList Console.WriteLine(item) Next

Simple; use the built-in reverse function:

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

List reversing, List reversing. The below Haskell program to reverse a list appears in Haskell: The Craft of Functional Programming, by S. Thompson, page 156. Central to the� List reversing The below Haskell program to reverse a list appears in Haskell: The Craft of Functional Programming, by S. Thompson, page 156.Central to the program is the list catenation operator ++.

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

Hoogle lookup of reverse, 99 questions/Solutions/5. From HaskellWiki. < 99 questions | Solutions. Jump to: navigation, search. (*) Reverse a list� ZVON > References > Haskell reference: Intro / Search creates a new string from the original one with items in the reverse order

99 questions/Solutions/5, Declarative reverse. The declarative definition answers the question: what is the reverse of a list? It depends on the list. If it is empty, then its� Each element, , of the list is displayed on a separate line. Output Format. The output is the reverse of the input list. Sample Input. 19 22 3 28 26 17 18 4 28 0 Sample Output. 0 28 4 18 17 26 28 3 22 19 Method Signature. Number Of Parameters: 1 Parameters: [list] Returns: List or Vector Constraints. For Hackers Using Clojure

Making Haskell run fast: the many faces of reverse, the reverse function on lists. reverse :: [a] → [a] reverse [] = [] reverse (x:xs) = reverse xs ++ [x] reverse maps the empty list to the empty list, and any non-empty list� The Haskell Report defines no laws for Eq. However, == is customarily expected to implement an equivalence relationship where two values comparing equal are indistinguishable by "public" functions, with a "public" function being one not allowing to see implementation details. For example, for a type representing non-normalised natural numbers

[PDF] PROGRAMMING IN HASKELL, I have to perform an operation on every other element of the list starting from the list beforehand or reversing it, performing the operation, and reversing again. Well, you could say that if we split a list to a head and a tail, the reversed list is equal to the reversed tail and then the head at the end. reverse' :: [a] -> [a] reverse' [] = [] reverse' (x:xs) = reverse' xs ++ [x] There we go! Because Haskell supports infinite lists, our recursion doesn't really have to have an edge condition.

Comments
  • 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.
  • My bad, sorry. Corrected.
  • am i not doing the same thing because when i take out head i am inserting head first like x:reverseList xs
  • Just for completeness, the lazy form foldl' is even better.
  • @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 ;)
  • 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.
  • 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.
  • @Sapphire_Brick it's latex notation, it indicates a mathy formula, similar to backticks that indicate code.
  • You present these as two alternatives, but only one is an efficient solution! You should probably explain why that is.
  • 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.
  • 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, 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.