Listen mit gleichen Köpfen in einer 2D-Liste (OCaml) kombinieren

Question

Ich arbeite mit einer Liste von Listen in OCaml, und ich versuche, eine Funktion zu schreiben, die alle Listen kombiniert, die den gleichen Kopf teilen. Das ist, was ich bisher, und ich nutze die List.hd eingebauten Funktion, aber nicht überraschend, dass ich den Fehler „hd“ Fehler bekommen:

let rec combineSameHead list nlist = match list with 
| [] -> []@nlist 
| h::t -> if List.hd h = List.hd (List.hd t) 
    then combineSameHead t nlist@uniq(h@(List.hd t)) 
    else combineSameHead t nlist@h;; 

So zum Beispiel, wenn ich haben diese Liste:

[[Sentence; Quiet]; [Sentence; Grunt]; [Sentence; Shout]] 

ich möchte es in kombinieren:

[[Sentence; Quiet; Grunt; Shout]] 

Die Funktion uniq ich entfernt schrieb nur alle Duplikate innerhalb einer Liste. Bitte lassen Sie mich wissen, wie ich das machen würde. Danke im Voraus!

Answer 1

Zum einen vermeide ich generell Funktionen wie List.hd, da Pattern Maching in der Regel übersichtlicher und weniger fehleranfällig ist. In diesem Fall kann Ihre if durch geschützte Muster ersetzt werden (eine when Klausel nach dem Muster). Ich denke, was geschieht, um Ihren Fehler zu verursachen ist, dass Ihr Code fehlschlägt, wenn t[] ist; Geschützte Muster helfen dies zu vermeiden, indem sie die Fälle expliziter machen. So können Sie (x::xs)::(y::ys)::t when x = y als eine Klausel in Ihrem Ausdruck match tun, um zu überprüfen, dass die Köpfe der ersten beiden Elemente der Liste identisch sind. Es ist nicht ungewöhnlich in OCaml, mehrere aufeinanderfolgende Muster zu haben, die bis auf Wächter identisch sind.

Weitere Dinge: Sie brauchen nicht []@nlist - es ist das gleiche wie nur Schreiben nlist.

Es sieht auch aus wie Ihre nlist@h und ähnliche Ausdrücke versuchen, Listen zu verketten, bevor Sie sie an den rekursiven Aufruf übergeben; In OCaml bindet die Funktionsanwendung jedoch fester als jeder Operator, sodass das Ergebnis des rekursiven Aufrufs tatsächlich an h angehängt wird.

Ich habe nicht, off-hand, eine korrekte Version der Funktion. Aber ich würde damit anfangen, es mit bewachten Mustern zu schreiben, und dann sehen, wie weit es dich bringt, es auszuarbeiten.

Answer 2

Verwenden Sie eine Map oder eine Hash-Tabelle, um die Köpfe und die für jeden Kopf gefundenen Elemente zu verfolgen. Die nlist Hilfs Liste ist nicht sehr hilfreich, wenn Listen mit den gleichen Köpfen nicht benachbart sind, wie in diesem Beispiel:

# combineSameHead [["A"; "a0"; "a1"]; ["B"; "b0"]; ["A"; "a2"]] 
- : list (list string) = [["A"; "a0"; "a1"; "a2"]; ["B"; "b0"]] 

Answer 3

Ihr bestimmungsgemäßen Betrieb eine einfache rekursive Beschreibung hat: rekursiv den Schwanz der Liste verarbeiten, dann Führen Sie eine "insert" -Operation mit dem head durch, der nach einer Liste sucht, die mit dem gleichen head beginnt und, falls vorhanden, fügt alle Elemente außer head ein und fügt sie sonst am Ende an. Sie können das Ergebnis dann umkehren, um die gewünschte Liste zu erhalten.

In OCaml, würde dieser Algorithmus wie folgt aussehen:

let process list = 
    let rec insert (head,tail) = function 
    | [] -> head :: tail 
    | h :: t -> 
     match h with 
     | hh :: tt when hh = head -> (hh :: (tail @ t)) :: t 
     | _ -> h :: insert (head,tail) t 
    in 
    let rec aux = function 
    | [] -> [] 
    | [] :: t -> aux t 
    | (head :: tail) :: t -> insert (head,tail) (aux t) 
    in 
    List.rev (aux list) 

Answer 4

ich wahrscheinlich etwas entlang der Linien von getan hätte, was vorgeschlagen Antonakos. Es würde die O (n) -Kosten der Suche in einer Liste vollständig vermeiden. Sie können auch feststellen, dass die Verwendung einer StringSet.t StringMap.t einfacher für die weitere Verarbeitung. Natürlich ist die Lesbarkeit von größter Bedeutung, und ich halte das immer noch unter diesen Kriterien.

module OrderedString = 
    struct 
     type t = string 
     let compare = Pervasives.compare 
    end 

module StringMap = Map.Make (OrderedString) 
module StringSet = Set.Make (OrderedString) 

let merge_same_heads lsts = 
    let add_single map = function 
     | hd::tl when StringMap.mem hd map -> 
      let set = StringMap.find hd map in 
      let set = List.fold_right StringSet.add tl set in 
      StringMap.add hd set map 
     | hd::tl -> 
      let set = List.fold_right StringSet.add tl StringSet.empty in 
      StringMap.add hd set map 
     | []  -> 
      map 
    in 
    let map = List.fold_left add_single StringMap.empty lsts in 
    StringMap.fold (fun k v acc-> (k::(StringSet.elements v))::acc) map [] 

Answer 5

Sie können viel tun, nur die Standard-Bibliothek mit:

(* compares the head of a list to a supplied value. Used to partition a lists of lists *) 
let partPred x = function h::_ -> h = x 
    | _ -> false 

let rec combineHeads = function [] -> [] 
    | []::t -> combineHeads t (* skip empty lists *) 
    | (hh::_ as h)::t -> let r, l = List.partition (partPred hh) t in (* split into lists with the same head as the first, and lists with different heads *) 
    (List.fold_left (fun x y -> x @ (List.tl y)) h r)::(combineHeads l) (* combine all the lists with the same head, then recurse on the remaining lists *) 

combineHeads [[1;2;3];[1;4;5;];[2;3;4];[1];[1;5;7];[2;5];[3;4;6]];; 
- : int list list = [[1; 2; 3; 4; 5; 5; 7]; [2; 3; 4; 5]; [3; 4; 6]] 

Dies wird nicht schnell sein (Partition, fold_left und concat sind alle O (n)) jedoch.