Декартово произведение (улучшение сложности)

Question

Я хочу написать функцию, которая дает декартово произведение двух последовательностей, это то, что я сделал, но я подумал, что может быть интересно иметь меньшую сложность с тем, что я хочу просмотреть один раз первую последовательность s1 и n раз вторую, используя картуи затем добавьте все результаты:

`let cartesian_product a b =
    let na = length a in
    let nb = length b in
    init
    (na * nb)
    (fun j -> let i = j / nb in
      at a i, at b (j - i*nb))
`

---

это то, что я сделал на данный момент:

`let rec cartesian_product a b =
 let rec aux x b () = match b () with
  | Nil -> Nil
  | Cons(e, b) -> Cons ((x, e), aux x b)
 in
 match a () with
 | Nil -> nil
 | Cons (x, a)  -> append (aux x b) (cartesian_product a b)`

но я не использовал карту (есть ли лучший способ дляделает это) ??

Answer 1

Вот пример алгоритма со структурой списка:

let cartesian_product a b =
  let open List in
  let mk_tuple l n = map (fun x -> (n,x)) l in  
   a |> map (mk_tuple b) |> fold_left append []

Это даст вам:

    cartesian_product [0;1] [2;3];;
    - : (int * int) list = [(0, 2); (0, 3); (1, 2); (1, 3)]

Answer 2

Ваша aux функция - это, по сути, особый случай map, поэтому вы можете написать:

let rec cartesian_product a b = match a () with
  | Nil -> Nil
  | Cons (x, a)  -> append (map (fun e -> (x, e)) b) (cartesian_product a b)

Как правило, когда вы чувствуете необходимость написать функцию с именем aux,сделайте шаг назад и подумайте, можете ли вы использовать map или fold.Фактически, вы можете улучшить мой код, используя fold вместо того, чтобы деконструировать последовательность самостоятельно.