No, you can't simply apply that analysis to lazy algorithms. foldr is not a tail-recursive function in a strict language. However, in a lazy language, foldr may

No, you can't simply apply that analysis to lazy algorithms. foldr is not a tail-recursive function in a strict language. However, in a lazy language, foldr may not push O(n) frames on the stack. The code you are looking at here is NOT tail-recursive. Haskell's implementation of ++, in a strict language, will always push O(n) frames on the stack. But it IS true that this code is O(1) in stack consumption with Haskell's execution model.