Dedicated Computation Expressions like State Builder

[natalie-o-perret]

I was looking for a dedicated computation expression for State<'s, 'a> and turns out there was nothing available, so I went to see @wallymathieu and he pointed me towards that implementation: https://gist.github.com/jwosty/5338fce8a6691bbd9f6f

I was wondering if there was a rationale for not having StateBuilder as part of FSharpPlus.

Description

I can't use State.get or State.put in a dedicated CE, I have to resort to use the monad CE.

Repro steps

Please provide the steps required to reproduce the problem

1. Step A

Can use that as an example:
https://github.com/fsprojects/FSharpPlus/blob/ca2b38c8a2ad7cc1a400d8e9bb864ce9548761f2/docsrc/content/type-state.fsx

open FSharpPlus
open FSharpPlus.Data

let rec playGame =
    function
    | []-> state {
            let! (_, score) = State.get
            return score
        }
    | x::xs-> state {
            let! (on, score) = State.get
            match x with
            | 'a' when on -> do! State.put (on, score + 1)
            | 'b' when on -> do! State.put (on, score - 1)
            | 'c'         -> do! State.put (not on, score)
            | _           -> do! State.put (on, score)
            return! playGame xs
        }

[<EntryPoint>]
let main _ =
    let startState = (false, 0)
    let moves = toList "abcaaacbbcabbab"
    State.eval (playGame moves) startState
    |> printfn "%A"
    0

2. Step B

Expected behavior

Could use a state builder, and code above should output 2.

Actual behavior

There is not state builder built-in implementation as part of FSharpPlus, hence the code above actually cannot compile

Known workarounds

Need to use the monad or its strict counterpart monad' to in order to benefit from State<'a, 's> in a computation expression:

open FSharpPlus
open FSharpPlus.Data

let rec playGame =
    function
    | []-> monad {
            let! (_, score) = State.get
            return score
        }
    | x::xs-> monad {
            let! (on, score) = State.get
            match x with
            | 'a' when on -> do! State.put (on, score + 1)
            | 'b' when on -> do! State.put (on, score - 1)
            | 'c'         -> do! State.put (not on, score)
            | _           -> do! State.put (on, score)
            return! playGame xs
        }

[<EntryPoint>]
let main _ =
    let startState = (false, 0)
    let moves = toList "abcaaacbbcabbab"
    State.eval (playGame moves) startState
    |> printfn "%A"
    0

or to import the aforementioned implementation in your own code, which seems far from being ideal:

open FSharpPlus
open FSharpPlus.Data

