The next version (7.10) of GHC is slated to have a drastically changed Prelude, driven by the (aptly) named Burning Bridges Proposal (BBP), ticket 9586. This proposal generalises many list operations, e.g. foldr, so they are overloaded  typically becoming members of either Foldable or Traversable. A complete list pf changes is given at the foot of this page. Gershom has made a wiki page that describes the change in more detail.
This message comes very late in the release process, but we would urge caution before changing. Even though the work has been going on for a while, it seems that this change is coming as a surprise to many people (including Simon Peyton Jones).
There is much to welcome in BBP, but changing the Prelude cannot be done lightly since it really is like changing the language. So I think it's really important for a large number of people to be able to try out such changes before they come into effect, and to have time to let the changes stabilize (you rarely get it right the first time).
I've discussed this with a number of people, including Simon PJ, and we have concrete proposals.
Nothing here proposes any change to AMP (which made Applicative
a superclass of Monad
). AMP is a change to Prelude, but it was discussed for much longer; was brought in over more than one GHC version (GHC 7.8 had custom warnings to encourage library authors to make changes); and is structurally baked into GHC (because of the connection with desugaring). In contrast BBP is a libraryonly change. Anyway, there is no suggestion here to row back on AMP.
Plan B
Simon Marlow rightly points out that adding a new LANGUAGE
pragma is full of backwards compatibility problems. So instead of the proposals below, here's a different plan how to introduce BBP.
 Leave
