Определение повторных компонентов списка F #

Question

У меня есть функция, которая генерирует список формы: [(String1, exp1); (String2, exp2); ... и т. д.]

exp - это тип, который я определил ранее.

Теперь мне нужен способ определить, является ли такой список недопустимым. Список недействителен, если он имеет повторяющуюся строку, но с каждым из них выполняется другой exp. i.e:

[("y", exp1); ("y", exp2); ("x", exp3)] //Invalid, as "y" is repeated with different exps 

[("y", exp1); ("y", exp1); ("x", exp3)] //Valid, as "y" is repeated with the same exps 

Я искал подходящее решение для этого и попытался использовать сопоставление с образцом без везения. Есть ли простое решение для этого, что мне не хватает? Благодаря!

Answer 1

Простое решение заключается в использовании groupBy:

let hasNoRepeatedComponents xs = 
    xs   
    |> Seq.groupBy fst 
    |> Seq.map snd 
    |> Seq.forall (fun s -> Set.count (Set.ofSeq s) = 1) 

соответствие шаблону не поможет, если не считать, что повторяющиеся компоненты являются последовательными.

Answer 2

Вам нужна какая-то структура для хранения предметов, которые вы видели раньше, если хотите сопоставить шаблон. Карта полезна для этого, так как нам нужно выполнять поиск. Ниже приведен пример соответствия шаблону:

let isValid source = 
    let rec loop source (m : Map<_,_>) = 
    match source with 
    | [] -> (true, "") 
    | (s,e) :: xs -> 
     match m.TryFind s with 
     | Some v when v <> e -> (false, sprintf "Key %s is repeated with different expressions" s) 
     | Some v -> loop xs m 
     | _ -> loop xs (m.Add (s,e)) 
    loop source Map.empty 

Решение Pad очень элегантно. Однако это будет немного быстрее для среднего недопустимого случая, так как он останавливается при первом недействительном повторном элементе.

Answer 3

@ Ответ пульта является хорошей отправной точкой, но он не работал для меня, как требуется (а именно, последний образец работает неправильно).

Если я правильно понял проблему, непоследовательные дубликаты по-прежнему считаются дублирующими, поэтому они «аннулируют» список.

В принципе, после того, как groupBy вам нужно сравнить две длины:

• исходной длины последовательности элементов, связанных с «у», «х» и т.д.
• Длина последовательности, созданной из ВУ применение Seq.distinct

Вот код:

let isValid xs = 
    xs 
    |> Seq.groupBy fst 
    |> Seq.map snd // we no longer need the key 
    // compare two lengthes: original and filtered/distinct 
    |> Seq.forall (fun x -> (Seq.length x) = Seq.length(Seq.distinct x)) 

[("y", 5); ("y", 6); ("x", 7)] |> isValid |> printfn "%A" // true 
[("y", 5); ("y", 5); ("x", 7)] |> isValid |> printfn "%A" // false 
[("y", 5); ("y", 6); ("x", 7); ("y", 7); ("y", 6)] |> isValid |> printfn "%A" // false