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

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

0 голосов
/ 13 января 2019

Как новичок в 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, но не могу заставить его работать ... Есть ли у вас какие-либо идеи ? Спасибо!

Ответы [ 2 ]

0 голосов
/ 13 января 2019

Если вы хотите повторно использовать 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;;
0 голосов
/ 13 января 2019

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

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

...