[Haskell-cafe] A question about mfix

[Ryan Ingram]

These aren't equivalent, at least with respect to sharing; consider
the sharing behavior with respect to the Identity monad:

> import Control.Monad.Fix
> import Control.Monad.Identity

> mfixWei f = mfix f >>= f

> v1, v2 :: [Int]
> v1 = runIdentity $ mfix $ \a -> return (0:a)
> v2 = runIdentity $ mfixWei $ \a -> return (0:a)

> cons = (:)

While v1 and v2 are both infinite lists of zeros, v1 takes constant memory:
v1 = cons 0 v1

but v2 takes memory linear in size to the last element evaluated:
v2 = cons 0 t0 where
  t0 = cons 0 t1
  t1 = cons 0 t2
  t2 = cons 0 t3
  t3 = ...

This is where the specification about "executes the action f only
once" comes from; your implementation expands to

mfix f
= mfix f >>= f
= (mfix f >>= f) >>= f
= ((mfix f >>= f) >>= f) >>= f
= ...

As you can see, f might get executed an arbitrary number of times
depending on "how lazy" >>= is.

Now, I don't know the answer if you "fix" (pardon the pun) your
definition of mfix to

> mfixLazy f = let x = x >>= f in x

which gives the correct sharing results in the "runIdentity" case.

  -- ryan



On Tue, Jul 29, 2008 at 6:28 PM, Wei Hu <weihu at cs.virginia.edu> wrote:
> What's wrong about giving mfix the following general definition?
>
>
>>  mfix :: (a -> m a) -> m a
>>  mfix f = (mfix f) >>= f
>
>
> I know it diverges if (>>=) is strict on the first argument. My
> question is, is this definition correct for all lazy monads? The
> documentation (http://haskell.org/ghc/docs/latest/html/libraries/base/
> Control-Monad-Fix.html#v%3Amfix) says "mfix f executes the action f
> only once, with the eventual output fed back as the input.". So my
> definition looks like a valid one, doesn't it?
>
> I haven't fully wrapped my head around this monadic fixed-point thing
> yet. So, if you can give an example showing how my definition differs
> from a standard monad, that'll be great.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>