The questions around recursion here made me wonder if Daml performs any tail call optimizations?
Short answer, Yes.
Since around November 2020, with this PR:
We have some test cases here:
For implementation details see:
@Nick_Chapman This is awesome. I’ll try to grok the Speedy scala. But in the meantime what about allocations that occur at the tail position?
my_map : (a -> b) -> [a] -> [b] my_map f  =  my_map f (h::t) = f h :: my_map f t
my_map is not tail recursive, so no tail call optimization will apply. The speedy execution stack will grow to the length of the input list. Fortunately, the speedy execution stack lives on the JVM heap, so there will be no JVM stack overflow. (Never overflowing the JVM stack during Daml execution is a property the speedy engine aims to ensure!)
As far as I am aware, the only way to code a tail-recursive definition of list mapping is to make two passes over the list. Something like this (and assuming
reverse is tail recursive):
myMapAcc : [b] -> (a -> b) -> [a] -> [b] myMapAcc acc _  = reverse acc myMapAcc acc f (h::t) = myMapAcc (f h :: acc) f t myMap : (a -> b) -> [a] -> [b] myMap f xs = myMapAcc  f xs
Just for fun, you can also implement a tail-recursive
foldl as follows:
map : (a -> b) -> [a] -> [b] map f xs = reverse $ foldl (\t h -> f h :: t)  xs
(This unpacks to the same as @Nick_Chapman’s code, but perhaps a little more efficient because
foldl is a built-in.)
Or more point-free:
map : (a -> b) -> [a] -> [b] map f = reverse . foldl (\t h -> f h :: t) 
For even more fun, and contrary to my earlier reply, it is possible to define a tail recursive version of map, which makes just a single pass over the list. And we can still use
foldl if we want:
onePassMap : (a -> b) -> [a] -> [b] onePassMap f xs = foldl (\t h -> t . (f h ::)) identity xs 
This is pretty silly, and if you squint you can still see a 2nd pass
I see 2nd passes everywhere!
It looks like your
my_map function is tail recursive modulo cons, which, if i am not mistaken, would be tail-call optimized in Haskell.