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


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

Last modified 3 years ago Last modified on Sep 3, 2017, 6:03:33 AM
Note: See TracWiki for help on using the wiki.