SML: tree reduce with a base and a composition function

Question

I want to reduce a binary tree with a base value z, a combining function g. This function has to have work of O(n) but a span of O(log n). Tree is defined as datatype tree = Leaf of int | Node of tree * tree.

This is my code

treeReduce : ('a * 'a -> 'a) -> 'a -> 'a tree -> 'a
Requires: g is associative, z is an identity of g
Ensures: treereduce g z T ~= foldr g z (inord T) ~= foldl g z (inord T)

fun treeReduce (g: 'a * 'a -> 'a) (z : 'a) (Empty: 'a tree)=z
  | treeReduce g z (Node(l,x,r))=g(g(treeReduce g z l,x),treeReduce g z r)

However this doesn't produce the correct answer. What am I doing wrong?

What functions and inputs are you testing it with, and what are the expected and actual outputs? — molbdnilo, Feb 28 '19 at 14:24

sshine · Answer 1 · 2019-02-28T07:45:46.147

You say that your code doesn't produce the correct answer, but you don't say what answer you get and why this isn't correct. So perhaps there's a bug in your code, or perhaps you're traversing the tree in another order than you want. If I were to find out, I'd reformat your code slightly:

fun treeReduce g z0 Empty = z0
  | treeReduce g z0 (Node (left, x, right)) =
    let val z1a = treeReduce g z0 left
        val z1b = treeReduce g z0 right
        val y = g (z1a, x)
        val z = g (z1b, y)
    in z end

I've used a let-in-end to more accurately give each calculation a name.

One thing that strikes me as odd is that z1a and z1b are both based on z0. Compare this to the implementation of preorder, inorder and postorder traversal of trees in SML and you'll see that you probably want the accumulated value to travel along each node. In your case, z1a is not carried to the right branch.
Another thing that strikes me as odd is treeReduce's type signature:
```
('a * 'a -> 'a) -> 'a -> 'a tree -> 'a
```
Compare this to treefold_preorder's:
```
('a * 'b -> 'b) -> 'b -> 'a tree -> 'b
```
and for that sake, List.foldl's:
```
('a * 'b -> 'b) -> 'b -> 'a list -> 'b
```
This allows for the accumulating function to produce values of arbitrary type 'b instead of only being able to produce values of the tree's node type, 'a. This presumably accidental variation is caused by feeding g's output to itself:
```
g(g(tree..., x), tree...)
```
forcing its input value (the node type, 'a) to have the same type as its output value.

What am I doing wrong?

You're gluing the left and right calls to treeReduce together the wrong way, and you have one call to g too many (in the attempt to glue together the left and right calls to treeReduce), causing it to have type 'a * 'a -> 'a when you want it to have type 'a * 'b -> 'b or similar.

Since you're folding trees, this may be of interest:

Tail-recursion on trees

SML: tree reduce with a base and a composition function

1 Answers1