Поддерживает ли SML вложенный список?

Question

Вложенный список может существовать в схеме, но законно ли использовать вложенный список в SML? или мы можем использовать только простой список в SML?

и если законно,

1) как проверить, имеют ли два списка ввода одинаковую структуру списка. По алгоритму атомы в списке не равны.

2) Независимо от глубины входного списка, как удалить все атомы во вложенном списке, равном входному значению: a. следует использовать исходный список, а не создавать новый список.

Answer 1

Нет проблем с наличием вложенных списков в Standard ML. Для примера:

val foo = [ [1, 2, 3], [4, 5], [6] ]

является примером int list listсписок списков целых чисел.

Что касается ваших дополнительных вопросов.

1

Если под той же структурой вы имеете в виду, содержат ли подсписки одинаковое количество элементов, т.е.

val bar = [ [34, 4, 6], [2, 78], [22] ]
val baz = [ [1], [4, 6, 2], [3, 6] ]

val cmp_foo_bar = structureEq (foo, bar) (* gives true, since the lengths of the sublists match up *)
val cmp_foo_baz = structureEq (foo, baz) (* gives false, since they don't *)

Затем вы можете просто создать в списках рекурсивную функцию, которая сравнивает длину каждого подсписка по очереди.

Обратите внимание: если списки вложены более одного раза, вам понадобится функция для каждого уровня. (т.е. один для 'a list listс, один для 'a list list listс и т. д.

2

Вы не можете создать функцию, которая "как бы глубока входной список" что-то делает с элементами в списке. Система типов не позволит вам сделать это. Это похоже на то, как вы не можете сделать следующий список:

val illegal_list = [ [1, 2], [ [1, 4], [2, 3] ] ]

Это связано с тем, что список может содержать только один тип элементов, поэтому, если у вас есть 'a list listкаждый элемент в списке должен быть 'a list, Вы не можете иметь 'aнапрямую.

Вам нужно определиться с тем, насколько вложенными являются списки, и создать функцию, специфичную для этой глубины.

Answer 2

Нет проблем со вложенными списками в SML, например [[1, 2], [3, 4]] работает просто отлично.

Однако, я подозреваю, что вы на самом деле имеете в виду нечто более общее, а именно способность вкладывать "списки" разнородными способами: [[1, [3]], 2], Это не разрешено как таковое в SML. Тем не менее, это потому, что на самом деле это не список, а дерево.

Вы также можете легко определить деревья, но вам нужно более общее определение типа, чем определение для списка:

datatype 'a tree = L of 'a | T of 'a tree list

затем T[T[L 1, T[L 3]], L 2] является представлением "списка" выше. Функция для вычисления глубины (или высоты) такого дерева выглядит

fun depth (L _)  = 0
  | depth (T ts) = 1 + max (List.map depth ts)

где max должно быть определено очевидным образом.