Come implementare il ritardo nel builder di calcolo forse?

Question

Ecco quello che ho finora:

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 funziona bene per sostenere for loop, ma non vedo come ottenere cicli while supportati. Parte del problema è che la traduzione di loop while utilizza delay, che in questo caso non sono riuscito a capire. L'evidente implementazione qui sotto è probabilmente sbagliata, in quanto non ritarda il calcolo, ma lo esegue invece!

let delay f = f() 

Non avendo ritardo ostacola anche try...with e try...finally.

Answer 1

Ci sono due modi diversi di attuazione costruttori continuazione in F #. Uno è quello di rappresentare i calcoli ritardati utilizzando il tipo di monade (se supporta un modo di rappresentare i calcoli in ritardo, come Async<'T> o il tipo unit -> option<'T> come mostrato dalla CNM.

Tuttavia, è anche possibile utilizzare la flessibilità di F espressioni # di calcolo e l'uso . un diverso tipo come valore di ritorno di Delay allora avete bisogno di modificare il funzionamento Combine di conseguenza e anche implementare Run membro, ma tutto funziona abbastanza bene:

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() 

il trucco è che compilatore F # usa Delay quando si avere un calcolo che deve essere ritardato - t hat è: 1) per avvolgere l'intero computazione, 2) quando componi sequenzialmente calcoli, ad es.utilizzando if all'interno del calcolo e 3) per ritardare i corpi di while o for.

Nella definizione di cui sopra, l'organo Delay restituisce unit -> M<'a> anziché M<'a>, ma è perfettamente soddisfacente perché Combine e While prendono unit -> M<'a> come loro secondo argomento. Inoltre, aggiungendo Run che valuta la funzione, il risultato di maybe { .. } blocco (funzione ritardo) viene valutato, in quanto l'intero blocco viene passato 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 } 

Questo è un modo per definire builder calcolo per non- tipi ritardati che sono probabilmente più efficienti del tipo di wrapping all'interno di una funzione (come nella soluzione di kkm) e non richiedono la definizione di una versione speciale ritardata del tipo.

Si noti che questo problema non si verifica ad es. Haskell, perché è un linguaggio pigro, quindi non ha bisogno di ritardare i calcoli esplicitamente. Penso che la traduzione F # sia abbastanza elegante in quanto consente di gestire entrambi i tipi ritardati (utilizzando Delay che restituisce M<'a>) e tipi che rappresentano solo un risultato immediato (utilizzando Delay che restituisce una funzione & Run).

Answer 2

Secondo identità monadici, il vostro delay dovrebbe sempre essere equivalente a

let delay f = bind (return()) f 

Dal

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

il delay ha la firma di

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

'T essere di tipo legato a unit. Si noti che la funzione bind ha i suoi argomenti invertiti rispetto all'ordine consueto bind p rest. Questo è tecnicamente lo stesso, ma complica il codice di lettura.

Poiché si sta definendo il tipo monadico come type Maybe<'a> = option<'a>, non è necessario ritardare un calcolo, poiché il tipo non include alcun calcolo, solo un valore. Quindi la definizione di ritardo come let delay f = f() è teoricamente corretta. Ma non è adeguato per un ciclo while: il "corpo" del loop verrà calcolato prima della sua "condizione di test", molto prima che lo bind venga associato. Per evitare ciò, ridefinisci la tua monade con un ulteriore livello di ritardo: invece di avvolgere un valore, avvolgi un calcolo che prende un'unità e calcola il valore.

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 

noti che il calcolo avvolto non viene eseguito fino all'interno della funzione bind, i. e. non eseguire fino a quando gli argomenti a bind sono associati.

Con l'espressione di cui sopra, sia correttamente delay semplificato per

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