Data.List
type signatures and exports alone.  Make ghc 7.10 warn when
Data.List
has been imported in a way that will break with BBP.  No changes to
Prelude
signatures, but ship ghc 7.10 withPreludeBBP
.  Make
PreludeBBP
the default in ghc 7.12 (or later).
This will give us time to discuss exactly what should go into Foldable
.
The signature changes in Control.Monad
and other modules are unrelated to BBP and should be in ghc 7.10.
The ghc warning for importing Data.List
should be as helpful as possible, something like:
Foo:5:1 Warning: Data.List imported unqualified, this will conflict with BBP.
Instead use 'import Data.List(maximumBy, sortBy)'
Possible ghc 7.12 extension
If we feel forcing people to change Data.List
imports is too onerous, I suggest a small extension to name lookup in ghc. You can declare a symbol to be weak, and in the presence of a weak and a strong symbol the lookup will pick the strong one. So in Data.List
you'd say
{# WEAK foldr #}
foldr :: (a>b>b) > b > [a] > b
foldr = ...
And the Foldable
version of foldr
would be normal. The compiler would then pick the Foldable
symbol and issue a warning. I view this extension purely as a device to be used to make these kinds of transitions smooth.
Proposal 1:

Add a new pragma
{# LANGUAGE Prelude=AlternativePrelude #}
 This is a new feature, but it is easy and lowrisk to implement.
 Which Prelude you use really is a language choice; appropriate for a LANGUAGE pragma.
 Semantics is namespace only: import Prelude (); import AlternativePrelude
 No effect on desugaring or typing of builtin syntax (list comprehensions, donotation etc).

Ship with both old and new prelude.
With these changes, the current and new behaviour are easy to achieve, in the module or in a .cabal file. The question becomes "what is the default?".
Another alternative to {# LANGUAGE Prelude=AlternativePrelude #}
would be to use {# LANGUAGE NoImplicitPrelude #}
combined with import AlternativePrelude
. This requires sourcecode changes, but has no issues with backward compatibility with earlier versions of GHC.
Proposal 2:
Make the default be the old rather than the new.
 Altering the default Prelude API should be done slowly, with lots of warning; because all users get it willynilly.
 Unlike AMP, the change is controversial (clearly).
 Easier to make changes to New Prelude if it isn't the default.
Proposal 3:
The only remaining problem is that Data.List
and Control.Monad
have been similarly generalised, and while changing the Prelude with a language pragma makes sense, changing those modules doesn't. This problem only exists if, e.g. Data.List
has been imported unqualified and without an import list.
We can solve this by leaving Data.List
and Control.Monad
unchanged and having ghc warn when they are imported in a way that will conflict when BPP goes into effect (in a similar way ghc warned about AMP). It could look like this:
Foo:5:1 Warning: Data.List imported unqualified, this will conflict with BBP. Instead use 'import Data.List(maximumBy, sortBy)'
Rationale
What is the rationale behind proposal 1? We want to make it easy to switch an entire package over to an alternative Prelude. This can be done by putting the pragma in the .cabal file. Using the NoImplicitPrelude
doesn't work, because that disables importing the Prelude altogether; we just want a different one, but with desugaring still being done in terms of the regular Prelude.
Questions
Discussing the BBP proposal we also came up with a number of technical questions:
Q1
An alternative to Foldable would be
class Enumerable t where
toList :: t a > [a]  Implementations should use 'build'
Is Foldable
more general (or efficient) than a Enumerable
class, plus fusion?
Consider a new data type X a. I write
foldX :: (a > b > b) > b > X a > b
foldX = ...lots of code...
toList :: X a > [a] {# INLINE toList #}
toList x = build (\c n. foldX c n x)
So now toList
is small and easy to inline. Every good list consumer of a call to toList
will turn into a call to foldX
, which is what we want.
Q2
What are the criteria for being in Foldable?
For instance, why are sum
, product
in Foldable
, but not and
, or
?
Q3
What's the relationship of Foldable
to GHC.Exts.IsList
?
Which also has toList
, fromList
, and does work with ByteString
.
 For example, could we use
IsList
instead ofFoldable
?
Specifically,
Foldable
does not use its potential power to apply the type constructort
to different arguments. (UnlikeTraversable
which does.)foldr :: IsList l => (Item l>b>b) > b > l > b
Q4
The operations themselves (listed below) seem to miss some operations that could be generalised (isPrefixOf, scanl, findIndex), and some contexts still use Monad when they could be adjusted to Applicative (sequence_). We suspect there will be additional generalisations in the next version of the base library.
Some historical remarks
Many moons ago a similar generalization of the Prelude was considered. That time it was about, e.g., generalizing the type of map
that was generalized to have the type that fmap
has today. This proposal was consider too radical and was ultimately rejected.
Links
 http://neilmitchell.blogspot.co.uk/2014/10/howtorewriteprelude.html
 http://neilmitchell.blogspot.co.uk/2014/10/whytraversablefoldableshouldnotbe.html
 http://www.yesodweb.com/blog/2014/10/classybaseprelude, http://www.reddit.com/r/haskell/comments/2if0fu/on_concerns_about_haskells_prelude_favoring/
Raw diff of changes to base from 7.8 to 7.10
Control.Monad
+ (<$!>) :: Monad m => (a > b) > m a > m b
 class Monad m
+ class Applicative m => Monad m
 class Monad m => MonadPlus m
+ class (Alternative m, Monad m) => MonadPlus m
 foldM :: Monad m => (a > b > m a) > a > [b] > m a
+ foldM :: (Foldable t, Monad m) => (b > a > m b) > b > t a > m b
 foldM_ :: Monad m => (a > b > m a) > a > [b] > m ()
+ foldM_ :: (Foldable t, Monad m) => (b > a > m b) > b > t a > m ()
 forM :: Monad m => [a] > (a > m b) > m [b]
+ forM :: (Traversable t, Monad m) => t a > (a > m b) > m (t b)
 forM_ :: Monad m => [a] > (a > m b) > m ()
+ forM_ :: (Foldable t, Monad m) => t a > (a > m b) > m ()
 guard :: MonadPlus m => Bool > m ()
+ guard :: (Alternative f) => Bool > f ()
 mapM :: Monad m => (a > m b) > [a] > m [b]
+ mapM :: (Traversable t, Monad m) => (a > m b) > t a > m (t b)
 mapM_ :: Monad m => (a > m b) > [a] > m ()
+ mapM_ :: (Foldable t, Monad m) => (a > m b) > t a > m ()
 msum :: MonadPlus m => [m a] > m a
+ msum :: (Foldable t, MonadPlus m) => t (m a) > m a
 sequence :: Monad m => [m a] > m [a]
+ sequence :: (Traversable t, Monad m) => t (m a) > m (t a)
 sequence_ :: Monad m => [m a] > m ()
+ sequence_ :: (Foldable t, Monad m) => t (m a) > m ()
 unless :: Monad m => Bool > m () > m ()
+ unless :: (Applicative f) => Bool > f () > f ()
 when :: Monad m => Bool > m () > m ()
+ when :: (Applicative f) => Bool > f () > f ()
Data.Bits
+ countLeadingZeros :: FiniteBits b => b > Int
+ countTrailingZeros :: FiniteBits b => b > Int
+ toIntegralSized :: (Integral a, Integral b, Bits a, Bits b) => a > Maybe b
Data.Monoid
+ Alt :: f a > Alt f a
+ getAlt :: Alt f a > f a
+ newtype Alt f a
Data.List
 all :: (a > Bool) > [a] > Bool
+ all :: Foldable t => (a > Bool) > t a > Bool
 and :: [Bool] > Bool
+ and :: Foldable t => t Bool > Bool
 any :: (a > Bool) > [a] > Bool
+ any :: Foldable t => (a > Bool) > t a > Bool
 concat :: [[a]] > [a]
+ concat :: Foldable t => t [a] > [a]
 concatMap :: (a > [b]) > [a] > [b]
+ concatMap :: Foldable t => (a > [b]) > t a > [b]
 elem :: Eq a => a > [a] > Bool
+ elem :: (Foldable t, Eq a) => a > t a > Bool
 find :: (a > Bool) > [a] > Maybe a
+ find :: Foldable t => (a > Bool) > t a > Maybe a
 foldl :: (b > a > b) > b > [a] > b
+ foldl :: Foldable t => (b > a > b) > b > t a > b
 foldl' :: (b > a > b) > b > [a] > b
+ foldl' :: Foldable t => (b > a > b) > b > t a > b
 foldl1 :: (a > a > a) > [a] > a
+ foldl1 :: Foldable t => (a > a > a) > t a > a
 foldr :: (a > b > b) > b > [a] > b
+ foldr :: Foldable t => (a > b > b) > b > t a > b
 foldr1 :: (a > a > a) > [a] > a
+ foldr1 :: Foldable t => (a > a > a) > t a > a
+ isSubsequenceOf :: (Eq a) => [a] > [a] > Bool
 length :: [a] > Int
+ length :: Foldable t => t a > Int
 mapAccumL :: (acc > x > (acc, y)) > acc > [x] > (acc, [y])
+ mapAccumL :: Traversable t => (a > b > (a, c)) > a > t b > (a, t c)
 mapAccumR :: (acc > x > (acc, y)) > acc > [x] > (acc, [y])
+ mapAccumR :: Traversable t => (a > b > (a, c)) > a > t b > (a, t c)
 maximum :: Ord a => [a] > a
+ maximum :: (Foldable t, Ord a) => t a > a
 maximumBy :: (a > a > Ordering) > [a] > a
+ maximumBy :: Foldable t => (a > a > Ordering) > t a > a
 minimum :: Ord a => [a] > a
+ minimum :: (Foldable t, Ord a) => t a > a
 minimumBy :: (a > a > Ordering) > [a] > a
+ minimumBy :: Foldable t => (a > a > Ordering) > t a > a
 notElem :: Eq a => a > [a] > Bool
+ notElem :: (Foldable t, Eq a) => a > t a > Bool
 null :: [a] > Bool
+ null :: Foldable t => t a > Bool
 or :: [Bool] > Bool
+ or :: Foldable t => t Bool > Bool
 product :: Num a => [a] > a
+ product :: (Foldable t, Num a) => t a > a
+ scanl' :: (b > a > b) > b > [a] > [b]
+ sortOn :: Ord b => (a > b) > [a] > [a]
 sum :: Num a => [a] > a
+ sum :: (Foldable t, Num a) => t a > a
+ uncons :: [a] > Maybe (a, [a])
Foreign.Marshal.Alloc
+ calloc :: Storable a => IO (Ptr a)
+ callocBytes :: Int > IO (Ptr a)
Foreign.Marshal.Utils
+ fillBytes :: Ptr a > Word8 > Int > IO ()
Foreign.Marshal.Array
+ callocArray :: Storable a => Int > IO (Ptr a)
+ callocArray0 :: Storable a => Int > IO (Ptr a)
Control.Exception.Base
+ AllocationLimitExceeded :: AllocationLimitExceeded
+ data AllocationLimitExceeded
+ displayException :: Exception e => e > String
Control.Exception
+ AllocationLimitExceeded :: AllocationLimitExceeded
+ data AllocationLimitExceeded
+ displayException :: Exception e => e > String
Prelude
+ (*>) :: Applicative f => f a > f b > f b
+ (<*) :: Applicative f => f a > f b > f a
+ (<*>) :: Applicative f => f (a > b) > f a > f b
 all :: (a > Bool) > [a] > Bool
+ all :: Foldable t => (a > Bool) > t a > Bool
 and :: [Bool] > Bool
+ and :: Foldable t => t Bool > Bool
 any :: (a > Bool) > [a] > Bool
+ any :: Foldable t => (a > Bool) > t a > Bool
 class Monad m
+ class Applicative m => Monad m
+ class Monoid a
+ class Functor f => Applicative f
+ class Foldable t
+ class (Functor t, Foldable t) => Traversable t
 concat :: [[a]] > [a]
+ concat :: Foldable t => t [a] > [a]
 concatMap :: (a > [b]) > [a] > [b]
+ concatMap :: Foldable t => (a > [b]) > t a > [b]
+ data Word :: *
 elem :: Eq a => a > [a] > Bool
+ elem :: (Foldable t, Eq a) => a > t a > Bool
+ foldMap :: (Foldable t, Monoid m) => (a > m) > t a > m
 foldl :: (b > a > b) > b > [a] > b
+ foldl :: Foldable t => (b > a > b) > b > t a > b
 foldl1 :: (a > a > a) > [a] > a
+ foldl1 :: Foldable t => (a > a > a) > t a > a
 foldr :: (a > b > b) > b > [a] > b
+ foldr :: Foldable t => (a > b > b) > b > t a > b
 foldr1 :: (a > a > a) > [a] > a
+ foldr1 :: Foldable t => (a > a > a) > t a > a
 length :: [a] > Int
+ length :: Foldable t => t a > Int
 mapM :: Monad m => (a > m b) > [a] > m [b]
+ mapM :: (Traversable t, Monad m) => (a > m b) > t a > m (t b)
 mapM_ :: Monad m => (a > m b) > [a] > m ()
+ mapM_ :: (Foldable t, Monad m) => (a > m b) > t a > m ()
+ mappend :: Monoid a => a > a > a
 maximum :: Ord a => [a] > a
+ maximum :: (Foldable t, Ord a) => t a > a
+ mconcat :: Monoid a => [a] > a
+ mempty :: Monoid a => a
 minimum :: Ord a => [a] > a
+ minimum :: (Foldable t, Ord a) => t a > a
 notElem :: Eq a => a > [a] > Bool
+ notElem :: (Foldable t, Eq a) => a > t a > Bool
 null :: [a] > Bool
+ null :: Foldable t => t a > Bool
 or :: [Bool] > Bool
+ or :: Foldable t => t Bool > Bool
 product :: Num a => [a] > a
+ product :: (Foldable t, Num a) => t a > a
+ pure :: Applicative f => a > f a
 sequence :: Monad m => [m a] > m [a]
+ sequence :: (Traversable t, Monad m) => t (m a) > m (t a)
+ sequenceA :: (Traversable t, Applicative f) => t (f a) > f (t a)
 sequence_ :: Monad m => [m a] > m ()
+ sequence_ :: (Foldable t, Monad m) => t (m a) > m ()
 sum :: Num a => [a] > a
+ sum :: (Foldable t, Num a) => t a > a
+ traverse :: (Traversable t, Applicative f) => (a > f b) > t a > f (t b)
Data.Function
+ (&) :: a > (a > b) > b
Control.Monad.Instances
 class Monad m
+ class Applicative m => Monad m
Data.Coerce
 coerce :: Coercible k a b => a > b
+ coerce :: Coercible * a b => a > b
Data.Version
+ makeVersion :: [Int] > Version
Data.Complex
 cis :: RealFloat a => a > Complex a
+ cis :: Floating a => a > Complex a
 conjugate :: RealFloat a => Complex a > Complex a
+ conjugate :: Num a => Complex a > Complex a
 imagPart :: RealFloat a => Complex a > a
+ imagPart :: Complex a > a
 mkPolar :: RealFloat a => a > a > Complex a
+ mkPolar :: Floating a => a > a > Complex a
 realPart :: RealFloat a => Complex a > a
+ realPart :: Complex a > a
Data.Foldable
+ length :: Foldable t => t a > Int
+ null :: Foldable t => t a > Bool
System.Exit
+ die :: String > IO a
Numeric.Natural
+ data Natural
Data.Bifunctor
+ bimap :: Bifunctor p => (a > b) > (c > d) > p a c > p b d
+ class Bifunctor p
+ first :: Bifunctor p => (a > b) > p a c > p b c
+ second :: Bifunctor p => (b > c) > p a b > p a c
Data.Functor.Identity
+ Identity :: a > Identity a
+ newtype Identity a
+ runIdentity :: Identity a > a
Data.Void
+ absurd :: Void > a
+ data Void
+ vacuous :: Functor f => f Void > f a