[GHC] #9345: Data.List.inits is extremely slow

[GHC]

#9345: Data.List.inits is extremely slow
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  bug         |           Status:  new
              Priority:  normal      |        Milestone:  7.8.4
             Component:              |          Version:  7.8.3
  libraries/base                     |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Easy (less than 1
  Unknown/Multiple                   |  hour)
       Type of failure:  Runtime     |       Blocked By:
  performance bug                    |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 I've worked on it a bit, and if I'm not mistaken, `myScanl'` is safe if,
 whenever `a /= _|_`, and however I choose `evil`, `wrong`, and `f`, the
 "correct" expression

 {{{
 e1 = a `evil`
      foldr evil wrong $
        foldr (\b g x -> (let b' = f x b in b' `seq` (b' : g b')))
           (\b -> b `seq` [])
           bs
           a
 }}}

 gives the same result as the fused expression

 {{{
 e2 = a `evil`
      foldr (\b g x -> (let b' = f x b in b' `seq` (b' `evil` g b')))
            (\b -> b `seq` wrong)
            bs
            a
 }}}

 But I'm not sure how to prove this or find a counterexample. Any ideas?

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9345#comment:10>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler