F Sharp Liste der Tupel in Liste der zugeordneten Tupel konvertieren

Question

Deklarieren Sie eine Funktion, die eine Liste von Paaren in eine Relation umwandelt.

type Relation<'a,'b> = ('a * 'b list) list 

Grundsätzlich wenden diese:

[(2,"c");(1,"a");(2,"b")] 

in diese:

[(2,["c";"b"]);(1,["a"])] 

in dieser Form:

toRel:(’a*’b) list -> Rel<’a,’b> 

Irgendwelche Ideen? Dies sind keine Hausaufgaben, nur Selbststudium und dieser hat mich ein wenig ratlos, wenn man bedenkt, dass die Form keine Akkumulation zulässt.

Answer 1

[(2,"c");(1,"a");(2,"b")] 
|> List.groupBy fst 
|> List.map (fun (x,y)->x,List.map snd y) 

Ergebnis:

[(2, ["c"; "b"]); (1, ["a"])] 

Typ-Inferenz ist praktisch für die Torel Bit:

let toRel xs = 
    xs 
    |> List.groupBy fst 
    |> List.map (fun (x,y)->x,List.map snd y) 

Verbrauch:

toRel [(2,"c");(1,"a");(2,"b")] 

Answer 2

Sie können verschiedene integrierte Funktionen nutzen und Transformation, um das Verhalten wieder aufzubauen, aber es ist auch gut, Grundwissen über Rekursion zu haben, um spezielle Funktionen von Grund auf neu zu erstellen.

Es ist auch eine gute Idee, dies mit Rekursion zu tun, um ein Problem in kleinere Probleme aufzuteilen, um zu lernen, wie man ein größeres Problem löst.

Wenn Sie in einer rekursiven Art und Weise denken, was Sie brauchen, ist todo:

1. Sie entfernen den Kopf der Liste ein Element zu erhalten.
2. Dann erstellen Sie Ihr Tupel mit dem Schlüssel und allen Werten des angegebenen Schlüssels
3. Sie entfernen alle Elemente mit dem aktuellen Schlüssel, den Sie verarbeitet und auf dieser Liste wiederholt.
4. Wenn Sie eine leere Eingabeliste haben, ist Ihre Ausgabe ebenfalls leer.

So beginnen Sie mit:

let rec group list = 
    if List.isEmpty list then [] 
    else 
     ??? 

Sie das erste Element einer Liste mit List.head entfernen. Aber wir wollen auch das Tupel in seine zwei Komponenten extrahieren. Sie erreichen dies mit

let k,v = List.head list 

Was wollen wir ein neues Tupel erstellen, die den gleichen Schlüssel, aber alle Werte der Eingabeliste. Wir haben diese Funktion noch nicht, aber wir nehmen an, dass wir eine Funktion valuesOf haben, dass wir einen Schlüssel und eine Liste übergeben können, und es gibt uns nur alle Werte des definierten Schlüssels zurück.

(k, (valuesOf k list)) 

In der ersten Iteration der Eingangsliste, die Sie von uns definierten 2 als k haben würde, und wir gehen davon aus valuesOf 2 list kehrt ["b";"c"]. Der obige Code würde (2, ["b";"c"]) als Wert zurückgeben. Jetzt der rekursive Aufruf. Wir nehmen wieder an, wir haben eine Funktion removeKey, die wir einen Schlüssel und eine Liste übergeben können, und es gibt eine neue Liste mit allen Elementen des angegebenen Schlüssels entfernt.

(removeKey k list) 

Als Beispiel

removeKey 2 [(1,"a");(2,"a");(2,"b");(3,"a")] 

sollte

[(1,"a");(3,"a")] 

Diese neue Liste zurück, dass removeKey kehrt diejenige, die Sie auf erneut auftritt müssen, ist: nur

(group (removeKey k list)) 

Sie muss Bot setzen h Stücke zusammen. Was Sie zurückgeben wollen, ist Ihr neues Tupel mit dem rekursiven Ergebnis.

(k, (valuesOf k list)) :: (group (removeKey k list)) 

und als eine Funktion.

let rec group list = 
    if List.isEmpty list then [] 
    else 
     let k,v = List.head list 
     (k, (valuesOf k list)) :: group (removeKey k list) 

Wir sind noch nicht fertig, wir müssen noch valuesOf und removeKey erstellen.

let rec valuesOf key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then v :: (valuesOf key list) 
     else (valuesOf key list) 

valuesOf verwendet Pattern Matching, die Liste dekonstruieren, statt List.head oder List.tail verwenden. Wir prüfen nur, ob das Element den angegebenen Schlüssel hat. Wenn dies der Fall ist, geben wir den aktuellen Wert zurück, der mit der verbleibenden Liste verkettet ist. Andernfalls geben wir nur das Ergebnis des rekursiven Aufrufs zurück und lassen den aktuellen Wert fallen.

removeKey ist ähnlich. Wir prüfen, ob der Schlüssel eines Tupels übereinstimmt, wenn ja, löschen wir das ganze Element und geben nur den rekursiven Aufruf zurück, andernfalls geben wir das aktuelle Element mit dem rekursiven Aufruf zurück.

let rec removeKey key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then (removeKey key list) 
     else x :: (removeKey key list) 

und jetzt sind wir fertig. Alles auf einmal

let rec valuesOf key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then v :: (valuesOf key list) 
     else (valuesOf key list) 

let rec removeKey key list = 
    match list with 
    | []  -> [] 
    | x::list -> 
     let k,v = x 
     if k = key 
     then (removeKey key list) 
     else x :: (removeKey key list) 

let rec group list = 
    if List.isEmpty list then [] 
    else 
     let k,v = List.head list 
     (k, (valuesOf k list)) :: group (removeKey k list) 

group [(2,"c");(1,"a");(2,"b");(2,"d");(3,"a");(1,"b")] 
// returns: [(2, ["c"; "b"; "d"]); (1, ["a"; "b"]); (3, ["a"])] 

Die obigen Funktionen sind nicht tail-rekursiv. Aber Sie können valuesOf und removeKey einfach mit List.fold oder List.foldBack umschreiben. Hier verwende ich List.fold, da ich davon ausgehe, dass es egal ist, ob sich die Reihenfolge der Elemente ändert.

let valuesOf key list = 
    List.fold (fun acc (k,v) -> 
     if k = key 
     then v :: acc 
     else acc 
    ) [] list 

let removeKey key list = 
    List.fold (fun acc (k,v) -> 
     if k = key 
     then acc 
     else (k,v) :: acc 
    ) [] list 

group kann nicht einfach neu geschrieben mit List.fold oder List.foldBack weil wir Zugriff auf die gesamte Liste benötigen. Aber es ist immer noch nicht schwer, Tail-Rekursion zu erreichen.

let group list = 
    let rec loop result list = 
     if List.isEmpty list then result 
     else 
      let k,v = List.head list 
      loop 
       ((k, (valuesOf k list)) :: result) 
       (removeKey k list) 
    loop [] list 

Wenn Sie nicht erwarten, Listen mit Tausenden oder mehr Schlüssel, Wert-Paare haben dann auch Sie die nicht tail-rekursive Funktionen halten.

Auch wenn es sich gut anfühlt, kleineren Code mit bereits bereitgestellten Funktionen wie List.groupBy und List.map zu erstellen, sollten Sie in der Lage sein, solche rekursiven Funktionen selbst zu erstellen. Warum?

Eine unveränderbare verkettete Liste ist eine rekursiv definierte Datenstruktur und das Arbeiten mit rekursiven Funktionen ist nur natürlich. Wenn Sie nicht wissen, wie Sie solche Funktionen selbst erstellen, stolpern Sie in dem Moment, in dem Sie eigene rekursive Datenstrukturen erstellen, denn dann haben Sie null vordefinierte Funktionen wie groupBy und map, die Sie bereits verwenden können. Sie müssen diese Funktionen selbst erstellen.

Der Versuch, die im Modul List definierte Funktion oder Dinge, die Sie hier beschrieben haben, wieder aufzubauen, ist eigentlich eine gute Art des Trainings, das Sie selbst tun sollten.