Find character in tree with SML

Question

I'm new to SML and trying to wrap my head around functional programming. I want to have a function that accepts a tree t and a character c and returns true or false if the tree contains the character.

The algorithm I want to implement is:

1. if leaf is null return false,

2. else if character is in leaf return true,

3. return result of left tree or result of right tree

This is my tree datatype

datatype 'a tree =
    Leaf of 'a
  | Node of 'a tree * 'a * 'a tree;

And this is the function

fun containsChar (Leaf t, c: char) = false 
  | containsChar (Node (left, t, right)) = 
    if t = c then true else false
  | containsChar (Node (left, t, right)) = (containsChar left) <> (containsChar right);

I am getting Unbound value identifier "c". Why is this?

Answer 1

There is nothing called "c" in that clause. There is a "c" in the leaf case, but that's a completely different case. You forgot that parameter in the other cases.
(And if t = c then true else false is equivalent to t = c.)

You also have identical patterns in the second and third clauses, which isn't going to work.

Another problem you have is the "leaf is null" rule – a leaf can't be "null".
I suspect that this is what brought you astray, as the result of your first clause is false even though the argument is clearly an existing leaf, and your second clause is clearly not a leaf but looks like your second rule.

Your rules should be these:

A tree contains a character if and only if

• it is the value in a leaf, or
• it is the value in a node, or
• it is contained in a node's subtrees.

In ML (removing the restriction to char Tree since it seems arbitrary),

fun contains (Leaf t, c) = t = c 
  | contains (Node (left, t, right), c) = t = c
                                       orelse contains(left, c)
                                       orelse contains(right, c)