Tree fold in Racket

gistfile1.scm

(define-type (Tree a) (U (leaf a) (node a)))
(struct: (a) leaf ([val : a]))
(struct: (a) node ([left : (Tree a)] [right : (Tree a)]))

(: tree-height (All (a) ((Tree a) -> Integer)))
(define (tree-height t)
  (cond [(leaf? t) 1]
        [else (max (+ 1 (tree-height (node-left t)))
                   (+ 1 (tree-height (node-right t))))]))

(: tree-fold (All (a b) ((a -> b) (b b -> b) (Tree a) -> b)))
(define (tree-fold baseF treeF t)
  (cond [(leaf? t) (baseF (leaf-val t))]
        [else (treeF (tree-fold baseF treeF (node-left t))
                     (tree-fold baseF treeF (node-right t)))]))

;; this works OK

(: int-id (Integer -> Integer))
(define (int-id x) x)

(: plus (Integer Integer -> Integer))
(define plus +)

(: tree-sum-int ((Tree Integer) -> Integer))
(define (tree-sum-int t)
  (tree-fold int-id plus t))

;; but the following is too generic? :(

;;(: id (All (a) (a -> a)))
;;(define (id x) x)

;;(: tree-sum ((Tree Number) -> Number))
;;(define (tree-sum t)
;;  (tree-fold id + t))