CODEWITHSUNDEEP
f#monadsfree-monadrecursive-type
Abel
Abel

Reputation: 57159

Trying to get bind working for combination of State and Delayed monad

If the answer to this is "you are going about it all wrong", by all means let me know a more proper way. I had code which was structured like this:

type Res<'T> =
    | E of (DC -> 'T)
    | V of 'T

Now this type was primarily used directly, with a lot of inline code that did manual per-case binding, which is a lot of boilerplate I am trying to get rid of, so I figured I turn it into a computation expression. It wasn't too hard to get map, bind and apply right.

State was carried along through DC but this was cumbersome to get right, so I changed it to the following, which is a common signature I see in discussions with the state monad.

type Res<'T> =
    | E of (DC -> DC * 'T)
    | V of 'T

Then I decided to take it to the next level and introduce the Delayed monad (or Eventually or whatever its name is). So I changed my type as follows, making it recursive:

type Res<'T> =
    | E of (DC -> DC * Res<'T>)
    | V of 'T

I tried some variants of the following, but keep getting:

The resulting type would be infinite when unifying ''a' and 'Res<'a> -> Res<'b>'

(usually happens when I do not invoke the return, i.e. the Res.E <| below)

Or I can't seem to get my types right, the following (understandably) throws a type error, but I'm having a blind spot fixing it:

This expression was expected to have type 'Res<'a>' but here has type 'DC * Res<'a>'.

let rec bind k res =
    match res with
    | Res.V v -> k v      // not delayed, should it be?
    | Res.E e -> 
        Res.E <| fun dc -> bind k (e dc)   // here's my error, on 'e dc'
         //(fun dc -> dc, bind f (e dc))
bind k res

I understand that the signature should be ('a -> Res<'b>) -> Res<'a> -> XRes<'b>. The problem comes from getting the recursion right, at least in my head. I'm not even sure why I am feeding the result to Res.E, as in my understanding, the k continuation should already return this type anyway.

Also, I currently have the return as follows (following Steve Horsfield):

let result v = Res.V v

But also noticed in some posts (notably the hilarious Frankenfunctor) this:

let result v = Res.E <| fun dc -> dc, Res.V v

Maybe I am following a pattern I shouldn't have, but it seemed a good idea at the time, especially in trying to refactor zillions of boilerplate code and replace it with computation expressions, but perhaps I should stick to the direct evaluation, it fit in my head ;).

But I feel like I'm close... Any ideas?

Upvotes: 2

Views: 130

Answers (1)

Fyodor Soikin
Fyodor Soikin

Reputation: 80744

I'm not quite sure what the meaning of this monad would be, but
Ok, after thinking about it a bit and reading the question's header :- ), I do understand what it means, and I can see how to build bind for it.

Your mistake is that the function wrapped in Res.E should return a tuple, but you're having it return just Res<'b> by recursively calling bind. And to mirror that, you're passing the result of e to recursive bind call in place of Res<'b> parameter, while e actually returns a tuple.

To do this correctly, you need to destructure the result of e, then pass second part to recursive bind call, and pair its result with the first part:

let rec bind (k: 'a -> 'b Res) (res: 'a Res) : 'b Res =
  match res with
  | V a -> k a
  | E e -> 
      E <| fun dc -> 
        let dc', res' = e dc 
        dc', bind k res'

The terminal case, I don't believe should be also delayed. That is, I don't see a reason for it. As far as I understand, the interpretation of the V x case should be "a computation that doesn't change state and returns x", in which case making it delayed doesn't add anything but an extra lambda-expression.

Upvotes: 1

Related Questions