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