Constant-space left fold
First consider the Accumulator Pattern - transforming of a stack-based recursive process into loop-based iterative process with an explicit accumulator.
(define (length xs) (cond ((null? xs) 0) (else (+ 1 (length (cdr xs))))))
becomes a tail-call recursion with accumulator (which is transformed later by TCO into an iterative loop).
(define (length xs) (let loop ((ys xs) (acc 0)) (cond ((null? ys) acc) (else (loop (cdr ys) (+ 1 acc))))))
let form is an implicit
lambda with in-place invocation -
(let ((x 1)) x) is
((lambda (x) x) 1)
There is a constant-space O(2n)
map which an inner helper-procedure.
(define (map f xs) (define (iter xs acc) (cond ((null? xs) (reverse acc)) (else (iter (cdr xs) (cons (f (car xs)) acc))))) (iter xs '()))
reverse is required because a stack-based recursive process conses a new list from right to left, after reaching the base-case when recursion unwinds, while an iterative, loop-based helper procedure conses in a "straight-forward" reversed order.
This common pattern could be generalized as a constant-space, tail-recursive left-fold.
(define foldl (lambda (f a xs) (if (null? xs) a (foldl f (f a (car xs)) (cdr xs)))))
so we could encapsulate a CDR-ing or traversal of a List
(define (length xs) (foldl (lambda (acc x) (+ 1 acc)) 0 xs))
(define map (lambda (f xs) (reverse (foldl (lambda (xs x) (cons (f x) xs)) '() xs))))
(define (flip f) (lambda (x y) (f y x)))
reverse is just left-folding with
cons we have
(define map (lambda (f xs) (foldl (lambda (xs x) ((flip cons) (f x) xs)) '() xs)))
Together with Partial Application
(define partially (lambda (f . as) (lambda xs (apply f (append as xs)))))
we could define beautiful, declarative, O(n) constant-space
(define length (partially foldl (lambda (acc x) (+ 1 acc)) 0))
(define reverse (partially foldl (flip cons) '()))
and even constant-space right-fold of just O(2n)
(define (foldr f z xs) (foldl (flip f) z (reverse xs)))
Happy, Happy! Joy, Joy!