The problem we'll solve is to write a traversal of the DHTML DOM tree in a web page. The problem is useful and ubiquitous, but it's hard to solve in a language that doesn't like recursion. It's pretty well-known that you need to maintain an explicit stack to drive the traversal, but it's not obvious how to get it right. I could point out popular libraries that get it wrong, but I'll be polite.
For the sake of example, I'll simplify the problem somewhat: we'll represent DOM nodes as a simple structure:
;; tree = symbol × (listof tree)Leaf nodes are represented as trees with empty lists of children. We'll traverse the DOM in the style of CSS selectors, which are represented as an ancestry path of tags:
(define-struct tree (tag children))
;; path = (listof selector)For example, the path '(foo bar) represents the set of all bar nodes that are descendants of foo nodes.
;; selector = symbol
The clearest implementation of the problem is a structural induction on the DOM tree and selector path (technically, the ordering is lexicographic over both inputs):
We have two distinct datatypes to recur on: tree and (listof tree), which leads to two separate functions. When we find a node that matches, we need to test it against the rest of the path as well; otherwise we just search its descendants. We only produce a match when we find a node that has matched the entire selector path.1;; select : tree × path → (listof tree)
(define (select tree path)
[(null? path) (list tree)]
[(matches? tree (car path)) ; does node's tag match first tag in path?
(append (select tree (cdr path))
(select* (children tree) path))]
[else (select* (children tree) path)]))
;; select* : (listof tree) × path → (listof tree)
(define (select* trees path)
[(null? trees) null]
[else (append (select (car trees) path)
(select* (cdr trees) path))]))
The recursive solution uses the implicit control stack of Scheme to drive the traversal, but we want an explicit implementation. The easiest way to represent control is to CPS a program, so let's try that:
This no longer relies on the control stack of Scheme, because every function call is in tail position. However, it isn't a satisfying solution for an iterative language--even one with higher-order functions--because without proper tail calls, it will still use unbounded control space.;; select/k : tree × path × ((listof tree) → (listof tree)) → (listof tree)
(define (select/k tree path k)
[(null? path) (k (list tree))]
[(matches? tree (car path))
(select/k tree (cdr path)
(select*/k (children tree) path
(k (append ts1 ts2))))))]
[else (select*/k (children tree) path k)]))
;; select*/k : (listof tree) × path × ((listof tree) → (listof tree)) → (listof tree)
(define (select*/k trees path k)
[(null? trees) (k null)]
[else (select/k (car trees) path
(select*/k (cdr trees) path
(k (append ts1 ts2))))))]))
To be continued...
1 For the sake of simplicity, I'm not going to worry about duplicate elements in the result list.