Перекрестное произведение двух списков

Question

Возиться с "функциями расширения" для модуля List. (Я потратил довольно много времени на разработку "mapfold" - в котором используется накопитель, такой как fold, но использовал его в качестве параметра для создания новых значений, таких как map, - потом обнаружил, что это то, что List.scan_left делает)

Для генерации тестовых данных мне нужно было создать перекрестный продукт из двух списков. Вот что я придумал:

///Perform cross product of two lists, return tuple
let crossproduct l1 l2 =
    let product lst v2 = List.map (fun v1 -> (v1, v2)) lst
    List.map_concat (product l1) l2

Это хорошо, или уже есть какой-то лучший способ сделать это?

Тот же вопрос для этого:

///Perform cross product of three lists, return tuple
let crossproduct3 l1 l2 l3 =
    let tuplelist = crossproduct l1 l2 //not sure this is the best way...
    let product3 lst2 v3 = List.map (fun (v1, v2) -> (v1, v2, v3)) lst2
    List.map_concat (product3 tuplelist) l3

Answer 1

Другой вариант - использовать F# "выражения последовательности" и написать что-то вроде этого:

let crossproduct l1 l2 =
  seq { for el1 in l1 do
          for el2 in l2 do
            yield el1, el2 };;

(на самом деле, это почти то же самое, что вы написали, потому что "for .. in .. do" в выражении последовательности можно рассматривать как map_concat). Это работает с (ленивыми) последовательностями, но если вы хотите работать со списками, вам нужно просто обернуть код внутри [ ... ], а не внутри seq { ... }.

Answer 2

Начиная с F# 4.0, вы можете использовать List.allPairs дать декартово произведение двух списков. Если у вас есть n списков, см. Как вычислить декартово произведение n последовательностей в F#?

Answer 3

Просто наткнулся на довольно элегантное решение для этого с помощью выражений вычислений:

type Product () =
  member this.Bind (l,f) = List.collect f l    
  member this.Return n = [n]

let enumeratedPizzas = 
  Product() {
    let! x = ["New York";"Chicago"]
    let! y = ["Pepperoni";"Sausage"]
    let! z = ["Cheese";"Double Cheese"]
    return x,y,z
  }

По TechNeilogy, скопированный с http://fssnip.net/4L, перейдите по ссылке, чтобы увидеть закомментированный код.

Answer 4

Некоторое время я пользовался ответом Бенджола, пока не обнаружил, что вы можете сделать то же самое с Linq, Решение Benjol, вероятно, все еще самое элегантное, но если кто-то хочет решение, которое вы можете использовать с C# также тогда вы идете:

query {
  for i in [1, 2] do
  for j in [3, 4] do
  select (i, j)
}

Что почти совпадает с решением Томаса Петричека, за исключением того, что решение не нуждается во вложении for петли, так что это немного проще.

Answer 5

Ваша перекрестная функция выглядит хорошо (вы, вероятно, заметили пропущенные ключевые слова "in"). Мне больше нравится эта версия crossproduct3, но это только я:

let crossproduct3 l1 l2 l3 = 
List.map_concat 
(fun z ->
 (List.map_concat (fun y -> List.map (fun x -> (x, y, z)) l3) l2)) l1;;

Ваша функция имеет эквивалентную алгоритмическую сложность.

Наконец, при использовании перекрестного продукта в явно пустом списке вы можете столкнуться с ограничением значения (грубо говоря, ограничением, которое гарантирует, что компилятор выводит только полиморфные типы для синтаксического значения), что особенно строго в F#. Решение состоит в том, чтобы аннотировать вызовы, которые используют пустой список, следующим образом (если вы хотите, чтобы второй список состоял из целых чисел):

(crossproduct [3; 4] [] : (int * int) list)

Answer 6

Недавно мне нужно было что-то похожее - мне пришлось заархивировать список последовательностей в последовательность списков - так [(a1,a2,a3,...);(b1,b2,b3,...);(c1,c2,c3,...)] -> ([a1;b1;c1], [a2;b2;c3], ...)

Следующий код сделает это:

   let rec listZip (sl : 'a seq list) =   
       seq {  
           match sl with  
           | [] -> yield []  
           | hd::tl ->  
              for h in hd do  
              for t in listZip tl do  
              yield (h::t)  
   }