Вернуть список кортежей внутри прямоугольного диапазона

Question

Как новичок в OCaml, я пытаюсь написать функцию, которая принимает два аргумента int (a и b) и должна возвращать список, который содержит все кортежи (i,j), где i находится между 0 и a, а j - между 0 и b, порядок не имеет значения. Функция должна быть такой: myfunc: int -> int -> (int*int) list И результат должен быть чем-то вроде [(0,1);(0,2)]...

Я уже написал функцию, которая принимает два аргумента int и возвращает список между этими двумя. Например, 1 и 5 дают мне этот список: [1;2;3;4;5]. Вот что я сделал:

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

Моя идея состояла в том, чтобы повторно использовать эту функцию и создать два списка: один список с диапазоном 0; а и друг с другом в диапазоне 0; б, а затем сделать все кортежи с этими двумя списками. Я слышал о List.fold_left/right, List.map, но не могу заставить его работать... У вас есть идеи? Спасибо!

Answer 1

Если вы хотите использовать повторно btwnВы в основном хотите реализовать это:

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

Теперь вам нужно только реализовать cartesian_product, в основном это два вложенных цикла: внешний цикл повторяет элементы a от laи для каждого aперебираете все элементы b от lb составить список [(ai,b0)..., (ai,bj)], Затем вы должны объединить все списки (один для a0, затем a1, так далее.).

В псевдокоде это будет:

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

Но вместо конкатенации вы можете связать результирующий список с параметрами и промежуточными возвращаемыми значениями, чтобы гарантировать, что вы всегда добавляете только элементы впереди, что занимает постоянное время:

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

Если вы не возражаете против наличия локального изменяемого состояния, несколько более простой подход будет следующим:

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

Следующий код работает:

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

Код работает путем итерации двух заданных индексов 0

Answer 3

Это очень просто сList.mapиList.concat_map(для создания «плоского» списка).

      # let product a b =
    List.concat_map 
      (fun x -> List.map (fun y -> (x, y)) b) 
      a;;
val product : 'a list -> 'b list -> ('a * 'b) list = <fun>
# product [1;2;3] [4;5;6];;
- : (int * int) list =
[(1, 4); (1, 5); (1, 6); (2, 4); (2, 5); (2, 6); (3, 4); (3, 5); (3, 6)]