Ocaml: Lazy Lists

Question

Wie kann ich eine faule Liste erstellen, die eine Folge von Doppelnummern darstellt? Beispiel:

1 2 4 8 16 32 

Answer 1

Der große Blog enfranchised Geist hat einen großen Beitrag zu diesem Thema:

http://enfranchisedmind.com/blog/posts/ocaml-lazy-lists-an-introduction/

Sie auch aus http://batteries.forge.ocamlcore.org/doc.preview%3Abatteries-beta1/html/api/Lazy%5Flist.html

überprüfen, die die Standard-Bibliothek ist damit für den Umgang .

Diese Frage ist auch sehr ähnlich zu dieser Frage:

What OCaml libraries are there for lazy list handling?

Answer 2

Mit Streams:

let f x = Stream.from (fun n -> Some (x * int_of_float (2.0 ** float_of_int n))) 

oder

let f x = 
    let next = ref x in 
    Stream.from (fun _ -> let y = !next in next := 2 * y ; Some y) 

einen benutzerdefinierten lazy_list Typen verwenden:

type 'a lazy_list = 
    | Nil 
    | Cons of 'a * 'a lazy_list lazy_t 
let rec f x = lazy (Cons (x, f (2*x))) 

Answer 3

Wenn Sie es von Hand machen wollen, würde ich sagen Sie zur Haupt Möglichkeiten:

• Verwenden Sie eine benutzerdefinierte lazy_list Art, wie ephemient sagte (mit Ausnahme seiner Lösung ein bisschen gebrochen ist) :

  type 'a lazy_list = 
      | Nil 
      | Cons of 'a * 'a lazy_list 
  
  let head = function 
      | Nil -> failwith "Cannot extract head of empty list" 
      | Cons (h, _) -> h 
  
  let tail = function 
      | Nil -> failwith "Cannot extract tail of empty list" 
      | Cons (_, t) -> t 
  

• eine Art Thunk verwenden (wie die Sache verwendet lazy evaluation in einer Sprache zu implementieren, die nicht unterstützt wird). Sie definieren Ihre Liste als eine Funktion unit -> 'a, die sagt, wie man das nächste Element von dem aktuellen Element erhält (keine Notwendigkeit, Ströme dafür zu verwenden). Um zum Beispiel die Liste aller natürlichen Zahlen zu definieren, können Sie

  let make_lazy_list initial next = 
      let lazy_list current() = 
       let result = !current in 
       current := (next !current); result 
      in lazy_list (ref initial) 
  
  let naturals = make_lazy_list 0 (function i -> i + 1) 
  

  Das tun, wenn Sie

  print_int (naturals()); 
  print_int (naturals()); 
  print_int (naturals()) 
  

  tun, werden Sie die folgende Ausgabe:

  0 
  1 
  2 
  

Answer 4

Außerdem gibt es ein Faul List-Modul namens Cf_seq in meinem OCaml Network Application Environment Core Foundation. Tatsächlich habe ich eine ganze Reihe funktionaler Datenstrukturen geschrieben. Es ist alles unter einer 2-Klausel-BSD-Lizenz verfügbar. Genießen.

aktualisieren: Der Code wird umbenannt „Oni“ und jetzt ist es an BitBucket gehostet. Sie können auch das Paket GODI dafür verwenden.