convert int to natural number in ocaml

Question

I am trying to write a function that converts integers to natural numbers in OCaml. Here is my code

type nat = Zero | Succ of nat 
let rec int_to_nat (x:int):nat option=
    if x<0 then
        None
    else if x=0 then
        Some Zero
    else
        Succ(int_to_nat (x-1));;

The compiler prompts "This variant expression is expected to have type nat option.The constructor Succ does not belong to type option" error. I don't understand what does it mean.

It means what it says. Succ(...) has type nat, but ti expects a nat option, like Some (Succ ...), because that's what the other two branches of the if expression returns. They all need to return the same type, otherwise what would the type of the entire if expression be? — glennsl

sina sina · Accepted Answer · 2020-02-02T14:32:18

You should not change the type to "Succ of nat option", because the resulting type wouldn't make sense. Instead, you could return a value with the appropriate type in your function:

type nat = Zero | Succ of nat

let rec int_to_nat (x:int) : (nat option) =
  if x < 0 then None else
  match x with
  | 0 -> None
  | _ -> let y = int_to_nat (x-1) in
    match y with
    | None -> None
    | Some z -> Some (Succ z);;

However, this will lead to stack overflow for large x. You can resolve this problem by making it tail-recursive:

type nat = Zero | Succ of nat

let int_to_nat (x:int) : (nat option) =
  if x < 0 then None else
  let rec int_to_nat' (x:int) (accum:nat) : (nat option) =
    match x with
    | 0 -> Some accum
    | _ -> int_to_nat' (x-1) (Succ accum)
  in int_to_nat' x Zero;;

Regarding tail-recursion, you might find the visualizations in this blog post useful.

convert int to natural number in ocaml

2 Answers