Ocaml - Lazy.force

Question

Ist meine Karte Funktion in:

type 'a stream = Cons of 'a * 'a stream Lazy.t 

let rec ones = Cons(1, lazy(ones));; 

let rec map (f:'a -> 'b) (s:'a stream) : 'b stream = 
    match s with 
    |Cons(h,t) -> Cons(f h, lazy (map f (Lazy.force t)));; 
;; 

Richtige? Würde Lazy.forcing es so schon machen?

Answer 1

Ja, es ist korrekt.

Beachten Sie jedoch, dass keine Berechnungen geteilt werden, wenn Sie sie auf eine reguläre/zyklische statt unendliche Datenstruktur anwenden (wie hier ones). Das Erzwingen der N ersten Elemente von map succ ones gilt noch immer succ N-mal. (Es gibt tatsächlich einige Forschungsarbeiten über Sprachen, die es ermöglichen würden, solche Formen von Regelmäßigkeit/Zyklen zu erkennen und eine strenge Zuordnung auf ihnen zu beenden, siehe beispielsweise das CoCaml Projekt.)

Answer 2

Es gibt etwas Magie im ocaml Lazy-Typ. Ich denke, es ist einfacher, Faulheit zu verstehen, wenn Sie es selbst implementieren, was einfach, aber nicht so syntaktisch bequem ist. Die Tricks sind

• Verzögerung Auswertung Schließungen
• Verwendung ref Zellen unter Verwendung von Berechnungen memoize

Hier ist es klar, wie und wann die memoization geschieht während Lazy'.force.

module Lazy' : sig 
    type 'a t 
    val delay: (unit -> 'a) -> 'a t 
    val force: 'a t -> 'a 
end = struct 
    type 'a susp = 
    | NotYet of (unit -> 'a) 
    | Done of 'a 

    type 'a t = 'a susp ref 

    let delay f = ref (NotYet f) 

    let force f = 
    match !f with 
    | Done x -> x 
    | NotYet f' -> 
     let a = f'() in 
     f := Done a; 
     a 
end 

Typ 'a stream = Nachteile von' a * 'ein Stream Lazy'.t ;;

lassen diejenigen = rec ones'() = Cons (1, Lazy'.delay ones ') in Einsen'() lassen ;;

Lassen Sie die Karte fs = match s mit | Nachteile (h, t) -> Nachteile (f h, Lazy'.delay (Spaß() -> Karte f (Lazy'.force t))) ;;