Используйте рекурсию, чтобы перевернуть список в Ocaml - PullRequest
Новая
       37

Используйте рекурсию, чтобы перевернуть список в Ocaml

0 голосов
/ 12 сентября 2018

Я пытаюсь использовать рекурсию, чтобы перевернуть список (не изменяя его) с помощью вспомогательной функции, без сопоставления или сворачивания.Цель: 

# let list1 = ["a"; "b"; "c"; "d"; "e"];;
val list1 : string list = ["a"; "b"; "c"; "d"; "e"]
# listreverse list1;;
- : string list1 = ["e"; "d"; "c"; "b"; "a"]

Мой код: 

let rec helper remainder reversed =  
if remainder  = [] then reversed else List.hd remainder :: (helper (List.tl remainder) reversed);;

let listreverse lst = helper lst [];;

Однако в настоящее время это просто вернет тот же список, не обращая его.Похоже, добавление головы в конец списка - моя проблема.Могу ли я сделать небольшое исправление, чтобы перевернуть список?

Ответы [ 2 ]

0 голосов
/ 12 сентября 2018

Вы всегда передаете пустой список как reversed и добавляете первый элемент ввода в front рекурсивного результата.

Давайте пройдемся по небольшому тестовому сценарию - реверсирование [1;2].

Это helper [1;2] [] и 

   helper [1;2] []
—> if [1;2]  = [] then [] else List.hd [1;2] :: (helper (List.tl [1;2]) [])
-> List.hd [1;2] :: (helper (List.tl [1;2]) [])
—> 1 :: (helper [2] [])
—> 1 :: (if [2]  = [] then [] else List.hd [2] :: (helper (List.tl [2]) []))
—> 1 :: (List.hd [2] :: (helper (List.tl [2]) []))
—> 1 :: 2 :: (helper [] [])
—> 1 :: 2 :: if []  = [] then [] else List.hd [] :: (helper (List.tl []) [])
—> 1 :: 2 :: []
—> [1;2]

Рассмотрим колоду карт.
Возьмите верхнюю карту и положите ее на стол.
Затем возьмите вторую карту и положите ее поверх первой карты.
Если вы продолжите это делать, пока первая колода не опустеет, у вас будет "новая колода, которая находится в обратном порядке от первой.

Точка вспомогательной функции в точности соответствует этому принципу - вы можете повернуть элементы, «переместив» их с remainder на reversed, ирекурсивный вызов должен быть «хвостовым вызовом», то есть он просто возвращает результат, ничего не делая с ним. 

let rec helper remainder reversed =  
    if remainder = [] 
    then reversed 
    else helper (List.tl remainder) (List.hd remainder :: reversed)

затем 

   helper [1;2] []
—> if [1;2] = [] then []    else helper [2] [1]
—> if [2]   = [] then [1]   else helper []  [2;1]
—> if []    ≈ [] then [2;1] else helper []  ...
—> [2;1]
0 голосов
/ 12 сентября 2018

Может возникнуть вопрос: почему ваша вспомогательная функция имеет два параметра?

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

Если это план, то вы должны возвращать результат в конце (когда исходный список пуст). Но ваш код возвращает пустой список.

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

...