Сторнирование списка в OCaml с рекурсией

Question

Я смотрю на алгоритм обращения списка в Ocaml:

let rec reverseList list revList=
   match list with 
     | [] -> revList
     | h::t -> reverseList t revList@[h]

Примером использования может быть:

let list = [1;2;3;4];;
reverseList list [];;

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

reverseList [1;2;3;4] []
reverseList [2;3;4] [1]
reverseList [3;4] [1;2]
reverseList [4] [1;2;3]
reverseList [] [1;2;3;4]

, которые возвращали бы [1; 2; 3; 4]. Тем не менее, этот код работает. Итак, почему это работает, и почему не последняя строка

| h::t -> reverseList t [h]@revList

У меня есть подозрение, что это как-то связано с карри, но я не очень хорошо понимаю это. Пожалуйста, помогите!

Answer 1

Выражение:

reverseList t revList@[h]

Разбирается так:

(reverseList t revlist) @ [h]

Другими словами, сначала рекурсивно реверсирует хвост, затем добавляет новый элемент в конец. Это действительно работает (хотя это не эффективный способ перевернуть список.)

Также обратите внимание, что параметр revList никогда не является ничем иным, как пустым списком.