>>3
But!
If we talk about inversion, it does have a curious effect on data structures. Consider a function that sums the elements of a list of natural numbers.
(define (natsum l)
(cond
((null? l) 0)
(else (+ (car l) (natsum (cdr l))))))
(define (natsum-cps l k)
(cond
((null? l) (k 0))
(else (natsum-cps (cdr l) (lambda (v) (k (+ v (car l))))))))
(define (natsum-dispatch v k)
(match k
('Start v)
(('Cdr w k') (natsum-dispatch (+ v w) k'))))
(define (natsum-defun l k)
(cond
((null? l) (natsum-dispatch 0 k))
(else (natsum-defun (cdr l) `(Cdr ,(car l) ,k)))))Notice the data structures in natsum-dispatch! They really look like a list, don't they? Let's rewrite it using a simple list.
(define (natsum-aps a l)
(cond
((null? l) a)
(else (natsum-aps (+ a (car l)) (cdr l)))))
(define (natsum-?? l k)
(cond
((null? l) (natsum-aps 0 k))
(else (natsum-?? (cdr l) (cons (car l) k)))))As you can guess from the name, the dispatch function turned out to be the accumulator passing style version of the original function! Or you could call it iterative and name it Natsumi. This is possible because + is commutative. Otherwise, we would have something different here, and natsum-?? will give us a hint what. If you squint your eyes, you might recognize the accumulator passing style of reverse.
I cheated a little, if you try it on a tree traversing algorithm you will end up with something different but just as much fascinating.