Find values in a tree - type checking SML

Question

I need to write my own datatypes - either, and eitherTree, which have their own types. With these, I need to create a function, that takes an int, and an eitherTree as parameters, that searches through the tree, and returns true if the value exists in the tree. the type needs to be: eitherTree -> int -> bool

So far I have :

datatype either = ImAString of string | ImAnInt of int
datatype eitherTree = eLEAF of either | eINTERIOR of (either*eitherTree*eitherTree)

fun eitherSearch v1 (eLEAF((v2)) = if v1 = v2 then true
                                            else false
    | eitherSearch v1 (eINTERIOR(e1, et1, et2)) = if v1 = e1 then true
                                              else if (eitherSearch v1 et1) = true
                                              then true
                                              else if  (eitherSearch v1 et1) = true
                                              then true else false

The "trick" seems to be casting ImAnInt / int to one another so I can compare them. Anyone have any ideas? Thank you.

molbdnilo molbdnilo · Accepted Answer · 2018-02-18T09:11:14

You can use pattern matching on the entire parameter; you don't need to limit yourself to the outermost constructor.

fun eitherSearch v1 (eLEAF (ImAnInt v2)) = v1 = v2
  | eitherSearch v1 (eLEAF _) = false
  | ...

Or you can write a comparison function:

fun equalInt (v, ImAnInt v') = v = v'
  | equalInt _ = false

fun eitherSearch v1 (eLEAF v2) = equalInt(v1, v2)
  | ...

On a side note,

if E then true else false

is a very roundabout way of writing E,

if E1 then true else E2

is usually written

E1 orelse E2

and you never need to compare a boolean with true or false – e = true is equivalent to e and e = false is equivalent to not e.

Find values in a tree - type checking SML

1 Answers