Как изменить пользовательский список в SML?

Question

Мой пользовательский тип данных определяется следующим образом: тип данных 'a mylist = NIL | CONS of 'a * 'a mylist;

Пытался часами, но не могу понять, как перевернуть такой список.

Мой код не соответствуетработа:

fun reverse NIL = NIL
| reverse (CONS(head,tail)) = reverse tail @ [head];

Вот вызов функции:

reverse (CONS(4,CONS(3,CONS(2,NIL))));

Answer 1

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

например

fun reverse xs =
let
  fun revhelp NIL ys = ys
    | revhelp (CONS(x,xs)) ys = revhelp xs (CONS(x,ys))
in
  revhelp xs NIL
end;

Answer 2

Вы не можете использовать встроенные приложения (@) и списки ([head]) со своим собственным типом списка.

Вам нужно CONS (head, NIL) вместо [head], и вам нужнонапишите свой

append: 'a mylist -> 'a mylist -> 'a mylist

или

append: ('a mylist * 'a mylist) -> 'a mylist

Реализация append оставлено в качестве упражнения.