在列表 SML 中查找匹配的数字

Question

我正在尝试用 SML 编写一个函数，其中有两个列表被传递给一个函数，如果两个列表包含相同的数字（或相同数字的倍数），这些数字将被添加到一个新函数中。

fun shared([], []) = []
    let 
        val list = []
    in
        shared(x::xs, y) = if x = y then x::list else shared(xs,y)
    end

我的想法是，如果 x 和 y 相等，则 x 将被添加到列表中，该列表将包含两个原始列表中共享的所有数字。

编辑：新代码

fun append([], L) = L
    | append(x::rest, L) = x::append(rest, L);

fun shared([], y) = 
    let 
        val list = []
    in
        | shared(y, x::xs) = if y = x then append(list, x)
                                    else shared(y,xs)
    end;

我认为在 in 语句中使用 | 在这里是不合法的，但我不知道如何在没有它的情况下递归地运行通过列表。

Answer 1

if both lists contain the same number (or multiple of the same number) [...]

您假设输入列表可能包含重复项，但您没有说明结果列表是否应包含重复项，如果是，它们的重数应该是多少。您的代码表明存在左偏：xs 中的重复项应重复出现在 xs 中的次数，而不管 ys 中出现的重复次数；这似乎是无意和不受欢迎的。

如果您希望重复出现不止一次，您可能应该坚持 multiset intersection 多重性的定义。

在下面的回答中，我假设您只希望数字在结果中出现一次，即使它们在任一输入列表中出现多次。不过，在这种情况下，理想情况下，您可以为不允许重复的集合使用数据类型。

我将从找到两个列表之间的交集开始：

(* Remove duplicates in ''a list. O(n^2) *)
fun nub [] = []
  | nub (x::xs) = x :: nub (List.filter (fn y => x <> y) xs)

(* Determine membership of x in ys. O(n) *)
fun isElem (x, ys) = List.exists (fn y => x = y) ys

(* Find intersection of xs, ys, remove duplicates. O(n^2) *)
fun intersect (xs, ys) = nub (List.filter (fn x => isElem (x, ys)) xs)

这是一个使用这个的例子：

- intersect ([0,0,1,1,2,2,3,4], [1,1,2,3,3,5,6,6]);
> val it = [1, 2, 3] : int list

[...] those numbers are added to a new function

我不确定这里的确切含义。你不会把数字和函数加在一起，函数也没有可以添加东西的可变状态。也许你的意思是如果交集是非空的，一个函数被应用到这个非空的结果？

可能看起来像：

fun sum xs = foldl op+ 0 xs

fun printIntersectSum (xs, ys) =
    case intersect (xs, ys) of
         []  => print "Nothing to see; move along!\n"
       | res => print ("Sum of intersection: " ^ Int.toString (sum res) ^ "\n")

这是一个使用这个的例子：

- printIntersectSum ([0,0,1,1,2,2,3,4], [1,1,2,3,3,5,6,6]);
The sum of the intersection is: 6
> val it = () : unit

在列表 SML 中查找匹配的数字

Finding matching numbers in lists SML

recursion

list

sml

smlnj