3

How do you implement in OCaml the operator 

mfix : ('a -> 'a state_monad) -> 'a state_monad

for a state monad? (Since it relies heavily on laziness, I guess one has to use the Lazy module from the standard library).

More precisely:

assuming a signature with 

type 'a t
( >>= ) : 'a t -> ('a -> 'b t) -> 'b t

mfix is the least fixpoint of the equation: mfix f = mfix f >>= f

But if you define it simply as 

let rec mfix f = mfix f >>= f

you end up with looping recursion due to the strict semantics of OCaml as opposed to the lazy semantics of Haskell.

Take for instance 

type 'a t = 'a list 
let ( >>= ) m f = List.flatten (List.map f m)

then for example 

let _ = mfix (fun _ -> [])

leads to a stack overflow while I would like it to be [].

I guess there is a way to overcome this using the Lazy module of the standard library but I cannot find how.

Bob
  • 1,713
  • 10
  • 23
  • What have you tried? What problem have you encountered? Have you looked at the implementation of `mfix` for Haskell's `StateT`: `mfix f = StateT $ \s -> mfix $ \ ~(a, _) -> runStateT (f a) s`? – Cirdec Jul 24 '14 at 22:17
  • @Cirdec: Indeed I tried to convert this code into OCaml. But, because of the recursive definition of a, it always end up looping: OCaml is a strict language! I tried to introduce laziness using the Lazy module but it still loops. – Bob Jul 24 '14 at 22:24
  • 1
    could you please describe what exactly mfix does? It will help OCamlers who don't know Haskell, like myself. – Jackson Tale Jul 25 '14 at 10:47
  • @JacksonTale: I have added explanations as you required. – Bob Jul 25 '14 at 18:07
  • 1
    @Bob. Well values in a CBV language don't work like that. But I can tell you that `val mfixLazy : ('a Lazy.t -> 'a Lazy.t state_monad) -> 'a state_monad` and `val mfixThunk : ('a thunk -> 'a thunk state_monad) -> 'a state_monad` where `type 'a thunk = unit -> 'a` are both definable (at least if we're talking about the *lazy* state monad). You will probably need `val join : 'a thunk thunk -> 'a thunk` and `val fstThunk : ('a, 'b) thunk -> 'a thunk`. – Lambdageek Jul 25 '14 at 22:10
  • 1
    Related: [MonadFix in strict language](http://stackoverflow.com/q/15553526/1333025). – Petr Aug 03 '14 at 16:40

0 Answers0