MonadFix in strict language

Question

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?

Determine

Answer 1

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.

Catholicism

So, no - it isn't possible in a purely strict fashion. Since all functional languages have some concept of laziness (mostly using functions, closures and variables) - it is possible in "strict languages" via lazy constructs. – Cf

Often the laziness is already there but if your monad is behind an abstract type, OCaml will not let you exploit it -- This kind of expression is not allowed as right-hand side of 'let rec'. You need to go for spurious unit arguments in such cases (or perhaps "lazy" if you need memoization...) – Wooldridge