1

我无法理解标准 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 类型表示“非 nil”附加列表，而 'a alist 类型表示任意（nil 或非 nil）附加列表。

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

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

在理解此列表定义时，我们将不胜感激。

4

2 回答 2

3

该数据结构表示一个带有树的列表，其中每个内部节点表示其子节点的串联，每个叶子节点都是一个元素。例如，下面是列表 [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，但我将把它留给您。

于 2018-03-06T03:36:15.227 回答
1

使用普通列表，

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)，但是cons变得更加困难O(n)因为，正如您所说，它需要破坏列表来重建它，因为数据结构的头部不再是第一个元素，而是而是最近添加列表的点。

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

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

附加到附加列表。

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

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其他两个列表中的一个。在每种情况下，结果都是NonNilsome ，因为将 an 添加x到列表中永远不会给出Nil。

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

像这样，您可以构建通过键入open List;REPL 找到的所有辅助功能。Evenhd并且tl不是完全微不足道的，因为他们一心想要找到第一个元素和列表其余部分之间的拆分。用于测试目的的一个有用功能是toList使用签名'a alist -> 'a list。为这些附加列表制作一个有趣的内容是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)

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

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 仿函数示例

于 2018-03-06T07:32:43.057 回答