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

Разнообразные функции расширения для модуля List. (Я потратил довольно много времени на разработку "mapfold" - который накладывает такой накопитель как сгиб, но использует его как параметр для создания новых значений, таких как 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

Ответ 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 {...}.

Ответ 2

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

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, скопированный из fssnip.net, следуйте ссылка, чтобы увидеть прокомментированный код.

Ответ 3

Функция кросспроизведения выглядит хорошо (вы, вероятно, заметили отсутствующие ключевые слова). Мне нравится эта версия 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)

Ответ 4

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

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

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

Ответ 5

Мне недавно нужно было что-то подобное - мне пришлось закрепить список последовательностей в последовательности списков - так [(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)  
   }