list - SML 是否支持嵌套列表？

Question

嵌套列表可以存在于Scheme中，但是在SML中使用嵌套列表是否合法？或者我们只能在 SML 中使用简单列表？

如果合法，

1）如何检查两个输入列表是否具有相同的列表结构。算法列表中的原子不相等。

2）无论输入列表的深度如何，如何删除嵌套列表中等于输入值的所有原子：a。应该使用原始列表而不是创建新列表。

Answer 1

在标准 ML 中嵌套列表没有问题。例如：

val foo = [ [1, 2, 3], [4, 5], [6] ]

是一个例子int list list，即一个整数列表。

至于您的其他问题。

1

如果通过相同的结构，您的意思是子列表是否包含相同数量的元素，即您想要

val bar = [ [34, 4, 6], [2, 78], [22] ]
val baz = [ [1], [4, 6, 2], [3, 6] ]

val cmp_foo_bar = structureEq (foo, bar) (* gives true, since the lengths of the sublists match up *)
val cmp_foo_baz = structureEq (foo, baz) (* gives false, since they don't *)

然后你可以简单地在列表上创建一个递归函数，依次比较每个子列表的长度。

请注意，如果列表不止一次嵌套，则每个级别都需要一个函数。（即，一个给'a list lists，一个给'a list list lists，等等。

2

您不能创建一个“无论输入列表有多深”的函数对列表中的元素执行某些操作。类型系统不会让你这样做。这类似于您无法列出以下列表：

val illegal_list = [ [1, 2], [ [1, 4], [2, 3] ] ]

这是因为列表只允许包含一种类型的元素，因此如果您有'a list list，则列表中的每个元素都必须是'a list。你不能'a直接拥有 s 。

您必须确定列表的嵌套程度，并创建一个特定于该深度的函数。

Answer 2

SML 中的嵌套列表没有问题，例如[[1, 2], [3, 4]]工作得很好。

但是，我怀疑您实际上是指更笼统的东西，即以异构方式嵌套“列表”的能力：[[1, [3]], 2]. 这在 SML 中是不合法的。然而，这是因为这样的东西并不是一个真正的列表，它是一棵树。

您也可以轻松定义树，但您需要比列表更通用的类型定义：

datatype 'a tree = L of 'a | T of 'a tree list

然后T[T[L 1, T[L 3]], L 2]是上面“列表”的表示。计算这种树的深度（或高度）的函数看起来像

fun depth (L _)  = 0
  | depth (T ts) = 1 + max (List.map depth ts)

哪里max需要以明显的方式定义。