Write a function that returns every other element of the list

Question

I want to write a function that can return every other element of the list like this ['a' ; 'b' ; 'c' ; 'd' ; 'e'] can return: ['a' ; 'c' ; 'e'] My function can use only with predefined functions List.hd, List.tl or List.length. I wrote this but I think something wrong...

remove_half l =
  let rec rm_half n l =
    if l = [] then []
    else
      let fst = hd l in
      let rest = tl l in
      if n then fst :: (rm_half (not n) rest) 
      else (rm_half (not n) rest) 
  in
  rm_half true l;;

Answer 1

As it is, your code is missing a let and you haven't shown that you've opened List. If we fix those little things by adding the let and fully qualifying List.hd and List.tl:

# let remove_half l =
    let rec rm_half n l =
      if l = [] then []
      else
        let fst = List.hd l in
        let rest = List.tl l in
        if n then fst :: rm_half (not n) rest
        else rm_half (not n) rest
    in
    rm_half true l;;
val remove_half : 'a list -> 'a list = <fun>

# remove_half [1; 2; 3; 4; 5; 6];;
- : int list = [1; 3; 5]

Bingo. It works.

Now, this can be cleaned up using pattern-matching rather than List.hd and List.tl. The boolean is no longer necessary given that we can pattern match on the first two elements of a list with at least two elements.

let rec remove_half =
  function
  | x::_::xs -> x :: remove_half xs
  | lst -> lst 

This technique can be applied using List.hd and List.tl.

let rec remove_half lst =
  if lst = [] || List.tl lst = [] then lst
  else 
    let x = List.hd lst in
    let xs = List.tl (List.tl lst) in
    x :: remove_half xs