F # возвращает пары элементов в списке

Question

Я искал элегантный способ написать функцию, которая принимает список элементов и возвращает список кортежей со всеми возможными парами различных элементов, не принимая во внимание порядок, т. Е. (A, b) и ( б, а) следует считать одинаковыми и вернуть только один из них. Я уверен, что это довольно стандартный алгоритм, и это, вероятно, пример с титульной страницы документации F #, но я не могу его найти, даже не ища в Интернете SML или Caml. Я придумал следующее:

let test = [1;2;3;4;5;6]

let rec pairs l = 
    seq { 
        match l with
        | h::t -> 
            yield! t |> Seq.map (fun elem -> (h, elem))
            yield! t |> pairs
        | _ -> ()
        }

test |> pairs |> Seq.toList |> printfn "%A"

Это работает и возвращает ожидаемый результат [(1, 2); (1, 3); (1, 4); (1, 5); (1, 6); (2, 3); (2, 4); (2, 5); (2, 6); (3, 4); (3, 5); (3, 6); (4, 5); (4, 6); (5, 6)] но это выглядит ужасно однотипно. Мне не нужно проходить через выражение последовательности и затем преобразовывать обратно в список, должно быть эквивалентное решение, включающее только базовые операции со списком или библиотечные вызовы ...

Отредактировано:

У меня также есть этот здесь

let test = [1;2;3;4;5;6]

let rec pairs2 l =
    let rec p h t =
        match t with
        | hx::tx -> (h, hx)::p h tx
        | _ -> []
    match l with
    | h::t -> p h t @ pairs2 t
    | _ -> []


test |> pairs2 |> Seq.toList |> printfn "%A"

Также работает, но, как и первый, он кажется излишне сложным и сложным, учитывая довольно легкую проблему. Я думаю, что мой вопрос больше о стиле, и если кто-то может придумать для этого двухслойный.

Answer 1

Я думаю, что ваш код на самом деле довольно близок к идиоматической версии.Единственное изменение, которое я сделал бы, это то, что я бы использовал for в выражении последовательности вместо использования yield! в сочетании с Seq.map.Я также обычно форматирую код по-другому (но это просто личное предпочтение), поэтому я бы написал так:

let rec pairs l = seq {  
    match l with 
    | h::t -> for e in t do yield h, elem
              yield! pairs t
    | _ -> () } 

Это практически то же самое, что опубликовал Брайан.Если вы хотите получить список в качестве результата, вы можете просто обернуть все это в [ ... ] вместо seq { ... }.

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

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

let splits list = 
  let rec splitsAux acc list =
    match list with 
    | x::xs -> splitsAux ((x, xs)::acc) xs
    | _ -> acc |> List.rev
  splitsAux [] list

Например, splits [ 1 .. 3 ] даст [(1, [2; 3]);(2, [3]);(3, [])] .Когда у вас есть эта функция, реализация вашей первоначальной задачи становится намного проще - вы можете просто написать:

[ for x, xs in splits [ 1 .. 5] do
    for y in xs do yield x, y ]

В качестве руководства для поиска в Google - проблема называется поиском всех 2-элементных комбинаций из данного набора.

Answer 2

Вот один из способов:

let rec pairs l =
    match l with
    | [] | [_] -> []
    | h :: t -> 
        [for x in t do
            yield h,x
         yield! pairs t]
let test = [1;2;3;4;5;6] 
printfn "%A" (pairs test)

Answer 3

Вы, кажется, слишком усложняете вещи.Зачем даже использовать seq, если вы хотите список?Как насчет

let rec pairs lst =
    match lst with
    | [] -> []
    | h::t -> List.map (fun elem -> (h, elem)) t @ pairs t


let _ = 
    let test = [1;2;3;4;5;6]
    printfn "%A" (pairs test)