在SML中实现eitherTree树的整数查找函数（类型匹配问题）

Got it, let's break this down step by step. The key here isn't really "type conversion"—instead, we use SML's pattern matching to extract the integer from the ImAnInt constructor, which is the idiomatic way to handle this kind of algebraic data type.

Step 1: Define the Required Data Types #

First, let's formalize the either (we'll call it myEither to avoid confusion with standard library types) and eitherTree types. I'll assume your either type holds either an integer (via ImAnInt) or another type (like a string—adjust this to your actual non-integer type if needed):

-- Define the either type: holds either an int (wrapped in ImAnInt) or a string
datatype myEither = ImAnInt of int | NonIntValue of string

-- Define the tree structure where each node holds a myEither value
datatype eitherTree = Leaf 
                    | Node of myEither * eitherTree * eitherTree

If you want a generic version that works with any two types, you can make it polymorphic instead:

-- Generic either type for any two types 'a and 'b
datatype ('a, 'b) either = Left of 'a | Right of 'b

-- Generic tree using the either type
datatype ('a, 'b) eitherTree = Leaf 
                             | Node of ('a, 'b) either * ('a, 'b) eitherTree * ('a, 'b) eitherTree

We'll use the non-generic version first since you mentioned ImAnInt specifically.

Step 2: Implement the Search Function #

We need a function of type eitherTree -> int -> bool that traverses the tree and checks if the target integer exists (wrapped in ImAnInt). Here's how to write it with pattern matching:

fun existsInt Leaf _ = false
  | existsInt (Node(valInNode, leftTree, rightTree)) target =
    case valInNode of
         ImAnInt n => n = target orelse existsInt leftTree target orelse existsInt rightTree target
       | NonIntValue _ => existsInt leftTree target orelse existsInt rightTree target

How This Works: #

• Base Case: If we hit a Leaf, there's nothing to check, so return false.
• Node Case: For each node, we pattern match on the myEither value inside the node:
  • If it's ImAnInt n, we compare n directly to the target integer. If they match, we return true immediately. If not, we recursively check the left and right subtrees (using orelse to short-circuit if either subtree finds the value).
  • If it's a non-integer value (like NonIntValue), we skip checking this node and recursively search the left and right subtrees.

Step 3: Test the Function #

Let's create a sample tree to verify the function works:

-- Sample tree: has ImAnInt 5, ImAnInt 10, and a NonIntValue "hello"
val testTree = Node(ImAnInt 5,
                    Node(NonIntValue "hello", Leaf, Leaf),
                    Node(ImAnInt 10, Leaf, Leaf))

-- Test cases
val test1 = existsInt testTree 5  (* Returns true *)
val test2 = existsInt testTree 7  (* Returns false *)
val test3 = existsInt testTree 10 (* Returns true *)

For the Generic Version #

If you went with the polymorphic ('a, 'b) either type, you'd adjust the function to target the integer branch (say, Left holds integers):

fun existsIntGeneric Leaf _ = false
  | existsIntGeneric (Node(eitherVal, left, right)) target =
    case eitherVal of
         Left n => n = target orelse existsIntGeneric left target orelse existsIntGeneric right target
       | Right _ => existsIntGeneric left target orelse existsIntGeneric right target

-- Usage example
val genericTree = Node(Left 3, Node(Right "foo", Leaf, Leaf), Leaf)
val testGeneric = existsIntGeneric genericTree 3 (* Returns true *)

The core idea stays the same: use pattern matching to extract the integer from its constructor, then compare directly. No conversion needed—pattern matching is how you unpack values from algebraic data types in SML.

内容的提问来源于stack exchange，提问作者Oppa