4

基于这个定义：

附加列表是列表抽象数据类型的（简单）实现，它使构造成本低（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类型代表任意（零或非零）附加列表。

我要求将地图函数定义为：

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)

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

4

1 回答 1

2

您的内部函数mapNN使用错误类型进行了注释。type的构造函数Sing和Append表单值alistNN，而不是alist. 所以它应该被注释如下。

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

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

  1. 该行alistAppend (ys, zs)有类型'a alist，但函数需要返回一些类型'b alistNN，所以这将是一个类型错误。作为解决此问题的提示，请注意您创建了值ws，ts但从不使用它们... ;)

  2. 一旦你修复mapNN了，你就会有一个类型错误就行了mapNN f xs，因为它有类型'b alistNN，但必须是某种类型的东西'b alist。

总之，要注意alist和之间的区别alistNN。这是两种不同的类型，具有不同的构造函数，具有根本不同的含义！

于 2018-03-09T03:16:39.157 回答