Does using a free monad in F# imply a higher startup time and limited instructions?

Question

I am reading this excellent article by Mark Seemann.

In it, he gives a simple demonstration of using the free monad to model interactions using pure functions.

I understand it enough to be able to write such a program, and I can appreciate the virtues of such an approach. There is one bit of code though, that has me wondering about the implications.

let rec bind f = function
    | Free instruction -> instruction |> mapI (bind f) |> Free
    | Pure x -> f x

The function is recursive.

1. Given that this is not tail recursive, does that mean that the number of instructions I include is limited by stack space, because every time I add an instruction, it has to unwrap the whole thing to add it?
2. Similarly to the above, does this imply a higher startup time because each new instruction has to go further down to be added? It might be negligible, but that is not the point of the question; I am trying to understand the theory, not the practicality.
3. If the answer to the above questions is 'Yes', would an alternative implementation along the lines of (make a list of instructions in the order you want them, then process the list in reverse order such that each instruction gets added to the top of your program, rather than deep down in the bottom) be preferable?

I may (probably) have missed something fundamental here that means that the recursion never has to go very far, please let me know.

Answer 1

I think the answer to the first two questions is "it depends" - there is some overhead associated with free monads and you can certainly run into stack overflows, but you can always use an implementation that avoids this and if you're doing I/O, then the overhead probably is not too bad.

I think the much bigger issue with free monads is that they are just too complicated abstraction. They let you solve one problem (abstracting over how you run code with lots of iteractions), but at a cost that you are making code very complicated. Most of the time, I think you can just keep a "functional core" as a nice testable pure part and "imperative wrapper" around it that is simple enough that you do not need to test it and abstract over it.

Free monads are very universal way of modeling this and you could use a more concrete representation. For reading and writing, you could do:

type Instruction = 
  | WriteLine of string
  | ReadLine of (string -> Instruction list)

As you can see, this is not just a simple list - ReadLine is tricky, because it takes a function that, when called with the string from the console, produces more instructions (that may, or may not, depend on this string):

let program = 
  [ yield WriteLine "Enter your name:"
    yield ReadLine (fun name ->
      [ if name <> "" then
          yield WriteLine ("Hello " + name) ] ) ]

This says "Hello " but only when you enter non-empty name, so it shows how the instructions depend on the name you read. The code to run a program then looks like this:

let rec runProgram program = 
  match program with 
  | [] -> ()
  | WriteLine s :: rest ->
      Console.WriteLine s
      runProgram rest
  | ReadLine f :: rest ->
      let input = Console.ReadLine()
      runProgram (f input @ rest)    

The first two cases are nice and fully tail-recursive. The last case is tail-recursive in runProgram, but it is not tail recursive when calling f. This should be fine, because f only generates instructions and does not call runProgram. It also uses slow list append @, but you could fix that by using a better data structure (if it actually turned out to be a problem).

Free monads are basically an abstraction over this - but I personally think that they are going one step too far and if I really needed this, then something like the above - with concrete instructions - is better solution because it's simpler.