2016-07-15 76 views
9

Sto cercando di imparare un po 'di più sulle espressioni di calcolo di F # implementando uno dei miei. Tuttavia, ho riscontrato un ostacolo in relazione al metodo Bind. Ecco quello che ho finora:Implementare il binding in un'espressione di calcolo personalizzata

type public op<'a> = Op of ('a list -> 'a list) 

let inline (>>) (Op a) (Op b) = Op (a >> b) 

module Op = 
    let id = Op id 
    let bind (b : 'b -> op<'a>) (v : 'b) = b v 
    let call (Op f) = f 
    let push v = Op (fun t -> v :: t) 
    // .. snip .. 

type OpBuilder() = 
    member __.Bind (v, b) = Op.bind b v 
    member __.Yield (()) = Op.id 
    member __.Return (m) = Op.call m 

    [<CustomOperation("push")>] 
    member __.Push (m : op<'a>, v : 'a) = m >> Op.push v 
    // .. snip .. 

let op = new OpBuilder() 

Ora, la mia comprensione è che tutte le seguenti dovrebbe essere grosso modo equivalente:

// Use only the Op module methods 
let f1 = Op.call(Op.bind (fun x -> Op.push x) 1) 

// Use op builder with external closure 
let f2 = Op.call(let x = 2 in op { push x }) 

// Use op builder bind explicitly 
let f3 = op.Return(op.Bind(3, fun x -> op.Push(op.Yield(), x))) 

// Use op builder with let! binding 
let f4 = op { let! x = 4 in push x } 

I primi 3 sembrano funzionare bene, tuttavia, f4 dà questo errore:

This expression was expected to have type
  unit
but here has type
  int

ottengo lo stesso errore se uso let invece di let!. Tutto ciò che ho letto suggerisce che questo è il modo corretto di implementare Bind, ma a quanto pare mi manca qualcosa. Qualcuno può far notare cosa sto facendo male?

+1

Che cosa rappresenta questo flusso di lavoro? Ora posso dirti che i tipi di vincoli e di ritorno non sono all'altezza, almeno per quanto riguarda il legame e il ritorno monadici, ma non ho idea di cosa sto guardando. – scrwtp

+0

@scrwtp L'idea è di creare una sorta di DSL stack-oriented. per esempio. 'op {push 2; dup; aggiungi} [] '→' [4] '. –

+2

Quello che chiami 'bind' non è un binding, ma solo una funzione. Per renderlo un binding monadico, il secondo parametro dovrebbe essere 'op <'b>', non ''b'. –

risposta

6

Se si sta tentando di implementare qualcosa come un DSL stack-based, le espressioni di calcolo non sono molto adatte. Si può perfettamente rappresentare questo solo con una lista di operazioni:

type Op = 
    | Push of int 
    | Dup 
    | Add 

let sample = 
    [ Push 2 
    Dup 
    Add ] 

E non ho potuto resistere a scrivere un semplice valutatore troppo:

let rec eval stack ops = 
    match ops, stack with 
    | (Push n)::ops, stack -> eval (n::stack) ops 
    | Dup::ops, s::stack -> eval (s::s::stack) ops 
    | Add::ops, s1::s2::stack -> eval ((s1+s2)::stack) ops 
    | [], stack -> stack 
    | _ -> failwith "Wrong arguments" 

eval [] sample 

espressioni di calcolo sono utili se si vuole dare un significato speciale per costrutti di linguaggio ordinario come il binding variabile let!, altri costrutti come for e try o la restituzione di un valore come acquisito da yield o return. Sebbene tu possa implementare alcune delle monadi Haskell, quelle non sono così utili in F # - quindi è un po 'complicato trovare un esempio di giocattolo utile con cui giocare.

+0

Non sono sicuro di essere d'accordo: puoi usare un'espressione di calcolo per far rispettare il fatto che non imposti mai uno stack vuoto, ad esempio, purché tu sia disposto a tollerare alcuni tipi instabili. Puoi farlo senza usare le espressioni di computazione, componendo invece una sequenza di metodi, ma non puoi ottenerla con una lista di valori di DU. – kvb

+0

Questo è simile a qualcosa con cui ho iniziato, ma sono arrivato alla conclusione che era troppo limitante (ad esempio sarebbe difficile definire nuovi moduli). Inoltre, i costruttori di espressioni computazionali mi sembravano sempre una specie di stregoneria, quindi volevo cogliere l'occasione per demistificarli un po '. –

+0

@ p.s.w.g Sì, questo ha senso: scrivere un costruttore di computazione è divertente :) tutto quello che sto cercando di dire è che è più facile iniziare con qualcosa che si adatta più alle strutture tradizionali di tipo monade. –

5

Mentre una soluzione adeguata che consente di sviluppare la respirazione comporta l'utilizzo di una monade di stato a pieno titolo come discusso nei commenti, è comunque possibile ottenere un po 'di distanza dal proprio tipo di Op come definito. È necessario definire una sorta di generatore degenerato per esso - non è una monade, è essenzialmente un costruttore di "composizione di funzioni", ma è solo abbastanza espressivo per do!, quindi si ottiene una sintassi piacevole.

Quindi supponendo che si dispone di un tipo Op come questo:

type Op<'a> = 'a list -> 'a list 

Definite il vostro costruttore come questo - con un'unità di prendere posto di una "propria" valore scartare nella legatura e tornare - pensare a come il parte mancante da stato tipo monade:

type OpBuilder() = 
    member __.Bind (ma, f) = ma >> f() 
    member __.Return (_) = id 

let op = new OpBuilder() 

Poi le operazioni:

[<AutoOpen>] 
module Ops = 

    let push (x:'a) : Op<'a> = fun st -> x::st 

    let dup: Op<'a> = fun st -> 
     match st with 
     | h::t -> h::h::t 
     | [] -> [] 

    let add: Op<int> = fun st -> 
     match st with 
     | a::b::t -> (a+b)::t 
     | _ -> failwith "not enough operands" 

E pinna alleato:

let comp : Op<_> = 
    op { 
     do! push 2 
     do! dup 
     do! add 
    } 

comp [] 
+0

Grazie, dovrò provare questo un po 'di più quando torno di fronte al mio PC. Ho capito che un problema che avevo era che "Return" doveva essere "Esegui" nel mio builder (ecco perché avevo bisogno di 'call' in' f2'). –

Problemi correlati