module State =
    let inline run state x = let (State(f)) = x in f state
    let get = State(fun s -> s, s)
    let put newState = State(fun _ -> (), newState)
    let map f s = State(fun (state: 's) ->
        let x, state = run state s
        f x, state)

/// The state monad passes around an explicit internal state that can be
/// updated along the way. It enables the appearance of mutability in a purely
/// functional context by hiding away the state when used with its proper operators
/// (in StateBuilder()). In other words, you implicitly pass around an implicit
/// state that gets transformed along its journey through pipelined code.
type StateBuilder() =
    member this.Zero () = State(fun s -> (), s)
    member this.Return x = State(fun s -> x, s)
    member inline this.ReturnFrom (x: State<'s, 'a>) = x
    member this.Bind (x, f) : State<'s, 'b> =
        State(fun state ->
            let (result: 'a), state = State.run state x
            State.run state (f result))
    member this.Combine (x1: State<'s, 'a>, x2: State<'s, 'b>) =
        State(fun state ->
            let _, state = State.run state x1
            State.run state x2)
    member this.Delay f : State<'s, 'a> = f ()
    member this.For (seq, (f: 'a -> State<'s, 'b>)) =
        seq
        |> Seq.map f
        |> Seq.reduceBack (fun x1 x2 -> this.Combine (x1, x2))
    member this.While (f, x) =
        if f () then this.Combine (x, this.While (f, x))
        else this.Zero ()

let state = StateBuilder()

let rec playGame =
    function
    | []-> state {
            let! (_, score) = State.get
            return score
        }
    | x::xs-> state {
            let! (on, score) = State.get
            match x with
            | 'a' when on -> do! State.put (on, score + 1)
            | 'b' when on -> do! State.put (on, score - 1)
            | 'c'         -> do! State.put (not on, score)
            | _           -> do! State.put (on, score)
            return! playGame xs
        }

[<EntryPoint>]
let main _ =
    let startState = (false, 0)
    let moves = toList "abcaaacbbcabbab"
    State.eval (playGame moves) startState
    |> printfn "%A"
    0

Related information

• Operating system: Windows 10
• Branch: master (should be renamed to main btw, no?)
• .NET Runtime, CoreCLR or Mono Version => CoreCLR
• Performance information, links to performance testing scripts: N/A

[wallymathieu]

Or you could use the available state-monad methods from F#+ to implement your CE?

[natalie-o-perret]

Or you could use the available state-monad methods from F#+ to implement your CE?

As another workaround, yes, but it does not change the fact that you still need to roll your own state builder implementation.

[adz]

I am not sure, but I don't think F#+ defines any computation expressions aside from the generic ones you mentioned.
This is quite interesting to me, since I haven't noticed before (I am a relatively new user, but have started using the monad CE).

When you said: I can't use State.get or State.put in a dedicated CE, I have to resort to use the monad CE. - I'm interested in why you are after a specific state builder?

I'm not sure 100% but I think the rationale is that monad CE (or it's variants) should be used, as they are built to work with any type, rather than a specific builder. They don't delegate to a specific builder (like a StateBuilder) but work by resolving specific static method implementations. So, I I'd say it's not a workaround to 'resort' to but the expected usage.

https://fsprojects.github.io/FSharpPlus/type-state.html
https://fsprojects.github.io/FSharpPlus//computation-expressions.html

[wallymathieu]

I guess the reasoning for wanting a specific state builder is to be more specific? Make it easier for developers to read what you mean? If F#+ should contain builders for monads, then it's not just state, but probably all of the base ones. In order to implement these builders we can use the existing generic monad definitions in order to ensure that they follow the same rules. Would it make sense to make a MonadBuilder<'T> base class in order to simplify the implementation of such?

[gusty]

While @adz is 100% right, I still fail to see a reason from the user perspective not to have some specialized CEs.

As F#+ developer there is a technical limitation from F# (no higher kinds) that prevents us to re-use the generic CE.

To illustrate, I would like to be able to write something like this:

let state = monad<State>
let reader = monad<Reader>

But that's not possible ( @wallymathieu not sure if you tried what you suggest, but AFAIK is not possible ).

So the only way to define a specialized builder is as @wallymathieu initially suggested:

open System
open System.Collections.Generic
open FSharpPlus
open FSharpPlus.Data
open FSharpPlus.Control


type StateBuilder() =
    member        __.ReturnFrom (expr) = expr                                        : State<'S,'T>
    member inline __.Return (x: 'T) = result x                                       : State<'S,'T>
    member inline __.Yield  (x: 'T) = result x                                       : State<'S,'T>
    member inline __.Bind (p: State<'S,'T>, rest: 'T->State<'S,'U>) = p >>= rest     : State<'S,'U>
    member inline __.MergeSources (t1: State<'S,'T>, t2: State<'S,'U>)               : State<'S,'T*'U> = Lift2.Invoke tuple2 t1 t2
    member inline __.BindReturn   (x : State<'S,'T>, f: 'T -> 'U)                    : State<'S,'U>    = Map.Invoke f x


type DelayedStateBuilder () =
    inherit StateBuilder ()
    member inline __.Delay (expr: _->State<'S,'T>) = Delay.Invoke expr : State<'S,'T>
    member        __.Run f = f

type MonadFxStateBuilder () =
    inherit DelayedStateBuilder ()

    member inline __.Zero () = result ()                                    : State<'S,unit>

    member inline __.Combine (a: State<'S,unit>, b) = a >>= (fun () -> b) : State<'S,'T>
    
    member inline __.WhileImpl (guard, body: State<'S,unit>) : State<'S,unit> =
        let rec loop guard body =
            if guard () then body >>= (fun () -> loop guard body)
            else result ()
        loop guard body

    member inline this.While (guard, body: State<'S,unit>) : State<'S,unit> =
        // Check the type is lazy, otherwise display a warning.
        // We don't need to check. State is Lazy -> let __ ()  = TryWith.InvokeForWhile (Unchecked.defaultof<State<'S,unit>>) (fun (_: exn) -> Unchecked.defaultof<State<'S,unit>>) : State<'S,unit>
        this.WhileImpl (guard, body)

    member inline this.For (p: #seq<'T>, rest: 'T->State<'S,unit>) : State<'S,unit> =
        let mutable isReallyDelayed = true
        Delay.Invoke (fun () -> isReallyDelayed <- false; Return.Invoke () : State<'S,unit>) |> ignore
        Using.Invoke (p.GetEnumerator () :> IDisposable) (fun enum ->
            let enum = enum :?> IEnumerator<_>
            // We don't need to check. State is really delayed ->  if isReallyDelayed then 
            this.WhileImpl (enum.MoveNext, Delay.Invoke (fun () -> rest enum.Current))
            // else this.strict.While (enum.MoveNext, fun () -> rest enum.Current)
            )


let state = MonadFxStateBuilder ()

So, basically what we're doing here is copying the source code from Builder and replacing the concrete type names Builder with StateBuilder, and replacing the generic type

'``Monad<'T>``

with the more specific: State<'S,'T> so each time we find Monad< we replace it with State<'S,

Finally we remove code that makes no sense in this specific monad, knowing that State is not a monadplus and it's not strict.

As you can see this is just boiler-plate. We can define a macro that does all these substitutions (except the code removal). Or you can do it on your and I know some users of this library do this on their side, in order to get less generic code with the advantages it brings (be more specific in the intention and less pressure on/better type inference).

The key question here is. Should we include all this boilerplate in this library?

I can't find any reason other than "it's boilerplate" not to include it, although for monad transformers it would require further analysis (make the monad a bit less generic? or have a combinatory of all monad combinations?), I did play once with type alias so it's still boilerplate, but it requires only the first 3 lines to be changed, the builder code is exactly the same, still it needs to be repeated.

[wallymathieu]

I think you are right @gusty that MonadBuilder<'T> is not possible since the generic type parameters assumes that you have a instance contract.

[gusty]

in order to get less generic code with the advantages it brings (be more specific in the intention and less pressure on/better type inference).

Note that for the intention it would suffice to define an alias like

let state = monad

[natalie-o-perret]

in order to get less generic code with the advantages it brings (be more specific in the intention and less pressure on/better type inference).

Yea, this is exactly my point! 💯

Note that for the intention it would suffice to define an alias like

let state = monad

Except that an alias like above will not restrict the types of monad that one can use in the given CE.

[gusty]

Except that an alias like above will not restrict the types of monad that one can use in the given CE.

Of course, that's why I said "for the intention", not for the other part.

[natalie-o-perret]

Except that an alias like above will not restrict the types of monad that one can use in the given CE.

Of course, that's why I said "for the intention", not for the other part.

Well if you don't restrict to the actual type matching a particular CE, then I'm not too sure this is actually reflecting the intention. It rather sounds confusing and misleading imho.

[gusty]

@kerry-perret I agree, let's say its name would express the intention but not its type.

Another possible advantage of specialized CEs could be Fable 2.0 compatibility.

But in order to achieve that, we can't define it by specializing generic code, which Fable won't be able to resolve. We'll have to write the functions by hand for each one, which is even more error prone as here we can't use a macro.

[natalie-o-perret]

Tbf, I wasn't expecting to impl. this using a macro.

[gusty]

OK, let's create a concrete proposal.

Some questions to answer:

• Should we create them using a macro, or by specifying function by function?
• Are we going to specialize everything? What about monad transformers?
• Do these specialized CEs follow the same rules as its generic counterpart?
• All monads are either lazy or strict, but they could be Fx and Plus at the same time. Should we create 2 CE's for those ones?

[natalie-o-perret]

OK, let's create a concrete proposal.

Some questions to answer:

• Should we create them using a macro, or by specifying function by function?
• Are we going to specialize everything? What about monad transformers?
• Do these specialized CEs follow the same rules as its generic counterpart?
• All monads are either lazy or strict, but they could be Fx and Plus at the same time. Should we create 2 CE's for those ones?

Should we create them using a macro, or by specifying function by function?

Might require further investigations. Reason is because of Fable 2.0 compatibility (I'm not an expert, but I'm just suspecting that the F# lang. support is not exactly 100% the same), not sure the macro would just do, I'd say that extra work would avoid to bump into unexpected behaviors. Also, I don't know if majority of people who use Fable tend to use the latest versions (looking at Fable 3.0), which is something that could change the direction we might be hinting to. I guess the benefit of leveraging macro is that it would save us some work.

Are we going to specialize everything? What about monad transformers?

Same rationale as above, so yea imho.

Do these specialized CEs follow the same rules as its generic counterpart?

For the sake of consistency, I'd say they should require the return keyword to return value, I've seen some implicit return cases with monad and monad'. Other than that, yes they should, but there are things I probably ignore, if you don't mind elaborate about these rules, I'm all for it.

All monads are either lazy or strict, but they could be Fx and Plus at the same time. Should we create 2 CE's for those ones?

I'm not sure to get this right:

All monads are either lazy or strict
=> one for each, definitely makes it super-duper clear what the developer can expect from a given or particular CE.

---

I would like to point out that the issue was initially just about the State Builder, not sure this requires another more general or broader issue.

Please, feel free to correct me if I'm wrong (I'm pretty sure there are things I haven't got them right).

[gusty]

I know the issue you raised was about State only, but if we do something with State we should do the same with Reader and others, that's why I expanded the issue to other types.

Regarding macros, we can skip them for now, at least until Fable 3 is around with proper overload support.

Monad transformers: if we decide to specialize them, further questions arise. Should we just make them generic (instead of bi-generic) or should we specialize the whole combination?

I've seen some implicit return cases with monad and monad'

Which ones?

For fx and plus monads how do we name them? We can name option the fx one and option.plus the plus version, but not sure if that's the best naming.

[natalie-o-perret]

@gusty Following up the #397

I've seen some implicit return cases with monad and monad'

Which ones?

let asyncMonad: Async<int32> = monad { 42 }
let asyncStrictMonad: Async<int32> = monad' { 42 }

// You can't just type that, you need the return keyword
// the type 'int32' doesn't match the type 'unit'
// async { 42 }
let asyncVanilla: Async<int32> = async { return 42 }

[<EntryPoint>]
let main _ =
    asyncMonad |> Async.RunSynchronously |> printfn "%A"
    asyncStrictMonad |> Async.RunSynchronously |> printfn "%A"
    asyncVanilla |> Async.RunSynchronously |> printfn "%A"

Output:

42
42
42

Monad transformers: if we decide to specialize them, further questions arise. Should we just make them generic (instead of bi-generic) or should we specialize the whole combination?

Not sure about MTs, discarding them for the time being, for starters:

• Cont<'R,'T>
• Reader<'R,'T>
• Writer<'Monoid,'T>
• State<'S,'T * 'S>
• Option<'T>
• Free<'Functor<'T>,'T>
• Validation<'Error, 'T>

For fx and plus monads how do we name them? We can name option the fx one and option.plus the plus version, but not sure if that's the best naming.

Lgtm, might need others feedback