1

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 was expected of type int". Can someone throw some light on why am I getting this error?

Thanks.

2
  • What did you think "loop" was going to do? Aug 28, 2011 at 11:37
  • Sorry Chris. That was a typo. I was trying to make it more clear. Aug 28, 2011 at 12:30

3 Answers 3

7

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.

3
  • Sorry. The 1st change was actually a typo. But it wasnt there in the actual program. You mean to say, I had to have additional braces surrounding (a+1) and I had to remove the braces surrounding the 3 arguments? Why is that? Aug 28, 2011 at 12:42
  • @Sunday Something ala let rec f (a, b) = is a function which takes a tuple in Ocaml. Where let rec f a b = is really a function, which returns a function. It is not like C-like languages. See "Functions" in files.metaprl.org/doc/ocaml-book.pdf or caml.inria.fr/pub/docs/oreilly-book/ocaml-ora-book.pdf - It is really difficult to explain the type-system and functions in short space :) Aug 28, 2011 at 20:04
  • 1
    Thanks Lasse. I cant give reputation to your answer cuz I'm a newbie. I hope someone gives it. Aug 29, 2011 at 1:53
6

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.

4
  • Good advice, but you haven't answered the question. Aug 28, 2011 at 11:36
  • Thanks Gasche. Any idea why my function was bumping into error? Aug 28, 2011 at 13:14
  • @Chris: sometimes one is interested in answers that go beyong what was explicitely asked. lasseespeholt already proposed a fix for the syntactic mistake. If you're interested into giving a detailed explanation of why f (x, y, z) and f x y z are typed differently, please do.
    – gasche
    Aug 28, 2011 at 22:08
  • Thanks Gasche. I cant give reputation to your answer cuz I'm a newbie. I hope someone gives it Aug 29, 2011 at 1:53
1

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);;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.