SML 多集交集函数

Question

我需要用 SML 编写一个函数，它将任意数量的列表作为输入，returns 所有给定集合的交集。例如，函数需要具有以下形式：

multiSetIntersection([s1,s2,s3,s4]) = (Intersection of s1,s2,s3,s4)

我已经能够编写包含两个列表的交集函数，如下所示：

    fun intersec([], y) = []
      | intersec(x::xs, y) =
        if memberOf(x,y) then x::intersec(xs,y)
        else intersec(xs,y)

但我无法"generalize"此函数将任意数量的列表作为输入。我尝试了以下方法：

    fun multiSetIntersection([]) = []
      | multiSetIntersection((x::xs)::y) =
            if memberOf(x,y) then x::multiSetIntersection([xs,y])
            else multiSetIntersection([xs,y])

但这会给我一些类型不匹配的错误，并且无法正常工作。任何人都可以帮助我或给我一些提示来编写这个函数吗？

谢谢！

Answer 1

使用这个交集函数

fun intersect ([], _) = []
| intersect (x::xs, ys) =
  if List.exists (fn y => x = y) ys
  then x :: intersect (xs, ys)
  else intersect (xs, ys)

做多集交集，有3种情况。

如果没有集合，则交集为[]。
如果有一组xs，交集就是那一组
如果有两个以上的集合，则交集为第一个集合的intersect和其余所有集合的交集。

将这四种情况放在一起我们得到：

  fun intersects [] = []
  | intersects [xs] = xs
  | intersects (xs::xss) = intersect (xs, intersects xss);;

SML 多集交集函数

SML Multiple Set Intersection Function

list

functional-programming

intersection

sml