Easiest way to remove the last element from list

Question

I am writing a function that will take a list of integers, for example :

let x = [1..5]

and should return a shuffled list like below :

[1;5;2;4;3]

So, it should take first element and then last, then 2nd element and before last and so on...

I have written this function so far:

let rec reshuffle list: List<int> =
  match list with
  | [] -> []
  | head :: tail -> [head;list |> List.last] @reshuffle tail

I am getting this answer :

[1; 5; 2; 5; 3; 5; 4; 5; 5; 5]

It seems that is because each time the function is being recursively done, the last element is not being removed. How do I remove both head and tail in the function?

Answer 1

If we assume no library function is allowed and trying to avoid processing the list again and again for "nothing", I propose this.

We first reverse the initial list, that is done only once.
We traverse those pair of lists and stop half way, accumulating the current item from both lists. The starting accumulator is either empty or contain the "middle" item depending if the initial list's length is odd/even.

For that we need a function to reverse a list :

let reverse xs =
  let rec aux acc = function
    | []      -> acc
    | x :: xs -> aux (x :: acc) xs
  aux [] xs

Then we need a function to get the length of a list :

// not tail-rec
let rec length = function
  | []      -> 0
  | _ :: xs -> 1 + length xs

Finally we can write the required function :

let reshuffle xs =
  let reversed = reverse xs

  let rec aux acc = function
    | -1    -> acc
    | index -> let newAcc = xs.[index] :: reversed.[index] :: acc
               aux newAcc (index - 1)

  let theLength = length xs
  let startAcc = if theLength % 2 = 0
                 then []
                 else [ xs.[theLength / 2] ]

  aux startAcc (theLength / 2 - 1)

Alternatively, if you think recursing on some index feel as some kind of "cheating" and the recursion should occur on list you could use this instead :
(Which is shorter but will do "double" job, one half for "nothing")

let reshuffle xs =
  let rec aux acc = function
    | x :: xs, r :: rs -> aux (r :: x :: acc) (xs, rs)
    | _                -> acc

  let full = aux [] (xs, reverse xs)
  full.[.. length xs - 1]

We build the full list of "pairs" so we get a list with double size from the initial and symmetric.
And from that we only return the "length" first.