[GHC] #1449: Bug in instance MonadFix []

[GHC]

#1449: Bug in instance MonadFix []
-------------------------------------+--------------------------------------
  Reporter:  oerjan at nvg.ntnu.no      |          Owner:         
      Type:  bug                     |         Status:  new    
  Priority:  normal                  |      Milestone:         
 Component:  libraries/base          |        Version:  6.6.1  
  Severity:  normal                  |       Keywords:         
Difficulty:  Unknown                 |             Os:  Unknown
  Testcase:  mfix (([1,2]++).(:[]))  |   Architecture:  Unknown
-------------------------------------+--------------------------------------
(Thanks to Simon Marlow for pointing me to trac)

 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.)

 The definition of mfix for lists is

 {{{
 instance MonadFix [] where
     mfix f = case fix (f . head) of
                []    -> []
                (x:_) -> x : mfix (tail . f)
 }}}

 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:

 {{{
 00:50  oerjan> > mfix (([1,2]++).(:[]))
 00:50  lambdabot>  Exception: stack overflow
 }}}

 The following replacement should give the result I expected:

 {{{
 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
 ...
 }}}

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1449>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
-------------- next part --------------
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs at haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs