sml - 标准机器学习列表上的映射函数

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类型表示“非零”附加列表，而 'a alist type 表示任意(nil 或非 nil)附加列表。

我要求制作一个定义为的 map 函数:

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但该函数需要返回 'b alistNN 类型的东西，所以这将是一个类型错误。作为解决此问题的提示，请注意您创建的值 ws和 ts但永远不要使用它们... ;)

一旦你修复 mapNN ，您将在 mapNN f xs 行出现类型错误，因为它有类型 'b alistNN ，但需要是 'b alist 类型的东西.

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