Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

F# Computation Expressions: How to use `for` to return a `seq`?

I'm writing a computation expression that is essentially implementing a State monad and I'm trying to use for expression.

I can use the boilerplate function forLoop or even MBuilder.For(), and they all return a nice M<seq<'U>, _> which can be processed by further let! expression. But when I'm trying to do the same with for expression, it fails to compile telling me that the expression inside for must return unit.

I'm sorry for a large code block that I can't make smaller.

type M<'T, 'E> = 'T * 'E                 // Monadic type is a simple tuple
type MFunc<'T, 'U, 'E> = 'T -> M<'U, 'E> // A function producing monadic value

// typical boilerplate functions
let bind (x: M<'T, 'E>) (f: MFunc<'T, 'U, 'E>) : M<'U, 'E> =
    let a, s = x
    let b, s1 = f a
    b, s1 + s
let combine (e1: M<'T, 'E>) (e2: M<'U, 'E>) : M<'U, 'E> = bind e1 (fun _ -> e2)
let delay f = (fun () -> f())()

// These two are explained below
let combineList (e1: M<'T, 'E>) (e2: M<'T seq, 'E>) : M<'T seq, 'E> =
    bind
        e1
        (fun x1 ->
            let e2body, e2state = e2
            seq{yield! e2body; yield x1}, e2state
        )
let forLoop (xs: seq<'T>) (f: MFunc<'T, 'U, 'E>) : M<seq<'U>, 'E> =
    Seq.fold
        (fun s x -> combineList (f x) s)
        (Seq.empty<'U>, 0)
        xs

// Builder class
type MBuilder() =
    member this.Bind (x: M<'T, 'E>, f: MFunc<'T, 'U, 'E>) : M<'U, 'E> = bind x f
    member this.Return(a) = a, 0
    member this.Combine(e1,e2) = combine e1 e2
    member this.Delay(f) = delay f
    member this.Zero() = (), 0
    member this.For (xs: seq<'T>, f: MFunc<'T, 'U, 'E> ) : M<seq<'U>, 'E> = forLoop xs f
let stateful = new MBuilder()

let mTest = stateful {
    // below is the typical use, just for example
    let! var1 = "q", 3
    let! var2 = true, 4
    // so far so good, the monad returns ("test", 7)
    return "test"
    }

Now, I'm trying to use the loops. The following three calls work as expected, incrementing the state as many times as there are elements in myList. They also return a beautiful string seq, obviously except the last call:

    let myList = ["one"; "two"; "three"] // define test data

    let! var3 = stateful.For(myList, (fun x -> x, 1))
    let! var4 = forLoop myList (fun x -> x, 1)

    // No return value, as expected
    for str in myList do
        let! _ = str, 1
        return ""

But the following does not compile: error FS0001: This expression was expected to have type M<'a,int> but here has type unit

    let! var5 =
        for str in myList do
            let! _ = str, 1
            return ""

So my question is - What am I doing wrong?

I'm also a bit confused with two overloads of For described here and how to make use of both.

like image 766
bytebuster Avatar asked Jun 28 '12 20:06

bytebuster


1 Answers

The code that you're trying to write is not syntactically valid computation expression. The syntax does not allow computation expression constructs in the expression e in let! v = e.

If you want to use nested computation expression, you have to write:

let mtest = stateful {
  let! var5 = 
    stateful { for str in myList do 
                 let! _ = str, 1 
                 return "" }
  return "something here" }

This should answer your immediate question, but there is a number of things that I find quite confusing about your definitions:

  • The type of your For is confusing. It should be either seq<'T> -> ('T -> M<'R>) -> M<'R> (if your monad can combine multiple results) or seq<'T> -> ('T -> M<unit>) -> M<unit> (if your computation returns just a single value)

  • You're sometimes using seq<'T> inside M<_> in the result (in For), but sometimes your monad returns only a single value. You should use the same monadic type everywhere.

  • The For construct can be defined in terms of Zero and Combine. Unless you're doing something special, that is the best way to go. See the example in the F# specification.

If you want a more detailed document, take a look at this article, which describes various options.

like image 94
Tomas Petricek Avatar answered Nov 15 '22 10:11

Tomas Petricek