Функция карты в списке в Standard 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 type представляет "ненулевые" списки дополнений, а '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)

Есть идеи, что может быть причиной этого?

Answer 1

Ваша внутренняя функция mapNN помечен неправильным типом. Конструкторы 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, Это два разных типа, с разными конструкторами и принципиально разными значениями!