fold-left has this basic recursion:
(fold-left f init ()) = init (fold-left f init (a . d)) = (fold-left f (f init a) d)A straightforward implementation of this is
(defun fold-left (f init list) (if (null list) init (fold-left f (funcall f init (car list)) (cdr list))))The straightforward implementation uses a slightly more space than necessary. The call to
foccurs in a subproblem position, so there the stack frame for
fold-leftis preserved on each call and the result of the call is returned to that stack frame.
But the result of
fold-left is the result of the last
f, so we don't need to retain the stack frame
fold-left on the last call. We can end the iteration on a tail call
f on the final element by unrolling the loop
(defun fold-left (f init list) (if (null list) init (fold-left-1 f init (car list) (cdr list)))) (defun fold-left-1 (f init head tail) (if (null tail) (funcall f init head) (fold-left-1 f (funcall f init head) (car tail) (cdr tail))))
There aren't many problems where this would make a difference (a challenge to readers is to come up with a program that runs fine with the unrolled loop but causes a stack overflow with the straightforward implementation), but depending on how extreme your position on tail recursion is, this might be worthwhile.