Suchen Sie Elemente in der Liste

Question

Ich baute eine einfache Funktion, die mir sagt, wo ein bestimmtes Element tatsächlich in einer Liste ist. Die erste Position ist 0:

let rec foo79 = 
fun k l -> 
    match k, l with 
    | k, []   -> failwith "What you are lookig for is not here" 
    | k, (x::xs) -> if  x = k then 0 
         else 1 + foo79 k xs 

Es ist einfach und funktioniert (trotzdem ist jeder Vorschlag, es zu verbessern, willkommen!).

Was ich mit dieser Funktion nicht zu tun, ist es mir die von xPositionen zu machen sagen, in dem Fall, dass xmehr mal in der Liste auftritt. Meine Versuche sind bis jetzt noch nicht einmal in der Nähe einer Lösung. Ich poste es gerade, um Ihnen ein Beispiel für den Ansatz zu geben, den ich verfolge.

let rec foo79b = 
fun k l -> 
    match k, l with 
    | k, []   -> failwith "What you are lookig for is not here" 
    | k, (x::xs) -> if  x = k & (x::xs) then 1 + foo79b k xs 
         elif x = k & []  then 0 
         else 1 + foo79b k xs 

Answer 1

Ihre Funktion muß eine Liste von Positionen zurückkehren, so können Sie einen Speicher für die resultierende Liste verwenden. Zur gleichen Zeit können Sie eine weitere Hilfsparameter verwenden Sie den Index zu treten, anstatt an der Aufrufstelle zusammenzufassen mit:

let findAllPos elem lst = 
    let rec foo79 = 
     fun k l i acc -> 
      match k, l with 
      | k, []  -> acc 
      | k, (x::xs) -> if x = k then foo79 k xs (i+1) (i::acc) 
          else   foo79 k xs (i+1)  acc 
    foo79 elem lst 0 [] 

Auf diese Weise wird es einfacher und noch wichtiger macht Ihre Lösung tail recursive. Wenn Sie mir nicht glauben, versuchen Sie, Ihre erste Funktion wie diese foo79 400000 [0..400000] zu nennen, dann versuchen Sie die, die ich vorschlage findAllPos 400000 [0..400000].

Answer 2

let positions (x: 'a) (xs: 'a seq) : int seq = 
    xs 
    |> Seq.mapi (fun i y -> if y = x then Some i else None) 
    |> Seq.choose id 

// [0; 0; 2; 3; 4; 0; 6] |> positions 0;; 
// val it : seq<int> = seq [0; 1; 5] 

Funktioniert auch mit Sequenzen.

Dieser funktioniert nur mit Listen (nicht-Sequenzen) und könnte sehr langsam sein:

let positions' (x: 'a) (xs: 'a list) : int list = 
    [0..(Seq.length xs - 1)] 
    |> List.filter (fun i -> xs.[i] = x) 

// [0; 0; 2; 3; 4; 0; 6] |> positions' 0;; 
// val it : int list = [0; 1; 5]