Concatenation with (++)
Maybe I'm thinking to deep into this but,
as far as I understand, if you try to concatenate
lists using (++)
for example:
[1, 2, 3] ++ [4, 5]
(++)
has to traverse the complete left list.
Taking a look at the code of (++) makes it
all the more clear.
(++) :: [a] -> [a] -> [a]
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
Thus, it would be desirable to avoid using (++)
, since with every call
reverse(xs)++[x]
the list is getting bigger (or smaller depending
on the point of view. Anyways, the program simply has to traverse another
list with every call)
Example:
Lets say I implement reverse as proposed through concatenation.
reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs)++[x]
Reversing a list [1, 2, 3, 4] would look somewhat like this:
reversex [1, 2, 3, 4]
reversex [2, 3, 4] ++ [1]
reversex [3, 4] ++ [2] ++ [1]
reversex [4] ++ [3] ++ [2] ++ [1]
reversex [] ++ [4] ++ [3] ++ [2] ++ [1]
[] ++ [4] ++ [3] ++ [2] ++ [1]
[4] ++ [3] ++ [2] ++ [1]
[4, 3] ++ [2] ++ [1]
[4, 3, 2] ++ [1]
[4, 3, 2, 1]
Tail Recursion using the cons operator (:)!!!
One method to deal with call stacks is by adding an accumulator.
(it's not always possible to just add an accumulator. But most of the
recursive functions one deals with are primitive recursive and can thus
be transformed into tail recursive functions.)
With the the help of the accumulator it is possible to make this example
work, using the cons operator (:)
.
The accumulator -- ys
in my example -- accumulates the current result and is passed along as a parameter. Because of the accumulator we are now able
to use the cons operator to accumulate the result by appending the
head of our initial list each time.
reverse' :: (Ord a) => [a] -> [a] -> [a]
reverse' (x:xs) ys = reverse' xs (x:ys)
reverse' [] ys = ys
There is one thing to note here.
The accumulator is an extra argument. I don't know if Haskell
provides default parameters, but in this case it would be nice,
because you would always call this function with an empty list
as the accumulator like so: reverse' [1, 2, 3, 4] []
There is plenty of literature about tail recursion and I'm
sure there are a lot of similar questions on
StackExchange / StackOverflow. Please correct me if you find any mistakes.
Kind regards,
EDIT 1:
Will Ness pointed out some links to really good answers for those of you who are interested:
EDIT 2:
Ok.
Thanks to dFeuer and his corrections I think I understand Haskell
a little bit better.
1.The $!
is beyond my understanding. In all my tests it seemed to
make things worse.
2.As dFeuer pointed out:
The thunk representing the application of (:)
to x
and y
is semantically identical to x:y
but takes more memory. So this is special to the cons operator
(and lazy constructors) and there is no need to force things in any way.
3.If I instead sumUp Integers of a list using a very similar function,
strict evaluation through BangPatterns or the seq
function
will prevent the stack from growing too large if used appropriately. e.g.:
sumUp' :: (Num a, Ord a) => [a] -> a -> a
sumUp' (x:xs) !y = reverse' xs (x + y)
sumUp' [] y = y
Notice the bang in front of y. I tried it out in ghci and it
takes less memory.