Ocaml - move the last list item forward

Question

Firstly, I apologize if this is a confusing or reverse way to do what I want to accomplish, but I'm new to Ocaml style.

I want to take the last element of the list and move it to the top of the list, moving all the elements to one.

For example: have [1;2;3;4;5] -> [5;1;2;3;4]

I understand that lists in Ocaml are mostly linked by a list, so I plan to iterate over the list recursively, find the last item, and then point that tail of the item / remaining list to the head of the list.

What I'm basically confused about is how to break the link from the second last element to the last element. In the above example, I want to have 5 points for 1, but 4 no longer point to 5.

How to do this, and is there an easier way to look at this that I am completely missing?

Answer 1

You cannot “Break the link” because Ocaml lists are a permanent data structure. You cannot really change the lists, so you need to create a new list with the values ​​in the order you want.

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

You can also define this in a function:

 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

Joshua code can be slightly improved in terms of time complexity by making sure List.rev thelist evaluated only once, as in:

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

Answer 3

The safe implementation is as follows:

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

This is safe in the sense that passing an empty list returns an empty list instead of raising an exception. Please note that I strongly recommend against using List.hd and List.tl, because they can fail with a common error message.

Also, the aux recursive call is a tail call (the last thing to do before returning). OCaml compilers will detect this and will not grow the stack with every function call (and possibly throw an exception or crash). This is what you need to know about when working with long lists and recursive functions.

To make this operation efficiently, i.e. in O (1), not O (length), you cannot use a regular list. You can use the Queue module from the standard library or the implementation of doubly linked lists provided by third parties.

Here is an example of using the Queue module:

  let rotate_queue q = if not (Queue.is_empty q) then let x = Queue.take q in Queue.add xq # 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

The Dllist module of the Batteries library may be what you are looking for. This is an imperative list structure.