Wie bekomme ich eine Unterliste von einer Liste in ocaml

Question

Ich bin in der Liste Dokumentation. Es scheint, dass die Bibliothek keine sublist-Funktion bereitstellt.

Ich versuche, Liste der Elemente von i zu j zu bekommen. Jetzt muss ich es schreiben, wie:

let rec sublist list i j = 
    if i > j then 
    [] 
    else 
    (List.nth list i) :: (sublist list (i+1) j) 

, die ganz präzise ist, aber ich bin in Frage, die Effizienz der List.nth, denn wenn es O (n), würde ich lieber zu schreiben, um es in einem weniger prägnant Weg.

Ich frage mich, warum nicht bieten sie List.sublist func, wenn List.nth nicht O (1) ist, weil es so ist eine ziemlich häufige Operation ..

Answer 1

let rec sublist b e l = 
    match l with 
    [] -> failwith "sublist" 
    | h :: t -> 
    let tail = if e=0 then [] else sublist (b-1) (e-1) t in 
    if b>0 then tail else h :: tail 
;; 

sublist 3 5 [1;2;3;4;5;6;7;8;9] ;; 
- : int list = [4; 5; 6] 

Die oben ist mehr oder weniger eine abgeholzten Version von newacct-Lösung. Die Lösung von newacct weist eine Zwischenliste zu (drop i list), die für den Compiler in Haskell optimiert werden kann, aber viel schwieriger in ML. Daher ist seine Version vollkommen in Ordnung für eine Haskell-Funktion und marginal suboptimal für eine ML-Funktion. Der Unterschied zwischen den beiden ist nur ein konstanter Faktor: beide sind O (e). zrr's Version ist O (Länge (l)) seit List.filteri weiß nicht, dass f erst nach einer Weile false zurückgibt, ruft es für alle Elemente in l auf.

Ich bin nicht sehr glücklich zu lassen b gehen negativ, aber die Version, wo es nicht ist komplizierter.

Eine Referenz unter den ganz wenigen für die Abholzung wenn Sie interessiert sind: http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html

Answer 2

Das ist ein bisschen schwieriger, als es sein sollte mit OCaml's Standard-Bibliothek --- die Standard-Bibliothek ist ein bisschen spärlich. Wenn Sie eine der erweiterten Standardbibliotheken verwenden, wird es einfacher. Mit Core könnten Sie zum Beispiel schreiben:

let sublist list low high = 
    List.filteri l ~f:(fun i _ -> i >= low && pos < high) 

Ich kann mir vorstellen, dass etwas Ähnliches mit Extlib/Batterien möglich ist.

Answer 3

Versuchen Sie zuerst die Funktionen take (erste n Elemente) und drop (alles außer den ersten n Elementen) zu schreiben (wie in Haskell). Dann sublist i j lst ist nur take (j-i) (drop i lst)

Answer 4

Während die Antwort von Pascal bereitgestellt besser ist die richtige Antwort ein schöner Kandidat für List.sublist implementiert ist, dass Sie wahrscheinlich eine Reihe von einer Liste verwenden . Die Array-Module implementieren die Array.sub-Funktion, die Sie möglicherweise verwenden.

Während in vielen Imperative Sprachen wie C++ oder Perl gibt es im wesentlichen keinen Unterschied zwischen Listen und Arrays, das ist nicht das gleiche in OCaml ist, wo:

• Listen sind besser geeignet für rekursive Behandlungen und sequenziellen Zugriff dh ist normalerweise ein besserer Kandidat als ein Array als Argument für eine rekursive Funktion, und Sie möchten normalerweise alle Elemente der Liste betrachten.

• Arrays eignen sich besser für den wahlfreien Zugriff, Strukturänderungen (z. B. Sortieren) oder für numerische Berechnungen.