Recursive function dealing with parity between list elements and an int

Question

This function should take two arguments a list and an int. if an element of the list and the number “a” parity is equal then they’d have to be summed, else the two numbers should be subtracted.

The calculation should be done in this order :

• At the beginning, the residual value r is the value of a,
• Each element e of lst (taken in the order given by the list) affects the residual value: if e and r are of the same parity (both odd or both even) then the new r’ is equal to the sum of r + e, if not then it should be equal to the subtraction of r - e,
• The last r is the result expected.

To put this into an example:

par [4;7;3;6] 5
should return -1, it would work as follows :
5 and 4 have a different parity so we subtract -> 5 - 4 = 1
1 and 7 are both odd, so we add them together -> 1 + 7 = 8
8 and 3 have a different parity -> 8 - 3 = 5
Finally, 5 and 6 have different parity -> 5 - 6 = -1

I have thought of something like this below :

let rec par lst a = 
match lst with 
| [] -> 0
| h::t -> if (h mod 2 == 0 && a mod 2 == 0) || (h mod 2 == 1 && a mod 2 == 1) then a + h
| h::t -> if (h mod 2 == 0 && a mod 2 == 1) || (h mod 2 == 1 && a mod 2 == 0) then a - h :: par t a ;;

EDIT1 : Here is the error I get from the compiler :

Line 4, characters 83-88: Error: This expression has type int but an expression was expected of type unit because it is in the result of a conditional with no else branch

The idea is to build this function using no more than the following predefined functions List.hd, List.tl et List.length.

What is disturbing in my proposition above and how to remediate it?

EDIT 2: I was able to do what is needed with if...then... else syntax (not the best I know for OCaml) but I personally have more difficulties sometimes understanding the pattern matching. Anyhow here's what I got :

let rec par lst a =  (* Sorry it might hurt some sensible eyes *)  
  if List.length lst = 0 then a
  else
    let r = if (List.hd lst + a) mod 2 == 0 then (a + (List.hd lst))
      else (a - (List.hd lst)) in
    par (List.tl lst) r ;;
val par : int list -> int -> int = <fun>

Answer 1

This is a natural situation for a fold, but you can't use List.fold_left, so let's re-implement it using the functions you can use.

# let rec fold_left f i lst =
    if lst = [] then i
    else
      let x = List.hd lst in
      let xs = List.tl lst in
      fold_left f (f i x) xs;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

This is even more straightforward if we use pattern-matching.

let rec fold_left f i = 
  function
  | [] -> i 
  | x::xs -> fold_left f (f i x) xs

Now we just need a function to run on each iteration of the fold.

# let even x = x mod 2 == 0 in
  let odd x = not @@ even x in
  let parity a b = (even a && even b) || (odd a && odd b) in
  fold_left 
    (fun a b -> 
       if parity a b then a + b 
       else a - b) 
    5 
    [4; 7; 3; 6];;
- : int = -1

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  5 
  [4; 7; 3; 6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  1 
  [7; 3; 6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  8 
  [3; 6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  5 
  [6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  (-1) 
  []

-1

Answer 2

Your code doesn't compile. Did you try compiling it? Did you read the errors and warnings produced by the compiler? Could you please add them to your question?

A few comments about your code:

• | h::t -> if ... then ... should be | h::t when ... -> ...;
• (h mod 2 == 0 && a mod 2 == 0) || (h mod 2 == 1 && a mod 2 == 1) can be simplified to (h - a) mod 2 == 0;
• The compiler likes to know that the matching was exhaustive; in particular, you don't need to repeat the test in the third line of the matching (the third line will only be read if the test was false in the second line);
• You are missing the recursive call in the second line of the matching;
• In the third line of the matching, you are returning a list rather than a number (the compiler should have explicitly told you about that type mismatch!! did you not read the compiler error message?);
• In the first line of the matching, in case the list is empty, you return 0. Are you sure that 0 is the value you want to return, when you've reached the end of the list? What about the residual value that you have calculated?
• Once you have fixed this version of your code as a recursive function, I recommend trying to write a code solving the same problem using List.fold_left, rather than List.hd and List.tl as you are suggesting.

When I first wrote my answer, I included a fixed version of your code, but I think I'd be doing you a disservice by handing out the solution rather than letting you figure it out.