MonadFix in strict language

f#, haskell, monadfix, monads, ocaml

Solution

The F# computation expression syntax (related to Haskell `do`) supports recursion:

let rec ones = seq {
  yield 1
  yield! ones }

This is supported because the computation builder has to support `Delay` operation in addition to other monadic (or MonadPlus) operations. The code is translated to something like:

let rec ones = 
  seq.Combine
    ( seq.Yield(1),
      seq.Delay(fun () -> seq.YieldFrom(ones)) )

The type of `Delay` is, in general, `(unit -> M<'T>) -> M<'T>` and the trick is that it wraps a computation with effects (or immediate recursive reference) into a delayed computation that is evaluated on demand.

If you want to learn more about how the mechanism works in F#, then the following two papers are relevant:

- Syntax Matters: Writing abstract computations in F#

- Initializing Mutually Referential Abstract Objects: The Value Recursion Challenge

The first one describes how the F# computation expression syntax is desugared (and how `Delay` is inserted - and in general, how F# combines delayed and eager computations with effects) and the second one describes how F# handles `let rec` declarations with values - like the `ones` value above.

Problem

I'm working on camlp4 extension for haskell-like do notation in Ocaml, and trying to figure out how GHC compiles recursive do-bindings (enabled with -XDoRec). I wonder if it possible for monadic fixpoint combinator to exist in strict language (like Ocaml/F#/SML/...)? If yes, how can it look like? Would it be very useful?

Original source