Find character in tree with SML

user_5058488 0
Viewed 177

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?

sml algorithm functional-programming
2 Answers

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)
user_4049700

You could generalise the function once more to

fun any p Leaf = false
  | any p (Node (left, x, right)) =
      p x orelse any p left orelse any p right

fun contains c t = any (fn x => c = x) t
user_2359080
Related