Ошибка типа в стандартной функции обратной связи ML

Question

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

fun reverse [] = [] | 
    reverse (v1::rest) = (reverse(tl(rest)) @ v1) 

Это выход, когда я пытаюсь запустить обратное ([1, 2, 3]);

poly: : error: Type error in function application. 
Function: reverse : 'a list list -> 'a list 
Argument: ([1, 2, 3]) : int list 
Reason: 
    Can't unify int (*In Basis*) with 'a list (*In Basis*) 
    (Different type constructors) 
Found near reverse ([1, 2, 3]) 
Static Errors 

Я вижу, что это ошибка типа. Похоже, что обратное ищет 2 списка (я думаю .. «список списка кажется мне странным типом)? Есть ли проблема с настройкой шаблона/параметров? Спасибо за помощь.

Answer 1

Вначале обратимся к неправильному вопросу.

'a list list означает список списков, как этот:

[[1,2], [3,4], [5,6]] : int list list 

который представляет собой список из списков целых чисел.

Общий вид вашей reverse функции

val reverse = fn : 'a list list -> 'a list 

Это происходит потому, что оператор @ имеет следующую сигнатуру (вы можете найти документы here).

val @ : 'a list * 'a list -> 'a list 

Таким образом, механизм вывода типа делает вывод, что v1 является 'a list, но это означает, что список входов содержит элементы типа 'a list и, следовательно, должны быть типа 'a list list.

Но что на самом деле имел в виду, чтобы добавить элемент v1 до конца обращенного хвоста, и это может быть легко достигнуто путем v1 в список одного элемента:

some_list @ [v1]

Далее вам не нужно tl(rest), так как rest уже является хвостом вашего списка входных данных. В качестве побочного примечания: более идиоматично писать tl rest, круглые скобки здесь несущественны.

Принимая во внимание вышесказанное, мы получаем следующую реализацию:

fun rev [] = [] 
    | rev (h::tl) = rev tl @ [h] 

Я должен предупредить вас, что эта функция является очень неэффективным, поскольку это временная сложность является квадратным (O (N^2)).