tree-fold defintion that works both with + and app

问题:

(define (tree-fold f tree)
  (if (pair? tree)
      (apply f (car tree) (map (lambda (t) (tree-fold f t)) (cdr tree)))
      (f tree)))

works for example with: (tree-fold + '(1 (2 2)(2 2)) -> 9

However if I want to use (tree-fold append '(1 (2 2)(2 2))), I have to modify the tree-fold with list around (car tree), which breaks it for +. Is there some mechanism that can be used in the tree-fold definition that would make it work with both + and append?

回答1:

This should work, adding one parameter to initialise the result:

(define (tree-fold f n sxp)
  (let loop ((sxp sxp) (res n))
    (cond
      ((null? sxp) res)
      ((pair? sxp) (loop (car sxp) (loop (cdr sxp) res)))
      (else        (f sxp res)))))

Testing:

> (tree-fold + 0 '(1 (2 2)(2 2)))
9
> (tree-fold cons '() '(1 (2 3)(4 5)))
'(1 2 3 4 5)