F # bauen eine Liste/Array von Werten + aufeinander folgenden Duplikate

Question

Ich muss die Daten so verpacken:

let data = [1; 2; 2; 3; 2; 2; 2; 4] 
let packed = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Wo jedes Element sagen, wie viel Zeit es vor dem nächsten bestehen. Es muss jedoch mit nicht benachbarten Duplikationen arbeiten.

Ich kann dies mit klassischen Imperativ-Code arbeiten, aber frage mich, wie dies funktionell funktioniert.

Auch arbeiten Seq.countBy nicht, weil es

Konto alle Werte übernehmen übernimmt

Answer 1

Wenn Sie bereits eine Version zwingend notwendig haben, können Sie follow a set of small steps to refector to a recursive implementation.

Rekursion

Während ich weiß nicht, was Ihre Imperativ Version aussieht, hier eine rekursive Version:

let pack xs = 
    let rec imp acc = function 
    | [] -> acc 
    | h::t -> 
     match acc with 
     | [] -> imp [(h, 1)] t 
     | (i, count) :: ta -> 
      if h = i 
      then imp ((i, count + 1) :: ta) t 
      else imp ((h, 1) :: (i, count) :: ta) t 
    xs |> imp [] |> List.rev 

Diese Funktion den Typ 'a list -> ('a * int) list when 'a : equality hat. Es verwendet eine private 'Implementierungsfunktion' imp, um die Arbeit zu erledigen. Diese Funktion ist rekursiv und führt einen Akkumulator (acc) durch. Dieser Akkumulator ist die Ergebnisliste vom Typ ('a * int) list.

Wenn der Speicher-Liste leer ist, wird der Kopf der ursprünglichen Liste (h) sowie die Zählung 1 wird als Tupel als das einzige Element des aktualisierten Speichers erzeugt und die imp Funktion wird rekursiv aufgerufen, mit dieser aktualisierte Akku. Wenn der Akkumulator bereits mindestens ein Element enthält, wird das Element über die Mustererkennung extrahiert, und das Element in diesem Tupel (i) wird mit h verglichen. Wenn h = i, wird der Akkumulator aktualisiert; andernfalls wird ein neues Tupel auf acc geschrieben. In beiden Fällen wird jedoch imp rekursiv mit dem neuen Akkumulator aufgerufen.

Sie können es nennen mit einer Liste äquivalent zu Ihrem ursprünglichen Tupel wie folgt aus:

> pack [1; 2; 2; 3; 2; 2; 2; 4];; 
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Falten

Sobald Sie eine rekursive Version haben, haben Sie oft das Rezept für eine Version ein mit falten. In diesem Fall, da die obige pack Funktion den Akkumulator am Ende umkehren muss (unter Verwendung von List.rev), ist ein rechter Falz am besten geeignet.In F # ist dies mit der List.foldBack Funktion in integrierten getan:

let pack' xs = 
    let imp x = function 
     | (i, count) :: ta when i = x -> (i, count + 1) :: ta 
     | ta -> (x, 1) :: ta 
    List.foldBack imp xs [] 

In diesem Fall ging die Funktion List.foldBack ist ein bisschen zu komplex als eine anonyme Funktion zu übergeben, so wählte ich es als zu definieren, private innere Funktion. Es entspricht der rekursiven imp-Funktion, die von der obigen pack-Funktion verwendet wird, aber Sie werden bemerken, dass es sich nicht rekursiv aufrufen muss. Stattdessen muss nur der neue Wert für den Akkumulator zurückgegeben werden.

Das Ergebnis ist das gleiche:

> pack' [1; 2; 2; 3; 2; 2; 2; 4];; 
val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)] 

Answer 2

Meine Lösung der data Sammlung eine Liste ist. Wenn es als Tupel (wie in Ihrem Beispiel) beabsichtigt war, dann muss das Tupel in eine Liste umgewandelt werden (ein Beispiel, wie es zu tun ist, kann here gefunden werden).

let groupFunc list = 
    let rec groupFuncRec acc lst init count = 
     match lst with 
     | [] -> List.rev acc 
     | head::[] when head = init 
      -> groupFuncRec ((init, count)::acc) [] 0 0 
     | head::[] when head <> init 
      -> groupFuncRec ((head, 1)::acc) [] 0 0 
     | head::tail when head = init 
      -> groupFuncRec acc tail head (count+1) 
     | head::tail when head <> init 
      -> groupFuncRec ((init, count)::acc) tail head 1 
    let t = List.tail list 
    let h = List.head list 
    groupFuncRec [] t h 1 

Wenn ich die Funktion auf Ihrem Beispieldaten laufen bekomme ich das erwartete Ergebnis zurück:

list = [(1, 1); (2, 2); (3, 1); (4, 1)] 

Answer 3

Sie Seq.countBy erhalten können, indem einige Positionsinformationen in ihr Argument zu arbeiten. Natürlich müssen Sie dann auf Ihre ursprünglichen Daten zurückmelden.

[1; 2; 2; 3; 2; 2; 2; 4] 
|> Seq.scan (fun (s, i) x -> 
    match s with 
    | Some p when p = x -> Some x, i 
    | _ -> Some x, i + 1) (None, 0) 
|> Seq.countBy id 
|> Seq.choose (function 
| (Some t, _), n -> Some(t, n) 
| _ -> None) 
|> Seq.toList 
// val it : (int * int) list = [(1, 1); (2, 2); (3, 1); (2, 3); (4, 1)]