标准 ML 列表中的映射函数

Question

基于这个定义：

追加列表是列表抽象数据类型的（简单）实现，它使构建成本低 (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）附加列表。

我被要求制作一个地图函数定义为：

fun alistMap (f: 'a -> 'b) (xs: 'a alist): 'b alist =

在追加列表上执行映射。

我定义如下：

fun alistMap (f: 'a -> 'b) (xs: 'a alist): 'b alist =
    case xs of
      Nil => Nil
    | NonNil xs => 
      let
        fun mapNN(f: 'a -> 'b) (xs: 'a alist): 'b alist =
           case xs of 
             Sing x => Sing (f x)
           | Append (ys, zs) => 
             let
               val ws = mapNN f ys
               val ts = mapNN f zs
             in
               alistAppend (ys , zs)
             end
      in
        mapNN f xs
      end

我不断遇到类型冲突，尤其是：

Sing x => Sing (f x)

知道是什么原因造成的吗？

Answer 1

您的内部函数 mapNN 被注释为错误的类型。构造函数 Sing 和 Append 形成 alistNN 类型的值，而不是 alist。所以它应该改为注释如下。

fun mapNN (f : 'a -> 'b) (xs : 'a alistNN) : 'b alistNN = ...

您的代码还有其他几个问题：

行 alistAppend (ys, zs) 的类型为 'a alist 但函数需要 return 类型为 'b alistNN 的东西，所以这将是一个类型错误.作为解决此问题的提示，请注意您创建了值 ws 和 ts，但随后从不使用它们...;)
修复 mapNN 后，您将在 mapNN f xs 行出现类型错误，因为它的类型为 'b alistNN，但需要是输入 'b alist.

综上所述，注意alist和alistNN的区别。这是两种不同的类型，具有不同的构造函数，并且具有根本不同的含义！

标准 ML 列表中的映射函数

Map function on a list in Standard ML

sml

ml

mosml