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

Мой пользовательский тип данных определяется следующим образом: тип данных '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))));

recursion custom-data-type sml
person vin504    schedule 10.10.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

e.g.

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

arrow_upward
0
arrow_downward

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

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

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

or

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

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

person molbdnilo    schedule 12.10.2019