Понимание пользовательского списка приложений Стандарт мл

У меня возникли проблемы с пониманием этой реализации списков в стандарте ML. Вот как это определяется:

Список добавления - это (простая) реализация абстрактного типа данных списка, который удешевляет конструкцию (O(1)), но делает уничтожение дорогостоящим (O(n)). Типы "aistNN" и "aist" определяются следующим образом:

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

"Тип alistNN представляет списки добавления, отличные от nil", а тип "aist" представляет произвольные списки добавления (ноль или не ноль).

Я запутался в том, как я буду работать с этими списками / составлять эти списки. Например, я должен написать функцию, которая определяется как:

'a alist -> 'a alist -> 'a alist that appends to append lists.

Любая помощь будет оценена в понимании этого определения списка.

Источник

2 ответа

Решение

Эта структура данных представляет список с деревом, где каждый внутренний узел представляет конкатенацию своих дочерних элементов, а каждый лист является элементом. Например, вот два возможных представления для списка [1,2,3,4]:

val L1 = Append (Append (Sing 1, Sing 2), Append (Sing 3, Sing 4))

   *
  / \
 *   *
/ \ / \
1 2 3 4

val L2 = Append (Append (Sing 1, Append (Sing 2, Sing 3)), Sing 4)

    *
   / \
  *   4
 / \
1   *
   / \
  2   3

Добавить эти структуры данных очень легко; вы просто связываете их вместе с новым Append узел. Мы могли бы добавить два примера выше:

Append (L1, L2)

        *
      /   \
    /       \
   *         *
  / \       / \
 *   *     *   4
/ \ / \   / \
1 2 3 4  1   *
            / \
           2   3

Очевидно, вы также должны обернуть их в NonNil при необходимости, но я оставлю это вам.

Источник

С обычными списками,

datatype 'a normal_list = Nil | Cons of 'a * 'a normal_list

ваш Cons оператор для добавления одного элемента - O (1), а для добавления двух списков - O(n):

fun append (Nil, ys) = ys
  | append (xs, Nil) = xs
  | append (Cons (x, xs), ys) = Cons (x, append (xs, ys))

С этими списками дополнений,

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

ваш Append оператор теперь является O (1), но cons становится более сложным O(n), потому что, как вы говорите, он требует разрушения списка, чтобы перестроить его, поскольку заголовок структуры данных уже не первый элемент, а скорее точка, в которой список был добавлен в последнее время.

Я запутался в том, как я буду работать с этими списками / составлять эти списки. Например, я должен написать функцию, которая определяется как:

'a alist -> 'a alist -> 'a alist

который добавляет, чтобы добавить списки.

(Изменить: Уточнил этот раздел.) У вас уже есть конструктор Append : 'a alistNN * 'a alistNN -> 'a alistNN это делает именно это. Чтобы создать тот, который вместо этого работает для "алиста", вы должны сопоставить шаблон с различными случаями "алиста"; только когда оба списка NonNil Вы можете использовать Append (так как пустой список не может быть выражен как 'a alistNN. Случаи, когда любой операнд Nil может быть обработан отдельно;

fun append Nil ys = ys
  | append xs Nil = xs
  | append (NonNil xs) (NonNil ys) = NonNil (Append (xs, ys))

Одна вещь, которая становится более сложной, - это если вы хотите добавить один элемент перед списком "алист", то есть функцию с сигнатурой 'a * 'a alist -> 'a alist:

fun cons (x, Nil) = NonNil (...)
  | cons (x, NonNil (Sing y)) = NonNil (...)
  | cons (x, NonNil (Append (ys, zs))) = NonNil (...)

В каждом случае x предварительно Есть три случая, когда речь идет о списке, к которому вы готовитесь x: Либо список пуст, либо список не пустой и содержит один элемент, либо список не пустой и содержит Append из двух других списков. В любом случае, результат чего-то NonNil с момента написания x в список никогда не дадут Nil,

Первые два случая должны быть прямыми. Третий случай, вы должны думать о том, где поставить x с точки зрения подсписков ys а также zs,

Таким образом, вы можете построить все вспомогательные функции, найденные, набрав open List; в ответ. Четное hd а также tl не совсем тривиальны, потому что они стремятся найти разрыв между первым элементом и остальной частью списка. Полезная функция для тестирования toList с подписью 'a alist -> 'a list, Забавный, чтобы сделать для этих списков добавления rev,:-)

Поскольку вы, вероятно, не собираетесь делать foldl:

fun foldl f e Nil = e
  | foldl f e (NonNil (Sing x)) = f (x, e)
  | foldl f e (NonNil (Append (xs, ys))) =
      foldl f (foldl f e (NonNil xs)) (NonNil ys)

Для развлечения вы можете реализовать hd с помощью foldl и выбрасывать исключение:

fun hd xs =
    let exception FoundIt of 'a
    in foldl (fn (x, _) => raise FoundIt x) (fn _ => raise Empty) xs ()
       handle FoundIt x => x
    end

Вот немного связанный пост Stackru: стандартные примеры функторов ML

Источник
Другие вопросы по тегам