如何在SML中通过递归实现两个整数集合的子集判断函数

Hey there! Let's work through building this recursive subset function in SML step by step. First, let's fix the issues in your current code, then break down the logic so you understand how it all fits together.

First, Spot the Syntax Issue in Your Code #

Your current line subset(a::;lst1,lst2) has a syntax error — that extra semicolon after :: shouldn't be there. It should be a::lst1 to correctly pattern-match the head and tail of the list. Also, SML's standard library doesn't have a built-in member function, so we'll need to either implement that ourselves or use a standard library alternative.

Recursive Logic for Subset Check #

The core idea of the recursive subset function is straightforward:

• Base Case: If the first list (lst1) is empty, it's automatically a subset of any list — so we return true.
• Recursive Case: For each element in lst1, check if it exists in lst2. If it does, recursively check if the rest of lst1 is a subset of lst2. If any element from lst1 isn't in lst2, we can immediately return false.

Option 1: Implement with a Custom member Function #

First, let's write a simple recursive member function to check if an element is in a list:

fun member(x, []) = false
  | member(x, y::ys) = x = y orelse member(x, ys);

This works by:

• Returning false if we reach an empty list (the element isn't present)
• Checking if the current element matches our target; if not, recursively check the rest of the list.

Now we can pair this with our subset function:

fun subset([], _) = true
  | subset(a::lst1, lst2) = if member(a, lst2) then subset(lst1, lst2) else false;

Testing this:

• subset([1,5],[1,3,5]) returns true (as expected)
• subset([2,5],[1,3,5]) returns false

Option 2: Use List.exists (Idiomatic SML) #

SML's standard List structure has an exists function that does exactly what our custom member does, but in a more idiomatic way. We can rewrite the subset function to use it directly:

fun subset([], _) = true
  | subset(a::lst1, lst2) = List.exists(fn x => x = a) lst2 andalso subset(lst1, lst2);

Here, List.exists(fn x => x = a) lst2 checks if a is present in lst2, and andalso uses short-circuit evaluation — if the first condition fails, it won't run the recursive call, which makes the function more efficient.

Quick Notes to Remember #

• Short-Circuit Evaluation: orelse and andalso stop evaluating as soon as they know the result, which saves unnecessary recursive calls.
• Base Case is Critical: The empty list base case ensures our recursion terminates — without it, we'd end up with an infinite loop.

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