I am really confused on how to make a function "Tail recursive".
Here is my function, but I don't know whether it is already tail recursive or not.
I am trying to merge two lists in Haskell.
merge2 :: Ord a =>[a]->[a]->[a]
merge2 xs [] = xs
merge2 [] ys = ys
merge2 (x:xs)(y:ys) = if y < x then y: merge2 (x:xs) ys else x :merge2 xs (y:ys)
Your function isn't tail-recursive; it's guarded recursive. However, guarded recursion is what you should be using in Haskell if you want to be memory efficient.
For a call to be a tail call, its result must be the result of the entire function. This definition applies to both recursive and non-recursive calls.
For example, in the code
f x y z = (x ++ y) ++ z
the call (x ++ y) ++ z is a tail call because its result is the result of the entire function. The call x ++ y is not a tail call.
For an example of tail-recursion, consider foldl:
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs
The recursive call foldl f (f acc x) xs is a tail-recursive call because its result is the result of the entire function. Thus it's a tail call, and it is recursive being a call of foldl to itself.
The recursive calls in your code
merge2 (x:xs) (y:ys) = if y < x then y : merge2 (x:xs) ys
else x : merge2 xs (y:ys)
are not tail-recursive because they do not give the result of the entire function. The result of the call to merge2 is used as a part of the whole returned value, a new list. The (:) constructor, not the recursive call, gives the result of the entire function. And in fact, being lazy, (:) _ _ returns right away, and the holes _ are filled only later, if and when needed. That's why guarded recursion is space efficient.
However, tail-recursion doesn't guarantee space efficiency in a lazy language. With lazy evaluation, Haskell builds up thunks, or structures in memory that represent code that is yet to be evaluated. Consider the evaluation of the following code:
foldl f 0 (1:2:3:[])
=> foldl f (f 0 1) (2:3:[])
=> foldl f (f (f 0 1) 2) (3:[])
=> foldl f (f (f (f 0 1) 2) 3) []
=> f (f (f 0 1) 2) 3
You can think of lazy evaluation as happening "outside-in." When the recursive calls to foldl are evaluated, thunks are built-up in the accumulator. So, tail recursion with accumulators is not space efficient in a lazy language because of the delayed evaluation (unless the accumulator is forced right away, before the next tail-recursive call is made, thus preventing the thunks build-up and instead presenting the already-calculated value, in the end).
Rather than tail recursion, you should try to use guarded recursion, where the recursive call is hidden inside a lazy data constructor. With lazy evaluation, expressions are evaluated until they are in weak head normal form (WHNF). An expression is in WHNF when it is either:
Just (1 + 1))const 2)\x -> x)Consider map:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
map (+1) (1:2:3:[])
=> (+1) 1 : map (+1) (2:3:[])
The expression (+1) 1 : map (+1) (2:3:[]) is in WHNF because of the (:) data constructor, and therefore evaluation stops at this point. Your merge2 function also uses guarded recursion, so it too is space-efficient in a lazy language.
TL;DR: In a lazy language, tail-recursion can still take up memory if it builds up thunks in the accumulator, while guarded recursion does not build up thunks.
Helpful links:
