了解用户定义的追加列表标准 ml

Question

我在理解标准 ML 中列表的这种实现时遇到了麻烦。以下是它的定义：

追加列表是列表抽象数据类型的(简单)实现，它使构造变得便宜(O(1))，但使销毁变得昂贵(O(n))。'a alistNN 和 'a alist 类型定义如下：

datatype 'a alistNN = Sing of 'a | Append of 'a alistNN * 'a alistNN
datatype 'a alist = Nil | NonNil of 'a alistNN

'a alistNN 类型表示 'non-nil' 追加列表，而 'a alist 类型表示任意(nil 或 非 nil) 追加列表。

我对如何处理这些列表/制作这些列表感到困惑。例如，我必须编写一个定义为：

'a alist -> 'a alist -> 'a alist that appends to append lists. 

任何帮助将不胜感激，以理解此列表定义。

Answer 1

此数据结构表示带有树的列表，其中每个内部节点表示其子节点的串联，每个叶子节点都是一个元素。例如，下面是列表 [1,2,3,4] 的两种可能表示形式：

val L1 = Append (Append (Sing 1, Sing 2), Append (Sing 3, Sing 4))
*
/ 
*   *
/  / 
1 2 3 4
val L2 = Append (Append (Sing 1, Append (Sing 2, Sing 3)), Sing 4)
*
/ 
*   4
/ 
1   *
/ 
2   3

附加这些数据结构非常容易;您只需将它们与新的Append节点链接在一起即可。我们可以附加上面的两个示例：

Append (L1, L2)
*
/   
/       
*         *
/        / 
*   *     *   4
/  /    / 
1 2 3 4  1   *
/ 
2   3

显然，您还必须根据需要将它们包装在NonNil中，但我会留给您。

Answer 2

使用普通列表，

datatype 'a normal_list = Nil | Cons of 'a * 'a normal_list

Cons

运算符在单个元素前面加上是O(1)，但附加两个列表是O(n)：

fun append (Nil, ys) = ys
| append (xs, Nil) = xs
| append (Cons (x, xs), ys) = Cons (x, append (xs, ys))

有了这些附加列表，

datatype 'a alistNN = Sing of 'a | Append of 'a alistNN * 'a alistNN
datatype 'a alist = Nil | NonNil of 'a alistNN

您的Append运算符现在是O(1)，但缺点变得更加困难O(n)，因为正如您所说，它需要销毁列表才能重建它，因为数据结构的头部不再是第一个元素，而是最近附加列表的点。

我对如何处理这些列表/制作这些列表感到困惑。例如，我必须编写一个定义为：

'a alist -> 'a alist -> 'a alist

将追加到追加列表。

(编辑：澄清了本节。您已经有一个构造函数Append : 'a alistNN * 'a alistNN -> 'a alistNN可以做到这一点。要制作一个适用于"alist"的模式，您必须与"alist">的不同情况进行模式匹配;只有当两个列表都NonNil时，您才能使用Append(因为空列表不能表示为"alistNN。任一操作数Nil的情况可以单独处理;

fun append Nil ys = ys
| append xs Nil = xs
| append (NonNil xs) (NonNil ys) = NonNil (Append (xs, ys))

变得更加困难的一件事是，如果您想在'a alist(即带有签名'a * 'a alist -> 'a alist的函数)前面附加单个元素：

fun cons (x, Nil) = NonNil (...)
| cons (x, NonNil (Sing y)) = NonNil (...)
| cons (x, NonNil (Append (ys, zs))) = NonNil (...)

在每种情况下，x都是前缀。对于要预置x的列表，有三种情况：列表为空，列表为非空且包含单个元素，或者列表为非空，包含另外两个列表的Append。在每种情况下，结果都是NonNil的，因为将x附加到列表中永远不会给出Nil。

前两种情况应该是直截了当的。第三种情况，您必须考虑根据子列表ys和zsx

的位置。像这样，您可以通过在 REPL 中键入open List;来构建找到的所有辅助函数。即使是hd和tl也不是完全微不足道的，因为它们一心想找到第一个元素和列表其余元素之间的拆分。用于测试目的的有用功能将与签名'a alist -> 'a listtoList。为这些附加列表制作一个有趣的方法是rev.:-)

由于您可能不会制作foldl：

fun foldl f e Nil = e
| foldl f e (NonNil (Sing x)) = f (x, e)
| foldl f e (NonNil (Append (xs, ys))) =
foldl f (foldl f e (NonNil xs)) (NonNil ys)

为了娱乐，您可以使用foldl实现hd并抛出异常：

fun hd xs =
let exception FoundIt of 'a
in foldl (fn (x, _) => raise FoundIt x) (fn _ => raise Empty) xs ()
handle FoundIt x => x
end

这是一个稍微相关的 StackOverflow 帖子：标准 ML 函子示例