Reverse list in haskell
I am trying to modify the list.
Below is my code:
reverseList :: [Int] -> [Int]
reverseList [] = []
reverseList (x:xs) = x:reverseList xs
As a result, I get the list in the same order. I even have a solution for how to change the list, but I am trying to figure out what I did wrong here? I am very new to haskell, so I think I should focus on understanding more than I can solve more problems with ease. I know there are many solutions for this problem, but I need more help understanding esp, what did I do wrong here in this code.
source to share
There are several ways to solve this problem in Haskell. A naive approach would be to use the concatenation function ++
:
reverseList [] = []
reverseList (x:xs) = reverseList xs ++ [x]
However, for large lists, this will be very slow, since Haskell lists are really linked lists, so to add an element you have to go through the whole list. An alternative would be to keep up with the list you are building in the helper function:
reverseList = go []
where
go acc [] = acc
go acc (x:xs) = go (x:acc) xs
However, this is really just a pattern fold
:
reverseList = foldl (\acc x -> x : acc) []
But \acc x -> x : acc
simple flip (:)
, so it can be written as
reverseList = foldl (flip (:)) []
However, the simplest way would probably be to just use the function reverse
in the Prelude.
I would like to point out that your type reverseList :: [Int] -> [Int]
can be generalized to :: [a] -> [a]
, you don't do anything special with the list items, you just build a new list with them.
source to share
Basically a naive algorithm that uses the addition
revList [] = []
revList (x:xs) = revList xs ++ [x]
inefficient, since addition is an operation O(n)
where n
is the length of the first (left) operator parameter ++
. So the revList
above function revList
turns out to be O (n (n-1) / 2) ~ O (n ^ 2).
So there is a Difference List data type for such complex tasks.
The list of differences is just a list expressed as a function. I mean that a list of type [1,2,3]
in an expression like DList will be of the form \xs → [1,2,3] ++ xs
or shorter([1,2,3] ++)
type DList a = [a] -> [a]
toDList :: [a] -> DList a
toDList xs = (xs ++ )
fromDList :: DList a -> [a]
fromDList f = f []
This is cool because DList are functions, we can add them using the composition operator (.) And get a new DList. In other words toDList (xs ++ ys) == (toDList xs). (toDList ys)
toDList (xs ++ ys) == (toDList xs). (toDList ys)
.
So how is this useful? Using the composition of nested functions, we can reverse our list in a similar way to a function, revList
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 inverse of [a]
the DList a
type, all we need to apply fromfromDList
fastReverse :: [a] -> [a] fastReverse = fromDList . revList'
source to share