How to implement MonadFix instance of an IO-like type in JS?

Question

I am completely lost in trying to translate the following Haskell code into Javascript:

instance MonadFix IO where
  mfix f = do
    var <- newEmptyMVar                       -- 1
    ans <- unsafeInterleaveIO $ takeMVar var  -- 2
    result <- f ans                           -- 3
    putMVar var result                        -- 4
    return result                             -- 5

Let’s walk through this line by line in terms of our little time travel analogy:

1. Create an empty mutable variable.
2. Predict the future value that will be contained in that mutable variable.
3. Call the function f with the predicted future value.
4. Store the result of f in the variable, thus fulfilling the prophecy as required by line 2.
5. Return that result.

What I have is a special Lazy type that handles (or rather defers) synchronous IO. However, I'd like to abstract from direct recursion with value recursion:

const record = (type, o) =>
  (o[Symbol.toStringTag] = type.name || type, o);

const Lazy = lazy => record(Lazy, {get lazy() {
  delete this.lazy
  return this.lazy = lazy();
}});

// Monad

const lazyChain = mx => fm =>
  Lazy(() => fm(mx.lazy).lazy);

const lazyChain_ = fm => mx =>
  Lazy(() => fm(mx.lazy).lazy);

const lazyOf = x => Lazy(() => x);

// mfix = chain_ => fm => chain_(fm) (mfix(chain_) (fm)) ???

// MAIN

const trace = x => (console.log(x), x);
const app_ = x => f => trace(f(x));

const readLine = s => Lazy(() => window.prompt(s));

const fac = x => x === 0 ? 1 : x * fac(x - 1),
  tri = x => x === 0 ? 0 : x + tri(x - 1);

const foo = lazyChain(readLine("enter true/false")) (s => {
  return lazyOf(s === "true"
    ? fac : tri);
});

const bar = x => lazyChain(foo) (y => lazyOf(app_(x) (y)));
const main = bar(5);

console.log("effect has not yet been unleashed..");
main.lazy;

How do I implement the Lazy instance of MonadFix in Javascript?

Answer 1

You have a representation of thunks with your Lazy construct, which happens to form a monad (where monadic application is just strict function application, as you’ve written), but you don’t have a representation of IO, so you’re essentially just using unsafePerformIO everywhere.

In your model, each I/O action can only be executed once, so I expect this will not work quite the way you expect unless you add a separate IO wrapper with something like a runIO function (or property, if you like) that does not share Lazy’s behaviour of overwriting itself with the memoised result, or perhaps if you add some way to explicitly duplicate a deferred action. Of course, mfix f only runs the effects of f once anyway—that is, it’s for using effects to produce a lazy/self-referential data structure—so this may be fine for your purposes.

Those caveats aside, it’s perfectly possible to express something resembling an instance of MonadFix for your thunk structure, but it’s just a lazy version of fix:

// cf. Haskell ‘fix f = let ans = f ans in ans’
function lazyFix(f) {
  var ans = Lazy(() => f(ans));
  return ans;
}

If you have side effects interleaved in these thunks, they’ll happen as you force them.

I think the MVar business in the original Haskell code is mainly just a convenient way to catch a subset of infinite loops, by ensuring that if the action tries to force the thunk before a value is written into it, then the runtime will be able to detect that the thread is “blocked indefinitely in an MVar operation” and raise an error.

And as a side note, you should be able to simplify your lazyChain definition to just fm(mx.lazy), since Lazy(() => fm(mx.lazy).lazy) forces the result and then immediately wraps it in a thunk again, which is both extra work and possibly too eager about your interleaved effects. Your version is effectively let fx = fm mx in mx `seq` fx `seq` fx, which can be simplified (by a `seq` a = a) to mx `seq` fm mx, which is then equivalent to fm $! mx, i.e., strict function application.