OCaml: pell function with int lists

Question

I am trying to write a simple function in OCaml

let rec pell (i: int) =
(if i <= 2 then i (*if given n is less tahn 2 then return 2, else return previous n-1 th term and n-2 nd term recursively*)
  else if i>2 then
  2 * pell i - 1 + pell i - 2

else failwith "unimplemented" (*else fail with unimplemented message*)
);;

Write an infinite precision version of the pell function from before

pell2 0 = []

pell2 1 = [1]

pell2 7 = [9; 6; 1]

pell2 50 = [2; 2; 5; 3; 5; 1; 4; 2; 9; 2; 4; 6; 2; 5; 7; 6; 6; 8; 4]

I have written below code for this:

let rec pell2 i =

(if i <= 2 then
  [] -> i;
  else if i=0 then [];
  else if i>2 then                                (*finding pell number and using sum function to 
output list with infinite precision...*)
  [] -> pell2 i-1 + pell2 i-2;

else failwith "unimplemented"

);;

but still has some syntax errors. Can someone help me with this please.

Answer 1

if i <= 2 then
     [] -> i

In snippets like this, the -> is invalid. It looks like you might be mixing pattern matching with match ... with ... and if/else up.

Also, you're first checking if i is less than or equal to 2, but then you have an else to test for i being equal to zero. The first check means the second is never going to happen.

Answer 2

First, let's look at the examples for the output of pell2. We see that pell2 has a single integer parameter, and returns a list of integers. So, we know that the function we want to create has the following type signature:

pell2: int -> int list

Fixing (some but not all of) the syntax errors and trying to maintain your logic,

let rec pell2 i =
  if i=0 then []
  else if i <= 2 then i
  else if i>2 then pell2 i-1 + pell2 i-2

Note that I removed the semicolons at the end of each expression since OCaml's use of a semicolon in its syntax is specifically for dealing with expressions that evaluate to unit (). See ivg's excellent explanation on this. The major flaw with this code is that it does not type check. We see that we conditionally return a list, and otherwise return an int. Notice how above we defined that pell2 should return an int list. So, we can begin fixing this by wrapping our int results in a list:

let rec pell2 n = 
  if n = 0 then []
  else if n <= 2 then [n]
  else ... something that will return the Pell number as a list ...

As you have already written, the else branch can be written using recursive calls to the pell2 function. However, we can't write it as you did previously, because pell2 evaluates to a list, and the binary operator + only works on two integers. So, we will have to define our own way of summing lists. Calling this sum_lists, we are left with the following code: We can now fully define our function pell2:

let rec pell2 n =
  if n = 0 then []
  else if n <= 2 then [n]
  else (* Pell(n) = (2 * Pell(n-1)) + Pell(n-2) *)
    let half_of_first_term = pell2 n-1 in
    let first_term = sum_lists half_of_first_term half_of_first_term in
    let second_term = pell2 n-2 in
    sum_lists first_term second_term

So, all that is left is to define sum_lists, so that we are properly summing together two lists of the same format as the return type of pell2. The signature for sum_lists would be

sum_lists: int list -> int list -> int list

I'll give a basic outline of the implementation, but will leave the rest for you to figure out, as this is the main crux of the assignment problem.

let sum_lists lst1 lst2 =
  let rec sum_lists_helper lst1 lst2 carry =  
    match lst1, lst2 with
    | [], [] -> if carry = 1 then [1] else []
    | h::t, []
    | [], h::t -> ...
    | h1::t1, h2::t2 -> ...
  in
  sum_lists_helper lst1 lst2 0