Дедупликация списка кортежей, но сохранение коллизий в виде списка - PullRequest
Новая
       16

Дедупликация списка кортежей, но сохранение коллизий в виде списка

0 голосов
/ 24 сентября 2018

Я новичок в F # и функциональных языках в целом.Мне трудно придумать рекурсивный способ дедупликации списка кортежей следующим образом: 

 [("Apple", "500");
  ("Orange", "123");
  ("Pineapple", "300");
  ("Apple", "200");
  ("Apple", "100");
  ("Orange", "234");
  ("Cucumber", "900");]

  --becomes-->

  [("Apple", ["500", "200", "100"]);
  ("Orange", ["123", "234"]);
  ("Pineapple", ["300"]);
  ("Cucumber", ["900"]);]

В основном я хочу что-то вроде карты в список.Объяснения приветствуются, так как мне все еще трудно читать функциональный код.

Ответы [ 3 ]

0 голосов
/ 24 сентября 2018

Если вы не хотите использовать функцию Seq.groupBy, предназначенную для этой цели, рекурсивным способом группировки будет неизменная структура данных для хранения группировок, например Map <<em>, >.Он будет производить элементы в отсортированном порядке при окончательном перечислении.Если исходный порядок должен быть сохранен, то изменяемая структура данных, например, Словарь <<em>, >, может считаться достаточно функциональной, если она остается локальной для функции. 

let groupByFst input =
    let d = System.Collections.Generic.Dictionary<_,_>()
    let rec aux = function
    | [] -> [ for KeyValue(k, vs) in d -> k, List.rev vs ]
    | (k, v)::tail ->
        match d.TryGetValue k with
        | true, vs -> d.[k] <- v::vs
        | _ -> d.Add(k, [v])
        aux tail
    aux input
// val groupByFst : input:('a * 'b) list -> ('a * 'b list) list when 'a : equality

[ "Apple", "500"
  "Orange", "123"
  "Pineapple", "300"
  "Apple", "200"
  "Apple", "100"
  "Orange", "234"
  "Cucumber", "900"]
|> groupByFst
// val it : (string * string list) list =
//   [("Apple", ["500"; "200"; "100"]); ("Orange", ["123"; "234"]);
//    ("Pineapple", ["300"]); ("Cucumber", ["900"])]
0 голосов
/ 25 сентября 2018

Или вы можете использовать List.fold для достижения вашей цели: 

let input = 
    [
        ("Apple", "500");
        ("Orange", "123");
        ("Pineapple", "300");
        ("Apple", "200");
        ("Apple", "100");
        ("Orange", "234");
        ("Cucumber", "900");
    ]

let output =
    List.fold (fun (acc : Map<string,string list>) (k,v) ->
        match Map.tryFind k acc with
        | Some x -> Map.add k (v :: x) acc
        | None -> Map.add k [v] acc
    ) Map.empty input
    // If you want a list instead of a map in the end, uncomment the next line.
    // |> Map.toList

, что дает:

val output: Map = map [("Apple", ["100"; "200"; "500"]);(«Огурец», [«900»]);(«Апельсин», [«234»; «123»]);("Ананас", ["300"])]

Хотя это и не так, как в версии groupBy, fold является вашим швейцарским армейским ножом во многих случаях и его стоит использоватьto.

И - в то время как есть хорошие готовые функции, такие как fold, поставляемые бесплатно с F #, если вы хотите рекурсивное определение, вы можете написать свой собственный сгиб в качестве учебного упражнения.Это может выглядеть так и должно работать с той же лямбдой, которую я использовал выше. 

let rec myFold folder acc values =
    match values with
    | [] -> acc
    | (x::xs) -> myFold folder (folder acc x) xs
0 голосов
/ 24 сентября 2018

Группировка может быть выполнена с помощью Seq.groupBy.

Запуск Seq.groupBy fst input Выход: 

seq
  [("Apple", seq [("Apple", "500"); ("Apple", "200"); ("Apple", "100")]);
   ("Orange", seq [("Orange", "123"); ("Orange", "234")]);
   ("Pineapple", seq [("Pineapple", "300")]);
   ("Cucumber", seq [("Cucumber", "900")])]

Это близко, но не совсем то, что вы хотитепотому что вторые элементы полученного кортежа содержат полный входной объект, тогда как ваш пример показывает, что вы хотите извлечь второй элемент из списка.Вы можете получить второй элемент из кортежа, используя snd, и, поскольку у вас есть последовательность кортежей, из которой вы хотите извлечь второй элемент, вы можете использовать Seq.map: 

let grouped = Seq.groupBy fst input
              |> Seq.map (fun (a, b) -> (a, Seq.map snd b))

printfn "%A" grouped

// yields...
seq
  [("Apple", seq ["500"; "200"; "100"]); ("Orange", seq ["123"; "234"]);
   ("Pineapple", seq ["300"]); ("Cucumber", seq ["900"])]
...