¿Cómo implementar el retraso en el creador de cómputos tal vez?

Question

Esto es lo que tengo hasta ahora:

type Maybe<'a> = option<'a> 

let succeed x = Some(x) 

let fail = None 

let bind rest p = 
    match p with 
     | None -> fail 
     | Some r -> rest r 

let rec whileLoop cond body = 
    if cond() then 
     match body() with 
     | Some() -> 
      whileLoop cond body 
     | None -> 
      fail 
    else 
     succeed() 

let forLoop (xs : 'T seq) f = 
    using (xs.GetEnumerator()) (fun it -> 
      whileLoop 
       (fun() -> it.MoveNext()) 
       (fun() -> it.Current |> f) 
     ) 

whileLoop funciona bien para apoyar for bucles, pero no veo cómo conseguir que los bucles while compatibles. Parte del problema es que la traducción de while loops usa delay, lo que no pude entender en este caso. La implementación obvia a continuación probablemente sea incorrecta, ya que no demora el cálculo, ¡sino que lo ejecuta en su lugar!

let delay f = f() 

No tener retraso también dificulta try...with y try...finally.

Answer 1

En realidad, hay dos formas diferentes de implementar los constructores de continuación en F #. Una de ellas es para representar cálculos retardada utilizando el tipo monádico (si es compatible con alguna forma de representar cálculos retardados, como Async<'T> o el tipo unit -> option<'T> como se muestra por kkm.

Sin embargo, también se puede utilizar la flexibilidad de F expresiones # computación y el uso . un tipo diferente como valor de retorno de Delay Luego hay que modificar el funcionamiento Combine en consecuencia y también poner en práctica Run miembro, pero todo funciona bastante bien:

type OptionBuilder() = 
    member x.Bind(v, f) = Option.bind f v 
    member x.Return(v) = Some v 
    member x.Zero() = Some() 
    member x.Combine(v, f:unit -> _) = Option.bind f v 
    member x.Delay(f : unit -> 'T) = f 
    member x.Run(f) = f() 
    member x.While(cond, f) = 
    if cond() then x.Bind(f(), fun _ -> x.While(cond, f)) 
    else x.Zero() 

let maybe = OptionBuilder() 

el truco es que F # compilador utiliza Delay cuando tener un cálculo que necesita ser retrasado - t hat is: 1) para envolver todo el cálculo, 2) cuando compila cálculos secuencialmente, p.usando if dentro del cálculo y 3) para retrasar cuerpos de while o for.

En la definición anterior, el miembro Delay devuelve unit -> M<'a> en lugar de M<'a>, pero eso es perfectamente bien porque Combine y While tomar unit -> M<'a> como su segundo argumento. Por otra parte, mediante la adición de Run que evalúa la función, el resultado de maybe { .. } bloque (una función retardada) se evalúa, porque todo el bloque se pasa a Run:

// As usual, the type of 'res' is 'Option<int>' 
let res = maybe { 
    // The whole body is passed to `Delay` and then to `Run` 
    let! a = Some 3 
    let b = ref 0 
    while !b < 10 do 
     let! n = Some() // This body will be delayed & passed to While 
     incr b 
    if a = 3 then printfn "got 3" 
    else printfn "got something else" 
    // Code following `if` is delayed and passed to Combine 
    return a } 

Esta es una manera de definir constructor cálculo para no tipos retrasados ​​que probablemente sean más eficientes que el tipo de envoltura dentro de una función (como en la solución de kkm) y no requiere definir una versión especial retardada del tipo.

Tenga en cuenta que este problema no ocurre, p. Haskell, porque es un lenguaje perezoso, por lo que no necesita retrasar los cálculos explícitamente. Creo que la traducción F # es bastante elegante ya que permite tratar con ambos tipos que están retrasados ​​(usando Delay que devuelve M<'a>) y tipos que representan solo un resultado inmediato (usando Delay que devuelve una función & Run).

Answer 2

De acuerdo con identidades monádicos, su delay siempre debe ser equivalente a

let delay f = bind (return()) f 

Desde

val bind : M<'T> -> ('T -> M<'R>) -> M<'R> 
val return : 'T -> M<'T> 

la delay tiene la firma de

val delay : (unit -> M<'R>) -> M<'R> 

'T ser de tipo fijo, a unit. Tenga en cuenta que su función bind tiene sus argumentos invertidos desde el orden habitual bind p rest. Esto es técnicamente lo mismo pero complica el código de lectura.

Dado que está definiendo el tipo monádico como type Maybe<'a> = option<'a>, no hay retraso en el cálculo, ya que el tipo no ajusta ningún cálculo, solo un valor. Entonces su definición de retraso como let delay f = f() es teóricamente correcta. Pero no es adecuado para un ciclo while: el "cuerpo" del ciclo se computará antes de su "condición de prueba", realmente antes de que el bind esté vinculado. Para evitar esto, redefinir su mónada con una capa adicional de retraso: en lugar de envolver un valor, ajusta un cálculo que toma una unidad y calcula el valor.

type Maybe<'a> = unit -> option<'a> 

let return x = fun() -> Some(x) 

let fail = fun() -> None 

let bind p rest = 
    match p() with 
    | None -> fail 
    | Some r -> rest r 

Tenga en cuenta que el cálculo envuelta no se ejecuta hasta dentro de la función bind, i. mi. no se ejecuta hasta después de que los argumentos a bind están vinculados.

Con la expresión anterior, se simplifica delay correctamente a

let delay f = fun() -> f()