# 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))))))

note that `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))

so `map`

becomes

(define map (lambda (f xs) (reverse (foldl (lambda (xs x) (cons (f x) xs)) '() xs))))

however, with

(define (flip f) (lambda (x y) (f y x)))

and because `reverse`

is just left-folding with `flip`

of `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))

and

(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! *

**Note:**See TracWiki for help on using the wiki.