10

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?

John Rivers
  • 1,307
  • 10
  • 20

1 Answers1

14

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:

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.

Tomas Petricek
  • 240,744
  • 19
  • 378
  • 553
  • 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. – Ramon Snir Mar 21 '13 at 18:00
  • 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...) – lukstafi Mar 23 '13 at 14:24