chickadee » slib-wt-tree » wt-tree/fold

Folds tree, applying kons to the key, value, and the accumulated result, in that order, at each step. knil is passed to kons as the initial accumulator value. tree is traversed in reverse order.

Provided kons runs in O(1) time, wt-tree/fold takes time proportional to the size of tree.

Example:

(let ((t (alist->wt-tree string-wt-type
                         '(("rincewind" . 23)
                           ("twoflower" . 11)
                           ("the luggage" . 31)))))
  (list (wt-tree/fold (lambda (_k v sum) (+ v sum)) 0 t)
        (wt-tree/fold (lambda (k _v keys) (cons k keys))
                      '()
                      t)))
; -> (65 ("rincewind" "the luggage" "twoflower"))