Ocaml : function that two integers and returns the list of all integers in the range

This function takes two integers and returns the list of all integers in the range [a,b]

This is the solution that I wrote.

let rec range_rec l a b = 
  if (a=b) then l@[b]
  else range_rec (l@[a], a+1, b);;

let range a b = range_rec [] a b;;

I'm hitting an error "Error: This expression has type int list * int * int but an expression wa开发者_Go百科s expected of type int". Can someone throw some light on why am I getting this error?

Thanks.

It should look like this:

let rec range_rec l a b = 
  if a = b then l @ [b]
  else range_rec (l @ [a]) (a + 1) b;;

let range a b = range_rec [] a b;;

What I've done:

1. Changed loop to range_rec
2. Changed (l@[a], a+1, b) to (l @ [a]) (a + 1) b. The first is a triplet and the second is 3 arguments to a curried function.
3. Notice that if (a = b) then can be written as if a = b then.

Last, the function can be made more efficient by using :: instead of @ by looping "backwards". For example like gasche have shown.

The l @ [elem] operation is terrible from a performance perspective : as a @ b is linear in the length of a, adding an element to the end of list is linear in the length of the list, making your whole range_rec definition quadratic in |b-a|. The way to go is to change your code so that you can use the constant-time elem::l operation instead.

let rec range a b =
  if a > b then []
  else a :: range (a + 1) b

You may make additional optimizations such as making it tail-recursive, but at least the complexity of this solution is right.

To improve on the solution already suggested by gasche, this can be made tail-recursive.

let int_range a b =
  let rec int_range_rec l a b =
    if a > b then l
    else int_range_rec (b :: l) a (b - 1)
  in (int_range_rec [] a b);;