GHC: Ticket #1449: Bug in instance MonadFix []
http://ghc.haskell.org/trac/ghc/ticket/1449
<p>
(Thanks to Simon Marlow for pointing me to trac)
</p>
<p>
I was recently playing around with mfix on #haskell, after seeing the "fix
show" trick. I tried "mfix show" which ought to have done something similar
using Char instead of String. This turned up a bug for the list instance of
MonadFix and a half-bug for the Char instance for Show. (The latter is
slightly too strict for Char, not even producing the initial '. However I
guess this is unlikely to matter for anything other than this kind of
trick.)
</p>
<p>
The definition of mfix for lists is
</p>
<pre class="wiki">instance MonadFix [] where
mfix f = case fix (f . head) of
[] -> []
(x:_) -> x : mfix (tail . f)
</pre><p>
This assumes that mfix (tail . f) = tail (mfix f), which simply is not true
(for one thing, it would drop the head of anything produced by f.)
My attempts to use it failed with a stack error:
</p>
<pre class="wiki">00:50 oerjan> > mfix (([1,2]++).(:[]))
00:50 lambdabot> Exception: stack overflow
</pre><p>
The following replacement should give the result I expected:
</p>
<pre class="wiki">instance MonadFix [] where
mfix f = l where
l = case fix (f . head) of
[] -> []
x@(_:_) -> x ++ concatMap f (tail l)
00:51 oerjan> > mfix' (([1,2]++).(:[]))
00:51 lambdabot>
[1,2,1,1,2,2,1,2,1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2,1,2,1,1,2,1,1,2,2,1,2,1,1,2 ...
</pre>en-usGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/ticket/1449
Trac 1.2oerjan@…Thu, 21 Jun 2007 22:16:15 GMT
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:1
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:1
<p>
I realized that my solution does not give a particularly useful result when fix (f . head) is a single element list. Since any number of repetitions is a fixpoint in this case, it is not entirely obvious which one to choose (1 or infinitely many, I guess.) The following returns an infinite list, and is still slightly nonstrict for x = (y:undefined):
</p>
<pre class="wiki">instance MonadFix [] where
mfix f = l where
l = case fix (f . head) of
[] -> []
x@(_:r) -> x ++ case r of
[] -> l
_ -> concatMap f (tail l)
</pre>
TicketIsaac DupreeThu, 21 Jun 2007 23:16:44 GMT
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:2
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:2
<p>
Personally I have never yet understood what the meaning of MonadFix [] is... perhaps that is because it never had a correct/sensible definition? Do we have a consensus or even a good idea of what it should mean, or even some examples that use mfix::(a->[a])->[a] that are supposed to have a particular result?
</p>
TicketrossFri, 22 Jun 2007 01:02:22 GMTstatus changed; resolution set
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:3
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>invalid</em>
</li>
</ul>
<p>
<code>mfix</code> is intended to be <em>value recursion</em>, where the values are fed back, not the monadic computation (in this case the outer list). This is enforced by the <code>mfix</code> laws, which are reproduced in the documentation of <code>MonadFix</code>. The proposed definition violates at least the purity and left sliding laws, as the following expected equations do not hold:
</p>
<pre class="wiki">mfix (return . const 1) = return (fix (const 1))
mfix (\x -> [1,2] >>= \y -> [y,3]) = [1,2] >>= \y -> mfix (\x -> [y,3])
</pre><p>
Value recursion on the list monad isn't very useful; here's an example:
</p>
<pre class="wiki">mfix (\xs -> [take 3 (1:xs), take 4 (2:xs)])
</pre><p>
For much more detail, see Levent Erkok's thesis <em>Value Recursion in Monadic Computations</em> (from which the above examples were taken).
</p>
TicketrossFri, 22 Jun 2007 08:17:47 GMT
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:4
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:4
<p>
Typo: "left sliding" should have been "left tightening".
</p>
<p>
Regarding the <code>Show Char</code> instance, if there's a bug it's in the Haskell 98 Report, as the implementations follow it faithfully in this case.
</p>
TicketsimonmarTue, 30 Sep 2008 15:40:15 GMTarchitecture changed
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:5
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:5
<ul>
<li><strong>architecture</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
TicketsimonmarTue, 30 Sep 2008 15:51:23 GMTos changed
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:6
http://ghc.haskell.org/trac/ghc/ticket/1449#comment:6
<ul>
<li><strong>os</strong>
changed from <em>Unknown</em> to <em>Unknown/Multiple</em>
</li>
</ul>
Ticket