Mapping over trees

Just as map is a powerful abstraction for dealing with sequences, map together with recursion is a powerful abstraction for dealing with trees. For instance, the scale-tree/2 function, analogous to scale-list/2 of the section Representing Sequences, takes as arguments a numeric factor and a tree whose leaves are numbers. It returns a tree of the same shape, where each number is multiplied by the factor. The recursive plan for scale-tree/2 is similar to the one for count-leaves/2:

(defun scale-tree
  (('() _)
   '())
  (((cons head tail) factor)
   (cons (scale-tree head factor)
         (scale-tree tail factor)))
  ((tree factor)
    (* tree factor)))

> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 100)
(100 (200 (300 400) 500) (600 700))

Another way to implement scale-tree/2 is to regard the tree as a sequence of sub-trees and use map. We map over the sequence, scaling each sub-tree in turn, and return the list of results. In the base case, where the tree is a leaf, we simply multiply by the factor:

(defun scale-tree (tree factor)
  (lists:map #'scale-sub-tree/1 tree))

(defun scale-sub-tree
  ((sub-tree) (when (is_integer sub-tree))
   (* sub-tree factor))
  ((sub-tree)
   (scale-tree sub-tree factor)))

> (scale-tree (list 1 (list 2 (list 3 4) 5) (list 6 7)) 100)
(100 (200 (300 400) 500) (600 700))

Many tree operations can be implemented by similar combinations of sequence operations and recursion.