SML/NJ - связанный список, который может содержать любые типы

Question

Я пытаюсь создать тип данных для связанного списка, который может содержать все типы одновременно, то есть связанный список элементов void *, разработка заключается в создании Node тип данных, который содержит запись, содержит Value а также Next,

То, что я сделал до сих пор, -

datatype 'a anything = dummy of 'a ; (* suppose to hold any type (i.e void*) *)

datatype linkedList = Node of {Value:dummy, Next:linkedList}; (* Node contain this record *)

Как вы можете видеть вышеописанное, попытка не работает, но я считаю, что моя идея достаточно ясна, поэтому какие изменения здесь необходимы, чтобы это работало?

Answer 1

Я не уверен, что вас заставляют использовать тип записи. Потому что в противном случае я думаю, что это проще сделать:

datatype 'a linkedlist = Empty | Cons of 'a * 'a linkedlist

Тогда вы можете использовать это как:

val jedis = Cons ("Obi-wan", Cons("Luke", Cons("Yoda", Cons("Anakin", Empty))));

Я думаю, что использование записи - плохой выбор здесь. Я даже не могу думать, как я мог бы представить пустой список с таким подходом.

-РЕДАКТИРОВАТЬ-

Чтобы ответить на ваш комментарий о поддержке нескольких типов:

datatype polymorphic = N of int | S of string | B of bool
Cons(S("A"), Cons(N(5), Cons(N(6), Cons(B(true), Empty))));

Учитывая обстоятельства, вы можете предпочесть списки SML:

S("A")::N(5)::N(6)::B(true)::[];

Который производит список

[S "A",N 5,N 6,B true]

То есть список того же типа (т.е. полиморфный), но этот тип способен содержать различные виды вещей через несколько его конструкторов.

Answer 2

К вашему сведению, если важно, чтобы типы вашего полиморфного списка оставались открытыми, вы можете использовать встроенный тип исключения SML: exn. Тип exn открыт и может быть расширен в любом месте программы.

exception INT of int
exception STR of string
val xs = [STR "A", INT 5, INT 6] : exn list

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

val inc_ints = List.map (fn INT i => INT (i + 1) | other => other)

И позже вы можете расширить тип без упоминания его предыдущего определения:

exception BOOL of bool
val ys = [STR "A", INT 5, INT 6, BOOL true] : exn list

Обратите внимание, что вы можете поместить туда конструкцию любого исключения (здесь исключение деления на ноль):

val zs = Div :: ys : exn list

Тем не менее, это (ab) использование действительно имеет очень мало хороших вариантов использования, и вам, как правило, лучше использовать закрытый тип суммы, как объяснил Эдвин в ответе выше.