id,summary,reporter,owner,description,type,status,priority,milestone,component,version,resolution,keywords,cc,os,architecture,failure,difficulty,testcase,blockedby,blocking,related
7436,Derived Foldable and Traversable instances become extremely inefficient due to eta-expansion,shachaf,,"The following program:

{{{
{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}
import Prelude hiding (foldr)
import Data.Foldable

data List a = Nil | Cons a (List a)
    deriving (Functor, Foldable)

mkList :: Int -> List Int
mkList 0 = Nil
mkList n = Cons n (mkList (n-1))

main :: IO ()
main = print $ foldr (\x y -> y) ""end"" (mkList n)
  where n = 100000
}}}

Takes `n^2` time to run with GHC 7.6.1 -O2.

The generated `Foldable` code looks something like this:

{{{
instance Foldable List where
    foldr f z Nil = z
    foldr f z (Cons x xs) = f x (foldr (\a b -> f a b) z xs)
}}}

Eta-reducing the function, i.e.

{{{
instance Foldable List where
    foldr f z Nil = z
    foldr f z (Cons x xs) = f x (foldr f z xs)
}}}

Makes the program linear in `n` (in this case, runtime goes from 8.160s to 0.004s).

The `Traversable` instance also has the same issue.

There seem to be three different issues:

 * Derived `Foldable` and `Traversable` instances are nearly unusable for large structures.

 * An eta-expanded definition like `foldr` becomes asymptotically worse for some reason. Maybe this is expected behavior for this function, since `f` gets eta-expanded at each iteration?

 * `Foldable` instances are generated with `foldr` instead of `foldMap`.

This isn't directly related, since the code would have the same problem either
way, but since I'm already writing about it... `foldMap` can allow
asymptotically better operations on a structure than `foldr` (for example,
finding the rightmost leaf of a binary tree using `Data.Monoid.Last`), so it
should probably be generated instead. A `foldMap` definition should look like a
simpler version of `traverse`, which is already derivable. Maybe this should be
a separate ticket.",bug,merge,normal,7.6.3,Compiler,7.6.1,fixed,,patrick@… twanvl dreixel hackage.haskell.org@… jwlato@…,Unknown/Multiple,Unknown/Multiple,Runtime performance bug,Unknown,perf/should_runt/T7436,,,