在树中查找值 - 类型检查 SML

Question

我需要编写自己的数据类型 - either 和 eitherTree，它们都有自己的类型。有了这些，我需要创建一个函数，它接受一个 int 和一个 eitherTree 作为参数，搜索树，如果树中存在该值，则 returns 为真。类型需要是： eitherTree -> int -> bool

到目前为止我有：

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

"trick" 似乎正在将 ImAnInt / int 相互转换，以便我可以比较它们。谁有想法？谢谢。

Answer 1

您可以对整个参数使用模式匹配；你不需要将自己局限于最外层的构造函数。

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

或者你可以写一个比较函数：

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

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

旁注，

if E then true else false

是一种很迂回的写法E,

if E1 then true else E2

通常写成

E1 orelse E2

并且您永远不需要将布尔值与 true 或 false 进行比较 – e = true 等同于 e 而 e = false 等同于 not e.

在树中查找值 - 类型检查 SML

Find values in a tree - type checking SML

tree

types

sml

smlnj

pattern-matching