Why can Tail Recursion Modulo Cons be optimized?

user_11781198 0
Viewed 341

For example, this is not a tail call :

map _ [] = []
map f (x : xs) = f x : map f xs

the recursive callis guarded by the (:) data constructor, so it won't build up a huge stack like an equivalent in some other language might do. It works like this :

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : 3 : [])
2 : 3 : map (+1) (3 : [])
2 : 3 : 4 : map (+1) []
2 : 3 : 4 : []

Why not

map (+1) (1 : 2 : 3 : [])
2 : map (+1) (2 : 3 : [])
2 : (3 : map (+1) (3 : []))
2 : (3 : (4 : map (+1) []))
2 : (3 : (4 : []))
2 : (3 : [4])
2 : [3, 4]
[2, 3, 4]

It has to do with WHNF, but I still can't understand it well :(

tailrecursion-modulo-cons recursion lazy-evaluation functional-programming haskell
1 Answers

Because : is lazy. It does not by itself trigger evaluation of its second argument.

What you show is not the whole story. map does not do what you show on its own either, only if demanded by some other consumer whose result is demanded ultimately by main (or GHCi's REPL). So for instance,

GHCi> take 2 (map (1+) [1..4]
   {- implied `putStrLn . show` causes this -}
   = take 2 (2 : map (1+) (enumFromTo 2 4))
   = 2 : take 1 (map (1+) (enumFromTo 2 4))
   = 2 : take 1 (3 : map (1+) (enumFromTo 3 4))
   = 2 : 3 : take 0 (map (1+) (enumFromTo 3 4))
   = 2 : 3 : []

The rest of the input list is not even computed because take does not demand it from map which thus does not demand any more elements from the input list.

A side note: TRMC is eager-evaluating languages' terminology. In Haskell, it is referred to as guarded recursion. The recursive call must be behind a lazy constructor.

I don't believe Haskell (i.e. GHC) has TRMC-optimization in the strict constructor case. It could, in case the result type is a monoid, like lists indeed are:

[a] ++ ([b] ++ ([c] ++ ....))
=
([a] ++ [b]) ++ ([c] ++ ....)

So in an eager language with TRMCO, instead of first evaluating both arguments to the top : indeed opening up an O(n) stack of computations like your second snippet implies, it would create the top : first and fill its right slot afterwards, working in an iterative fashion in constant stack space (just like Wikipedia code snippets show).

But in Haskell all this does not apply, when the constructor is lazy and no arguments evaluation is triggered on its own anyway.

user_8498910
Related