Как рассчитать декартово произведение n списков разных типов?

Следующий код (извините, я не помню, откуда я его скопировал) вычисляет декартово (или внешнее) произведение двух списков, которые могут быть разных типов:

let outer2 xs ys = 
    xs |> List.collect (fun x -> ys |> List.map (fun y -> x, y))

Из этого можно написать функцию, которая вычисляет внешнее произведение двух списков, которые являются элементами 2-кортежа:

let outerTup tup = outer2 (fst tup) (snd tup)

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

Здесь, в SO, а также в F# Snippets, есть несколько решений проблемы, когда все списки имеют одинаковый тип (в этом случае аргумент является списком списков). Но я не видел пример, когда списки бывают разных типов.

Какие-либо предложения?

Источник

3 ответа

Решение

Теоретически, вы не можете делать то, что хотите, но можете приблизиться к этому. Причина, по которой вы не можете создать такую ​​функцию, заключается в статической типизации.

С кортежами вы можете комбинировать значения разных типов, но для обеспечения безопасности типов кортеж должен быть фиксированного размера, а тип каждого элемента должен быть известен.

Список может содержать переменное количество элементов, но из-за этого тип каждого элемента должен быть одинаковым. В противном случае вы не могли бы работать с ним на языке статической типизации.

В динамически типизированном языке вы можете, например, создать одну функцию, которая принимает список из списка (A) и другой список (B). Затем вы добавляете каждый элемент из B в каждый список внутри A, и все готово. Вы также можете сделать то же самое на языке статической типизации с двумя идеями:

  1. Вы конвертируете каждый элемент списка в object первый.
  2. Сначала вы создаете Дискриминационный Союз каждого типа.

Первая идея будет означать, что вам нужно много понижений и повышений, это обычно не то, что вы хотите в статически типизированном языке. Второй подход работает, но вы должны преобразовать каждый отдельный список в ваш тип DU (вам также нужно создать DU), и позже вам нужно будет сопоставить с шаблоном. Технически это то же самое, что и 1. только в более безопасном для типов виде.

Другой подход, и это то, что я рекомендую, это использование Applicative. Аппликатив фактически означает, что вы обновляете функцию, поэтому каждый аргумент функции может быть опцией, списком и так далее. Итак, вы сначала создаете apply функционировать так:

let apply fs xs = [
    for f in fs do
    for x in xs do
        yield f x
]
let (<*>) = apply

если у вас есть такая функция, вы можете написать что-то вроде этого:

[fun a b c d -> (a,b,c,d)]
    <*> [1..5]
    <*> ["a";"b"]
    <*> [(0,0);(1,1)]
    <*> [100;200]

Затем он возвращает список, содержащий:

[(1, "a", (0, 0), 100); (1, "a", (0, 0), 200); (1, "a", (1, 1), 100);
 (1, "a", (1, 1), 200); (1, "b", (0, 0), 100); (1, "b", (0, 0), 200);
 (1, "b", (1, 1), 100); (1, "b", (1, 1), 200); (2, "a", (0, 0), 100);
 (2, "a", (0, 0), 200); (2, "a", (1, 1), 100); (2, "a", (1, 1), 200);
 (2, "b", (0, 0), 100); (2, "b", (0, 0), 200); (2, "b", (1, 1), 100);
 (2, "b", (1, 1), 200); (3, "a", (0, 0), 100); (3, "a", (0, 0), 200);
 (3, "a", (1, 1), 100); (3, "a", (1, 1), 200); (3, "b", (0, 0), 100);
 (3, "b", (0, 0), 200); (3, "b", (1, 1), 100); (3, "b", (1, 1), 200);
 (4, "a", (0, 0), 100); (4, "a", (0, 0), 200); (4, "a", (1, 1), 100);
 (4, "a", (1, 1), 200); (4, "b", (0, 0), 100); (4, "b", (0, 0), 200);
 (4, "b", (1, 1), 100); (4, "b", (1, 1), 200); (5, "a", (0, 0), 100);
 (5, "a", (0, 0), 200); (5, "a", (1, 1), 100); (5, "a", (1, 1), 200);
 (5, "b", (0, 0), 100); (5, "b", (0, 0), 200); (5, "b", (1, 1), 100);
 (5, "b", (1, 1), 200)]

Если вы не хотите создавать оператора <*> Вы также можете написать:

[fun a b c d -> (a,b,c,d)]
    |> apply <| [1..5]
    |> apply <| ["a";"b"]
    |> apply <| [(0,0);(1,1)]
    |> apply <| [100;200]

но я обычно не рекомендую использовать <|, Я бы предпочел это вместо этого:

let ap xs fs = [
    for f in fs do
    for x in xs do
        yield f x
]

[fun a b c d -> (a,b,c,d)]
    |> ap [1..5]
    |> ap ["a";"b"]
    |> ap [(0,0);(1,1)]
    |> ap [100;200]

Единственное, что вы должны создать на лету - это первая линия. Функция, которая отображает четыре, пять, шесть,... аргументов в кортеж.

Если вы хотите узнать больше о Applicatives и о том, как он работает, я написал две публикации в блоге на эту тему:

http://sidburn.github.io/blog/2016/04/13/applicative-list http://sidburn.github.io/blog/2016/03/31/applicative-functors

Источник

Это не решение для п. Использование пространства имен отражения FSharp обычно нежелательно.

let outer2 xs ys = 
  xs |> List.collect (fun x -> List.map (fun y -> x, y) ys)

let outerTup2 (a,b) = outer2 a b

let outerTup3 (a,b,c) = 
  a
  |> outer2 b
  |> outer2 c
  |> List.map (fun (c,(b,a))->a,b,c)

let outerTup4 (a,b,c,d) =
  a
  |> outer2 b
  |> outer2 c
  |> outer2 d
  |> List.map (fun (d,(c,(b,a)))->a,b,c,d) 

// etc...

outerTup2 ([1;2],[3;4])

outerTup3 ([1;2],[3;4],[5;6])

outerTup4 ([1;2],[3;4],[5;6],[7;8])
Источник

В соответствии с этим вопросом Stackru может оказаться невозможным написать функцию, которая принимает в качестве аргумента кортеж любой длины.

Кортежи переменной длины в F#

Этот вопрос задан давно, и я не уверен, есть ли в F# какие-либо обновления и изменения, которые делают это возможным.

Источник
Другие вопросы по тегам