#7436: Derived Foldable and Traversable instances become extremely inefficient
due
to eta-expansion
---------------------------------+------------------------------------------
Reporter: shachaf | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 7.6.1
Keywords: | Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: Runtime performance bug
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
---------------------------------+------------------------------------------
Comment(by shachaf):
I just noticed that `DeriveFunctor` has the same issue, in a slightly less
severe form (you have to look at all the elements to do quadratic work).
"slow" is the instance that would be derived.
{{{
data List a = Nil | Cons a (List a)
mkList :: Int -> List Int
mkList 0 = Nil
mkList n = Cons n (mkList (n-1))
sumList :: List Int -> Int
sumList = go 0
where
go a Nil = a
go a (Cons n ns) = a `seq` go (a+n) ns
slow :: (a -> b) -> List a -> List b
slow f Nil = Nil
slow f (Cons x xs) = Cons (f x) (slow (\e -> f e) xs)
fast :: (a -> b) -> List a -> List b
fast f Nil = Nil
fast f (Cons x xs) = Cons (f x) (fast f xs)
main :: IO ()
main = print $ sumList . slow id $ mkList n
where n = 100000
}}}
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/7436#comment:6>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
