Внедрение привязки в пользовательском выражении Вычисление

Question

Я пытаюсь узнать немного больше о выражениях вычисления F #, реализовав один из моих собственных. Тем не менее, я ударил камень преткновения относительно метода Bind. Вот что у меня до сих пор:

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

Теперь я понимаю, что все следующие должны быть примерно эквивалентны:

// 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 } 

Первые 3, кажется, работает хорошо, однако, f4 дает эта ошибка:

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

я получаю ту же ошибку, если я использую let вместо let!. Все, что я читал, говорит о том, что это правильный способ реализовать Bind, но, видимо, я что-то упускаю. Может ли кто-нибудь указать, что я делаю неправильно?

Answer 1

Если вы пытаетесь реализовать что-то вроде DSL на основе стека, то вычисления выражения не очень хорошо подходят. Вы можете отлично представить это только со списком операций:

type Op = 
    | Push of int 
    | Dup 
    | Add 

let sample = 
    [ Push 2 
    Dup 
    Add ] 

И я не мог сопротивляться писать простой оценщик тоже:

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 

Расчетные выражения полезны, если вы хотите, чтобы дать какой-то особый смысл обычные языковые конструкции, такие как переменная привязка let!, другие конструкции, такие как for и try, или возврат значения, снятого yield или return. Хотя вы можете реализовать некоторые из монахов Haskell, это не все, что полезно в F #, поэтому немного сложно найти полезный пример игрушек для игры.

Answer 2

В то время как правильное решение, которое дает вам комнату для передышки, предполагает использование полноценной государственной монады, как описано в комментариях, вы все равно можете получить некоторый пробег из вашего типа Op, как определено. Для этого вам нужно определить своего рода вырожденный строитель - это не монада, это по сути «строитель функциональной композиции», но он достаточно экспрессивный для do!, поэтому вы получаете красивый синтаксис.

Так если у вас есть тип Оп, как это:

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

Вы определяете свой конструктор, как это - с единицей происходит о «правильном» развернутом значении в затруднительном и вернуться - думать об этом как часть отсутствует государственного типа монады:

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

let op = new OpBuilder() 

Тогда операции:

[<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" 

И плавник союзник:

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

comp []