Вопрос по list – Как взять товар из двух списков в OCaml?

5

У меня есть два списка:

let a = ["a";"b"];
let b = ["c";"d"];

Я хочу, чтобы список вывода c, таких как:

c = ["a";"c";"a";"d";"b";"c";"b";"d"];

Как это сделать в ocaml, так как списки неизменны? Я новичок в этом.

Ваш Ответ

3   ответа
3

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

let product l1 l2 =
  List.rev (
   List.fold_left
    (fun x a ->
      List.fold_left
       (fun y b ->
         b::a::y
       )
       x
       l2
   )
   []
   l1
 )
;;

Для декартового произведения просто поменяйте

b::a::y

в

(a,b)::y
14

Вы бы вернули новый список. Если вы действительно заинтересованы вcartesian product из списков, то этого должно быть достаточно:

let cartesian l l' = 
  List.concat (List.map (fun e -> List.map (fun e' -> (e,e')) l') l)

# cartesian ["a";"b"] ["c";"d"];;
- : (string * string) list = [("a", "c"); ("a", "d"); ("b", "c"); ("b", "d")]

Если вам нужна эта странная плоская структура, вы можете использовать дополнительную конкатенацию списков.

let flat_cartesian l l' = 
  List.concat (List.concat (
    List.map (fun e -> List.map (fun e' -> [e;e']) l') l))
2

Я бы разбил проблему на две подзадачи:

  • Firstly consider a function appendeach with takes a value and a list and returns the result of adding that value infront of each item in the list

    let rec appendeach x lst = match lst with [] -> [] 
                                            | hd::tl -> x::hd::(appendeach x tl);;
    
  • Then consider a function product with takes two lists and calls appendeach for each item in the first list and the whole second list

    let rec product lst1 lst2 = match lst1 with [] -> [] | 
                                             hd::tl -> (appendeach hd lst2)@(product tl lst2);;
    

Похожие вопросы