Return 矩形范围内的元组列表

Question

作为 OCaml 的初学者，我正在尝试编写一个接受两个 int 参数（a 和 b）的函数，并且应该 return 一个包含所有元组 (i,j) 的列表，其中 i介于 0 和 a 之间，j 介于 0 和 b 之间，顺序无关紧要。该函数应该是这样的：myfunc: int -> int -> (int*int) list 结果必须类似于 [(0,1);(0,2)]...

我已经写了一个函数，它接受两个 int 参数和 return 这两个参数之间的列表。例如，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 的列表； a 和另一个范围为 0 ； b，然后用这两个列表制作所有的元组。我听说过 List.fold_left/right, List.map 但我无法让它工作... 你有什么想法？谢谢！

Answer 1

以下代码有效：

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< i < n 和 0 < j < m ;第一个辅助函数创建形式为 (0,j)、(1,j)...,(n,j) 的元组。基本上迭代 I 给定一个固定的 j。第二次遍历 j.

的值

Answer 2

如果你想重用btwn，你基本上是想实现这个::

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

现在，您只需要实现 cartesian_product，这基本上是两个嵌套循环：外层循环从 la 迭代元素 a，并且对于每个 a，您遍历 lb 中的所有元素 b 以构建列表 [(ai,b0)，...，(ai,bj)]。然后，您必须连接所有列表（a0 的列表，然后是 a1，等等）。

在伪代码中，这将是：

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

但是，您可以将结果列表放入参数和中间 return 值中，而不是串联，以确保您始终只在前面添加元素，这需要常数时间：

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

Return 矩形范围内的元组列表

Return a list of tuples inside a rectangular range

ocaml

fold