building a list of ints in ocaml

Question

I want to write a function that does builds a list between two ints, inclusive

rec myFunc x y would build a list with all the ints between x and y, including x and y

For the logic right now I have something like this:

let rec buildList i n = let x = i+1 in if i <= n then i::(buildList x n)

But this gives me an error "Expression has type 'a list but but an expression was expected of type unit.

I thought buildList is returning a list of ints, and i as an int, so the cons operator would be valid, but its saying it should be void?

Why does this happen, and how do I fix it?

Answer 1

If the condition is true, you return the list i::(buildList x n). If it's not true, what do you return ?

Add else [] to your function to return the empty list when the condition is not met. When you don't have any else, the compiler supposes it is else () (hence the error message).

Answer 2

Your if is missing an else condition

I suggest that you use a tail recursive function:

let buildList x y =
  let (x,y) = if x<y then (x,y) else (y,x) in
  let rec aux cpt acc =
      if cpt < x then acc
      else aux (cpt-1) (cpt::acc)
  in aux y []

First, make sure that you ordered your boundaries correctly (idiot-proof), and then construct the list thank to a local recursive function which takes an accumulator.

Answer 3

Two alternatives relying on batteries' package,

Using unfold, which purpose is to build list,

let range ~from:f ~until:u = 
    BatList.unfold f (function | n when n <= u -> Some (n, succ n) | _ -> None)

Using Enum, allowing to work with lazy datastructure,

# BatList.of_enum @@ BatEnum.(1--9);;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

Answer 4

My suggestion, this respects the ordering of the arguments.

let rec iota n m = 
  let oper = if n < m then succ else pred  in 
    if n = m then [n] else n :: iota (oper n) m

Edit:

The operator selection is inside the recursive part, it should better be outside like this:

let iota n m = 
  let oper = if n < m then succ else pred  in 
    let rec f1 n m = if n = m then [n] else n :: f1 (oper n) m in
      f1 n m

At more than 200000 elements I get a stack overflow (so here we are)

# iota 0 250000;;
Stack overflow during evaluation (looping recursion?).

Todo: tail recursion

Answer 5

let buildList i n =
 let rec aux acc i =
   if i <= n then
     aux (i::acc) (i+1)
   else (List.rev acc)
 in
 aux [] i

Test:

# buildList 1 3;;
- : int list = [1; 2; 3]
# buildList 2 1;;
- : int list = []
# buildList 0 250000;;
- : int list =
[0; 1; 2; 3; .... 296; 297; 298; ...]