% $Id: TreeFuns.oz,v 1.1 2007/10/22 03:39:06 leavens Exp leavens $ % Functions on trees and a higher-order generalization declare % Return a list of pairs of labels and values in a pre-order traversal of T fun {Preorder T} case T of leaf then nil [] tree(key: L value: V left: Left right: Right) then (L#V) | {Append {Preorder Left} {Preorder Right}} end end % Return a tree like T, but with all values incremented by 1 fun {IncTree T} case T of leaf then leaf [] tree(key: L value: V left: Left right: Right) then tree(key: L value: 1+V left: {IncTree Left} right: {IncTree Right}) end end % The following rewrite the above to highlight the similarities betwen them. % These use the beta-equivalence rule, i.e., that % {fun {$ A B C D} Exp(A,B,C,D) end W X Y Z} == Exp(W,X,Y,Z) % but in the right-to-left direction. This is just functional abstraction. declare fun {Preorder T} case T of leaf then nil [] tree(key: L value: V left: Left right: Right) then fun {Combine L V Left Right} (L#V) | {Append Left Right} end in {Combine L V {Preorder Left} {Preorder Right}} end end fun {IncTree T} case T of leaf then leaf [] tree(key: L value: V left: Left right: Right) then fun {Combine L V Left Right} tree(key: L value: 1+V left: Left right: Right) end in {Combine L V {IncTree Left} {IncTree Right}} end end declare % A functional abstraction of Preorder and IncTree fun {FoldTree Combine Base T} case T of leaf then Base [] tree(key: L value: V left: Left right: Right) then {Combine L V {FoldTree Combine Base Left} {FoldTree Combine Base Right}} end end % The following use FoldTree to implement Preorder and IncTree fun {Preorder T} {FoldTree fun {$ L V Left Right} (L#V) | {Append Left Right} end nil T} end fun {IncTree T} {FoldTree fun {$ L V Left Right} tree(key: L value: 1+V left: Left right: Right) end leaf T} end