Free Monad in F# with generic output type

Question

I am trying to apply the free monad pattern as described in F# for fun and profit to implement data access (for Microsoft Azure Table Storage)

Example

Let's assume we have three database tables and three dao's Foo, Bar, Baz:

Foo          Bar          Baz

key | col    key | col    key | col
---------    ---------    ---------
foo |  1     bar |  2         |

I want to select Foo with key="foo" and Bar with key="bar" to insert a Baz with key="baz" and col=3

Select<Foo> ("foo", fun foo -> Done foo)
  >>= (fun foo -> Select<Bar> ("bar", fun bar -> Done bar)
    >>= (fun bar -> Insert<Baz> ((Baz ("baz", foo.col + bar.col), fun () -> Done ()))))

Within the interpreter function

• Select results in a function call that takes a key : string and returns an obj
• Insert results in a function call that takes an obj and returns unit

Problem

I defined two operations Select and Insert in addition to Done to terminate the computation:

type StoreOp<'T> =
  | Select of string * ('T -> StoreOp<'T>)
  | Insert of 'T * (unit -> StoreOp<'T>)
  | Done of 'T

In order to chain StoreOp's I am trying to implement the correct bind function:

let rec bindOp (f : 'T1 -> StoreOp<'T2>) (op : StoreOp<'T1>) : StoreOp<'T2> =
  match op with
  | Select (k, next) ->
      Select (k, fun v -> bindOp f (next v))
  | Insert (v, next) ->
      Insert (v, fun () -> bindOp f (next ()))
  | Done t ->
      f t

  let (>>=) = bindOp

However, the f# compiler correctly warns me that:

The type variable 'T1 has been constrained to be type 'T2

For this implementation of bindOp the type is fixed throughout the computation, so instead of:

Foo > Bar > unit

all I can express is:

Foo > Foo > Foo

How should I modify the definition of StoreOp and/or bindOp to work with different types throughout the computation?

Answer 1

As Fyodor mentioned in the comments, the problem is with the type declaration. If you wanted to make it compile at the price of sacrificing type safety, you could use obj in two places - this at least shows where the problem is:

type StoreOp<'T> =
  | Select of string * (obj -> StoreOp<'T>)
  | Insert of obj * (unit -> StoreOp<'T>)
  | Done of 'T

I'm not entirely sure what the two operations are supposed to model - but I guess Select means you are reading something (with string key?) and Insert means that you are storing some value (and then continue with unit). So, here, the data you are storing/reading would be obj.

There are ways of making this type safe, but I think you'd get better answer if you explained what are you trying to achieve by using the monadic structure.

Without knowing more, I think using free monads will only make your code very messy and difficult to understand. F# is a functional-first language, which means that you can write data transformations in a nice functional style using immutable data types and use imperative programming to load your data and store your results. If you are working with table storage, why not just write the normal imperative code to read data from table storage, pass the results to a pure functional transformation and then store the results?