Return a list of tuples inside a rectangular range

Question

As a beginner in OCaml, I'm trying to write a function who takes two int arguments (a and b), and should return a list which contains all tuples (i,j) where i is between 0 and a, and j is between 0 and b, order doesn't matter. The function should be like this : myfunc: int -> int -> (int*int) list And result must be something like [(0,1);(0,2)]...

I already wrote a function who takes two int argument and return a list between those two. For example, 1 and 5 give me this list : [1;2;3;4;5]. This is what i've done :

let rec btwn = fun a b -> if a>b then []
                       else if a = b then [a]
                       else a :: btwn (a+1) b ;;

My idea was to reuse this function, and create two list : one list with the range 0 ; a and one another with the range 0 ; b, and then making all tuples with these two lists. I've heard of List.fold_left/right, List.map but I can't get it work... Do you have any ideas ? Thanks!

Answer 1

If you want to reuse btwn, you basically want to implement this::

fun a b -> 
  let la = btwn 0 a
  and lb = btwn 0 b
  in cartesian_product la lb;;

Now, you only need to implement cartesian_product, which is basically two nested loops: the outer loop iterates of elements a from la, and for each a, you iterate over all elements b from lb to build a list [(ai,b0), ..., (ai,bj)]. You then have to concatenate all lists (the one for a0, then a1, etc.).

In pseudo-code, that would be:

R = []
loop for a in la:
  R := append(R, [(a,b) for b in lb])

But instead of concatenating, you can thread the resulting list in parameters and intermediate return values to ensure you always only add elements in front, which takes constant time:

let cross_product la lb =
  let rec outer sofar la =
    match la with
    | [] -> sofar
    | a::la -> 
       let rec inner sofar lb =
         match lb with
         | [] -> sofar
         | b::lb -> (inner ((a,b)::sofar) lb)
       in outer (inner sofar lb) la
  in outer [] la;;

If you don't mind having a local mutable state, a somewhat simpler approach would be:

open List;;
let cross_product la lb =
  let stack = ref []
  in iter (fun a -> iter (fun b -> stack := (a,b)::!stack) lb) la;
     !stack;;

Answer 2

The following code works:

let createTuples (i:int) (j: int)=
      let rec helper1 acc i j=
        match i with 
        |0 -> (0,j)::acc
        |q -> helper1 ((q,j)::acc) (q-1) j
      in let rec helper2 acc p o=
           match o with
           |0 -> (helper1 [] p 0)@acc
           |q -> helper2 ((helper1 [] p q)@acc) p (o-1)
      in helper2 [] i j

The code works by iterating through the two given indices 0< i < n and 0 < j < m ; The first helper function creates tuples of the form (0,j), (1,j)...,(n,j).Basically iterating through I given a fixed j. And the second iterate through values of j.