list - 从 SML 中的嵌套列表中提取重复项

Question

我在 SML 中有一个返回嵌套列表的函数：

[["A", "B", "C"], ["A", "B"], ["B", "C"]]]

是否可以提取出现在这些列表中的元素？即输出“B”？

我已经尝试了一些效果，List.filter (fn y=>(fn x=> x=y)) lst但无济于事..有什么提示吗？

Answer 1

我将假设您提供的示例嵌套列表具有代表性，即元素是唯一且有序的。我还将省略任何显式类型或参数化比较函数，因此这些函数将对整数而不是字符串进行操作。

首先，将问题分解为成对比较列表。定义一个辅助函数common来查找一对有序列表的共同元素。它可能看起来像这样：

fun common(xs, []) = []
  | common([], ys) = []
  | common(x::xs, y::ys) = if x=y then x::common(xs, ys) 
                           else if x < y then common(xs, y::ys) 
                           else common(x::xs, ys)

它有类型int list * int list -> int list。

为了使嵌套列表工作，您可以基于以下解决方案common：

fun nested_common([]) = []
  | nested_common(x::[]) = x
  | nested_common(x::y::rest) = nested_common(common(x,y)::rest)

这有类型int list list -> int list。

使用它（在莫斯科 ML 中）：

- nested_common [[1,2,3], [1,2], [2,3]];
> val it = [2] : int list