[Haskell-cafe] A question about mfix
Ryan Ingram
ryani.spam at gmail.com
Tue Jul 29 22:12:45 EDT 2008
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
>
More information about the Haskell-Cafe
mailing list