ocaml

How to remove every other element from a list only using List.hd, List.tl, and List.length


Write a function that removes every other element from a list. ['d'; 'o'; 'u'; 'c'; 'h'; 'e'; 'c'; 'a'; 'n'; 'o'; 'e'] -> ['d'; 'u'; 'h'; 'c'; 'n'; 'e']

It has to be a recursive method, and you can ONLY use List.hd, List.tl, and List.length, all the others are no bueno.

Here's an example of a function to remove the last element of a list: it should apparently be done similarly:

let rec rm_last_element l = 
    if  List.tl  l = [] 
      then []  
    else List.hd l :: remove_last(List.tl l);;

Solution

  • Consider what a list in OCaml looks like:

    [1; 4; 6; 3; 8; 9; 10] can be written as 1 :: 4 :: 6 :: 3 :: 8 :: 9 :: 10 :: [].

    We can pattern match against a list. (Expanding on what Butanium showed.)

    match [1; 4; 6; 3; 8; 9; 10] with
    (* The case of an empty list *)    
    | [] -> 
    (* The case of a list with a single element,
       where the single element has the value 1. *)
    | elt :: [] -> 
    (* The case of a list with at least two elements, 
       where elt1 is 1, and elt2 is 4 and 
       rest is [6; 3; 8; 9; 10] *)
    | elt1 :: elt2 :: rest ->
    

    If you want to drop every other element, what would each case need to return? What would we get if we did the same match on [6; 3; 8; 9; 10]? What would elt1, elt2, and rest be in that case?