I have difficulties with two problems with the langage OCaml

Question

Important: I am only allowed to use List.head, List.tail and List.length No List.map List.rev ...........etc

Only List.hd, List.tl and List.length

How to duplicate the elements of a list in a list of lists only if the length of the list is odd

Here is the code I tried:

let rec listes_paires x = 
  if x=[] then [] 
  else [List.hd (List.hd x)] 
       @ (List.tl (List.hd x)) 
       @ listes_paires (List.tl x);;

(* editor's note: I don't know where this line is supposed to go*)
if List.length mod 2 = 1 then []

For exemple:

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

returns

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

Any help would be very appreciated

thank you all

Answer 1

It looks like that your exercise is about writing recursive functions on lists so that you can learn how to write functions like List.length, List.filter, and so on.

Start with the most simple recursive function, the one that computes the length to the list. Recall, that you can pattern match on the input list structure and make decisions on it, e.g.,

let rec length xs = match xs with
  | [] -> 0 (* the empty list has size zero *)
  | hd :: tl -> 
  (* here you can call `length` and it will return you 
     the length of the list hing how you can use it to 
     compute the length of the list that is made of `tl` 
     prepended with `hd` *)
   ???

The trick is to first write the simple cases and then write the complex cases assuming that your recursive function already works. Don't overthink it and don't try to compute how recursion will work in your head. It will make it hurt :) Just write correctly the base cases (the simple cases) and make sure that you call your function recursively and correctly combine the results while assuming that it works correctly. It is called the induction principle and it works, believe me :)

The above length function was easy as it was producing an integer as output and it was very easy to build it, e.g., you can use + to build a new integer from other integers, something that we have learned very early in our lives so it doesn't surprise us. But what if we want to build something more complex (in fact it is not more complex but just less common to us), e.g., a list data structure? Well, it is the same, we can just use :: instead of + to add things to our result.

So, lets try writing the filter function that will recurse over the input list and build a new list from the elements that satisfy the given predicate,

let rec filter xs keep = match xs with
 | [] -> (* the simple case - no elements nothing to filter *)
  []
 | x :: xs -> 
   (* we call filter and it returns the correctly filtered list *)
   let filtered = filter xs keep in
   (* now we need to decide what to do with `x` *)
   if keep x then (* how to build a list from `x` and `filtered`?*)
   else filtered (* keep filtering *)

The next trick to learn with recursive functions is how to employ helper functions that add an extra state (also called an accumulator). For example, the rev function, which reverses a list, is much better to define with an extra accumulator. Yes, we can easily define it without it,

let rec rev xs = match xs with
  | [] -> []
  | x :: xs -> rev xs @ [x]

But this is an extremely bad idea as @ operator will have to go to the end of the first list and build a completely new list on the road to add only one element. That is our rev implementation will have quadratic performance, i.e., for a list of n elements it will build n list each having n elements in it, only to drop most of them. So a more efficient implementation will employ a helper function that will have an extra parameter, an accumulator,

let rev xs = 
  (* we will pump elements from xs to ys *)
  let rec loop xs ys = match xs with
    | [] -> ys (* nothing more to pump *)
    | x :: xs -> 
      let ys = (* push y to ys *) in
      (* continue pumping *) in
  loop xs []

This trick will also help you in implementing your tasks, as you need to filter by the position of the element. That means that your recursive function needs an extra state that counts the position (increments by one on each recursive step through the list elements). So you will need a helper function with an extra parameter for that counter.