Ocaml - Move last element of list to front

4
votes

First off, I apologize if this is a confusing or backwards way to go about what I want to accomplish, but I'm new to "Ocaml style".

I want to take the last element of a list, and move it to the front of the list, shifting all the elements up one.

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

I understand that lists in Ocaml are basically linked list, so I plan to recursively iterate through the list, find the last element, and then have that element's tail/remaining list point to the head of the list.

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

How do I accomplish this, and is there a simpler way to look at this that I'm completely missing?

4
listrecursionlinked-listocaml
As a note to complement Joshua Smith/nlucaroni's answer below, if you often want to move the last element to top, lists are the wrong representation, since all the nodes need to be reallocated. You could use lists with updatable tails—if you are very confident that sharing won't cause issues - Pascal Cuoq
Pascals correct; there also zippers with tail access. - nlucaroni

4 Answers

7
votes

You can't "Break the link" because Ocaml lists are a persistent data-structure. You can't really modify the lists, so you have to produce 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 could 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]
3
votes

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

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

A safe implementation is the following:

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

It is safe in the sense that passing the empty list returns the empty list instead of raising an exception. Note that I strongly discourage the use of List.hd and List.tl because they may fail, with a generic error message.

Also, the recursive call to aux is a tail call (last thing to do before returning). The OCaml compilers will detect this and avoid growing the stack with each function call (and possibly raise an exception or crash). This is something to be aware of when dealing with long lists and recursive functions.

In order to do this operation efficiently, i.e. in O(1) rather than O(length), you cannot use a regular list. You can use the Queue module from the standard library or implementations of doubly-linked lists provided by third parties.

Here is an example using the Queue module:

 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 = ()
 #
0
votes

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