CODEWITHSUNDEEP
listocamlint
Michael L
Michael L

Reputation: 33

building a list of ints in ocaml

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?

Upvotes: 3

Views: 10445

Answers (5)

Str.
Str.

Reputation: 1439

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

Upvotes: 0

V. Michel
V. Michel

Reputation: 1619

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; ...]

Upvotes: 0

Hugo
Hugo

Reputation: 535

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.

Upvotes: 3

zurgl
zurgl

Reputation: 1930

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]

Upvotes: 1

Laurent
Laurent

Reputation: 2999

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

Upvotes: 7

Related Questions