Map function on a list in Standard ML

Question

Based on this definition:

An append list is a (simple) implementation of the list abstract data type that makes construction cheap (O(1)), but makes destruction expensive (O(n)). The 'a alistNN and 'a alist types are defined as follows:

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

The 'a alistNN type represents the “non-nil” append lists, while the 'a alist type represents arbitrary (nil or non-nil) append lists.

Im asked to make a map function defined as:

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

That performs a map on an append list.

I have it defined as follows:

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

I keep getting clashing types, especially with:

Sing x => Sing (f x)

Any idea what might be causing this?

Answer 1

Your inner function mapNN is annotated with the wrong type. The constructors Sing and Append form values of type alistNN, not alist. So it should instead be annotated as follows.

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

There are a couple other issues with your code:

1. The line alistAppend (ys, zs) has type 'a alist but the function needs to return something of type 'b alistNN, so this will be a type error. As a hint to fix this problem, notice that you create values ws and ts but then never use them... ;)

2. Once you fix mapNN, you will have a type error on the line mapNN f xs, because it has type 'b alistNN, but needs to be something of type 'b alist.

In summary, be careful about the difference between alist and alistNN. These are two different types, with different constructors, and fundamentally different meanings!