Ocaml - переместить последний элемент списка вперед

Question

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

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

Например: have [1;2;3;4;5] -> [5;1;2;3;4]

Я понимаю, что списки в Ocaml - это в основном связанный список,поэтому я планирую рекурсивно перебирать список, находить последний элемент, а затем указывать хвост / оставшийся список этого элемента на начало списка.

Что меня смущает, так это то, как разбитьссылка со второго последнего элемента на последний элемент.В приведенном выше примере я хочу, чтобы 5 баллов указывали на 1, а 4 больше не указывали на 5.

Как мне это сделать, и есть ли более простой способ посмотреть на это, чтоЯ совсем скучаю?

Answer 1

Вы не можете «разорвать связь», потому что списки Ocaml являются постоянной структурой данных.Вы не можете действительно изменять списки, поэтому вы должны создать новый список со значениями в нужном вам порядке.

let thelist = [1;2;3;4;5] in
let lnewhead = List.hd (List.rev thelist) in
lnewhead :: (List.rev (List.tl (List.rev b)));;

Вы также можете определить это в функции:

let flipper = fun thelist -> 
    (List.hd (List.rev thelist)) :: (List.rev (List.tl (List.rev thelist)));;

val flipper : 'a list -> 'a list = <fun>
# flipper([1;2;3;4;5]);;
- : int list = [5; 1; 2; 3; 4]

Answer 2

Код Джошуа можно немного улучшить с точки зрения временной сложности, убедившись, что List.rev thelist вычисляется только один раз, как в:

let flipper = fun thelist ->
   let r = List.rev thelist
   in (List.hd r) :: (List.rev (List.tl r))

Answer 3

Безопасной реализацией является следующее:

let rot1 l =
  let rec aux acc = function
      [] -> []
    | [x] -> x :: List.rev acc
    | x :: l -> aux (x :: acc) l
  in
  aux [] l

Безопасно в том смысле, что пропуск пустого списка возвращает пустой список, а не вызывает исключение. Обратите внимание, что я настоятельно не рекомендую использовать List.hd и List.tl, потому что они могут потерпеть неудачу, с общим сообщением об ошибке.

Кроме того, рекурсивный вызов aux является завершающим вызовом (последнее, что нужно сделать перед возвратом). Компиляторы OCaml обнаружат это и избежат увеличения стека при каждом вызове функции (и, возможно, вызовут исключение или сбой). Об этом следует знать при работе с длинными списками и рекурсивными функциями.

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

Вот пример использования модуля очереди:

 let rotate_queue q =
   if not (Queue.is_empty q) then
     let x = Queue.take q in
     Queue.add x q

 # let q = Queue.create ();;
 val q : '_a Queue.t = <abstr>
 # Queue.add 1 q;;
 - : unit = ()
 # Queue.add 2 q;;
 - : unit = ()
 # Queue.add 3 q;;
 - : unit = ()
 # Queue.iter print_int q;;
 123- : unit = ()
 # rotate_queue q;;
 - : unit = ()
 # Queue.iter print_int q;;
 231- : unit = ()
 # 

Answer 4

Модуль Dllist библиотеки батарей может быть тем, что вы ищете. Это обязательная структура списка.