MonadFix in strict language

问题:

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?

回答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.