f # Schnittpunkt der Listen

Question

Die Funktion mem akzeptiert eine Liste und ein var X als Parameter und überprüft, ob die Liste den Wert X enthält und gibt true zurück, wenn es wahr ist, und false, falls es vorhanden ist.

let rec intersection list1 list2 = match list1 with 
       | head :: tail -> match list2 with 
        | head :: tail -> if mem list2 list1.Head = true 
        then (*add the value to a list*) else intersection list1.Tail list2 
       | [] -> failwith "Second list is empty" 
     | [] -> failwith "First list is empty" 

Ich bin ganz neu in F # und das Problem, das ich jetzt habe ist, ich weiß nicht, wie und fügen Sie dann den Wert auf eine Liste in der (auf einer Listefügen Sie den Wert) zu konstruieren. Ich habe den Code noch nicht getestet, da ich diesen Schritt zuerst ausführen muss, um keine Fehler zu bekommen, also bin ich nicht 100% sicher, wie es funktioniert.

Ich versuche, 2 Listen zu schneiden, ich weiß, dass es Funktionen für diese "Set.Intersect list1 list2" gibt. Die Einrückung ist ein bisschen seltsam hier, da ich nicht zu lange Reihen haben wollte, aber Sie werden wahrscheinlich sowieso verstehen.

Answer 1

Der direkteste Weg, um Ihren Code zu beheben, ist etwas wie den folgenden Code zu schreiben.

In mem Funktion, Ich reparierte gerade die Vertiefung und ändern Sie es head und tail zu verwenden, die Sie von Muster erhalten passend, anstatt sie über list.Head und list.Tail Zugriff (da dadurch das ist mehr idiomatische und sicherer):

let rec mem list x = 
    match list with 
    | [] -> false 
    | head :: tail -> 
    if x = head then true else mem tail x 

in intersection ist der Trick head::rest zu verwenden, um eine resultierende Liste zu erstellen, wenn head ein Element, das in beiden Listen erscheint (und rest ist die Liste, die Sie durch die Anwendung Kreuzung rekursiv auf den Schwanz bekommen). Sie brauchen auch nicht auf list2 passen, weil mem feine leere Listen Griffe:

let rec intersection list1 list2 = 
    match list1 with 
    | head :: tail -> 
     let rest = intersection tail list2 
     if mem list2 head then head::rest 
     else rest 
    | [] -> [] 

Dies ist nicht sehr effizient (vorausgesetzt n ist die Länge der list1 und m ist die Länge der list2, können Sie brauchen bis zu m * n Schritte), aber das ist wahrscheinlich nicht der Punkt. Außerdem ist intersection nicht tail-rekursiv, so dass es auf großen Listen nicht funktioniert, aber das ist ein anderes - fortgeschritteneres - funktionelles Programmierthema.

Schließlich wird der Code auch Liste zurück, die ein einzelnes Element mehrfach enthalten kann - aber ich denke, das für Sie in Ordnung (zB intersection [1;1;1] [1][1;1;1] zurückgibt, aber wenn Sie die Argumente Flip werden Sie nur [1] bekommen)

Answer 2

Um dies zu tun, müssen Sie den Überblick über die Liste behalten, die aufgebaut wird. Der beste Weg, dies zu tun, ist eine Hilfsfunktion zu definieren, die Liste als Parameter gebaut und schließt sie in dem rekursiven Aufruf

let intersection list1 list2 = 
    let rec inner list1 list2 builtList = 
    match list1 with 
    | head :: tail -> 
     match list2 with 
     | head :: tail -> 
     if mem list2 list1.Head = true then 
      inner tail list2 (list1.Head :: builtList) 
     else 
      inner tail list2 builtList 
     | [] -> failwith "Second list is empty" 
    | [] -> failwith "First list is empty" 
    inner list1 list2 [] 

Ein weiterer Kommentar ist, dass auf einer leere Liste andernfalls schlechte Praxis. Nur die leere Liste als eine Liste behandeln ohne Elemente daher ist kein Schnitt möglich

let intersection list1 list2 = 
    let rec inner list1 list2 builtList = 
    match list1 with 
    | head :: tail -> 
     if mem list2 list1.Head = true then 
     inner tail list2 (list1.Head :: builtList) 
     else 
     inner tail list2 builtList 
    | [] -> builtList 

    inner list1 list2 [] 

Diese Werke Version aber eine Liste der Rückkehr, die die Elemente in umgekehrter Reihenfolge hat, dass sie erscheinen in list1 enden.Um dies zu beheben, dass wir einen Rückruf verwenden können, um die Liste in der richtigen Reihenfolge aufzubauen

let intersection list1 list2 = 
    let rec inner list1 list2 builder = 
    match list1 with 
    | head :: tail -> 
     if mem list2 list1.Head = true then 
     inner tail list2 (fun next -> list1.Head :: next) 
     else 
     inner tail list2 builder 
    | [] -> (builder []) 

    inner list1 list2 (fun x -> x) 

Answer 3

Ich mag die Set-Operatoren http://msdn.microsoft.com/en-us/library/ee353629.aspx verwenden können Sie verwenden Set.intersect (Set.ofList list1) (Set.ofList list2) |> Set.toList