Opened 3 years ago

Closed 2 years ago

#9586 closed task (fixed)

Implement Traversable/Foldable-Burning-Bridges Proposal

Reported by: hvr Owned by: hvr
Priority: normal Milestone: 7.10.1
Component: Core Libraries Version:
Keywords: report-impact Cc: hvr, ekmett, core-libraries-committee@…, George, lelf
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #9621 Differential Rev(s): Phab:D209
Wiki Page:

Description (last modified by hvr)

More details to follow. I've created this ticket to be able to refer to from related preparatory commits.

In a nutshell the FTP (Foldable/Traversable-Proposal) sub-goal of the BBP (Burning-Bridges-Proposal) includes to be able to compile code like the following w/o errors (due to conflicting definitions):

module XPrelude (module X) where

import Data.Foldable     as X
import Data.Traversable  as X
import Data.List         as X
import Control.Monad     as X
import Prelude           as X

Other goals include to generalise/weaken type-signatures where possible w/o breaking (much) compatibility with existing code. An in-depth design-document is in the works.

Change History (47)

comment:1 Changed 3 years ago by hvr

Differential Rev(s): Phab:D209

The medium-sized patch in Phab:D209 implements the first phase, namely to re-export solely the two type-classes Foldable and Traversable (sans any methods) from Prelude

comment:2 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In c0fa383d9109800a4e46a81b418f1794030ba1bd/ghc:

Export `Traversable()` and `Foldable()` from Prelude

This exposes *only* the type-classes w/o any of their methods.
This is the very first step for implementing BPP (see #9586), which
already requires breaking up several import-cycles leading back to `Prelude`.

Ideally, importing `Prelude` should be avoided in most `base` modules,
as `Prelude` does not define any entities, but rather re-exports
existing ones.

Test Plan: validate passes

Reviewers: ekmett, austin

Reviewed By: ekmett, austin

Subscribers: simonmar, ezyang, carter

Differential Revision: https://phabricator.haskell.org/D209

GHC Trac Issues: #9586

comment:3 Changed 3 years ago by hvr

Description: modified (diff)

comment:4 Changed 3 years ago by dfeuer

I think if you're doing this, it would make sense to generalize these too:

null :: (Foldable f) => f a -> Bool
null = foldr (\_ _ -> False) True

length :: (Foldable f) => f a -> Int
length = foldl' (\k _ -> k + 1) 0

--and even though it's a very strange thing already
genericLength :: (Foldable f, Num n) => f a -> n
genericLength = foldr (\_ k -> 1 + k) 0
Last edited 3 years ago by dfeuer (previous) (diff)

comment:5 in reply to:  4 ; Changed 3 years ago by dfeuer

rwbarton points out that there are optimized versions of these for various things, and that most containers use size instead of length. Therefore, I would propose instead adding size and null to the Foldable class, with default definitions as above.

Last edited 3 years ago by dfeuer (previous) (diff)

comment:6 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 8b9083655f34120b47fe407123272e0687e0bd60/ghc:

Move (=<<) to GHC.Base

This allows GHC.Stack to avoid importing Control.Monad, and
is preparatory work for implementing #9586

Reviewed By: austin

Differential Revision: https://phabricator.haskell.org/D221

comment:7 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In eae19112462fe77a3f1298bff12b409b205a581d/ghc:

Move `when` to GHC.Base

This allows several modules to avoid importing Control.Monad and thus break
import cycles that manifest themselves when implementing #9586

Reviewed By: austin, ekmett

Differential Revision: https://phabricator.haskell.org/D222

comment:8 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In a94dc4c3067c6a0925e2e39f35ef0930771535f1/ghc:

Move Applicative/MonadPlus into GHC.Base

This is necessary in order to invert the import-dependency between
Data.Foldable and Control.Monad (for addressing #9586)

This also updates the `binary` submodule to qualify a GHC.Base import

Reviewed By: austin

Differential Revision: https://phabricator.haskell.org/D223

comment:9 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In af22696b8f6d8b677c33f70537a5999ad94266cd/ghc:

Invert module-dep between Control.Monad and Data.Foldable

This is the last preparation needed before generalizing entities in
Control.Monad conflicting with those from Data.Foldable (re #9586)

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D225

comment:10 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In b4060858f5201489e11ab57063e72380c03c3b55/ghc:

Generalise Control.Monad.{sequence_,msum,mapM_,forM_}

This finally takes the gloves off, and performs the first actual
generalization in order to implement #9586. This re-exports the
respective definitions for the 4 combinators defined in Data.Foldable.

This way, importing Data.Foldable and Control.Monad unqualified won't bring
conflicting definitions of those 4 entities into scope anymore.

This change seems to have some minor effect on rule-firing, which
causes some wibble in the test-case T4007

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D226

comment:11 Changed 3 years ago by dfeuer

rwbarton mentions also scanl1 and scanr1.

comment:12 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 3daf0023d2dcf7caf85d61f2dc177f8e9421b2fd/ghc:

Set up framework for generalising Data.List to Foldables

This renames the Data.List module to Data.OldList, and puts a new
Data.List module into its place re-exporting all list functions.

The plan is to leave the monomorphic versions of the list functions in
Data.OldList to help smooth the transition.

The new Data.List module then will simply re-export entities from
Data.OldList and Data.Foldable.

This refactoring has been placed in a separate commit to be able to
better isolate any regressions caused by the actual list function
generalisations when implementing #9586

This also updates the haskell2010, haskell98, and array submodules

Reviewed By: austin, ekmett

Differential Revision: https://phabricator.haskell.org/D228

comment:13 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 1812898c0332c6807201938911bb914633267d9d/ghc:

Turn a few existing folds into `Foldable`-methods (#9621)

Turn `toList`, `elem`, `sum`, `product`, `maximum`, and `minimum` into
`Foldable` methods. This helps avoiding regressions (and semantic
differences) while implementing #9586

Reviewed By: austin, dfeuer, ekmett

Differential Revision: https://phabricator.haskell.org/D231

comment:14 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In ed65808cebf068a98f564f6ad962838c6526591b/ghc:

Add missing changelog entries for current state of #9586

comment:15 in reply to:  5 Changed 3 years ago by hvr

Replying to dfeuer:

rwbarton points out that there are optimized versions of these for various things, and that most containers use size instead of length. Therefore, I would propose instead adding size and null to the Foldable class, with default definitions as above.

Extending Foldable has become a ticket of its own at #9621

comment:16 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In e7c1633203e33c4a1af866c8658683bcef20a514/ghc:

Simplify import-graph a bit more

This is preparatory refactoring for avoiding import cycles
when `Data.Traversable` will be imported by `Control.Monad` and
`Data.List` for implementing #9586

comment:17 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 5ed12810e0972b1e0d408fe1355805746c4614f9/ghc:

Move `mapM` and `sequence` to GHC.Base and break import-cycles

This simplifies the import graph and more importantly removes import
cycles that arise due to `Control.Monad` & `Data.List` importing
`Data.Traversable` (preparation for #9586)

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D234

comment:18 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In b8f583928fa6cb5371a872fc73080d2002dd87d9/ghc:

Export `Monoid(..)`/`Foldable(..)`/`Traversable(..)` from Prelude

This finally exposes also the methods of these 3 classes in the Prelude
in order to allow to define basic class instances w/o needing imports.

This almost completes the primary goal of #9586

NOTE: `fold`, `foldl'`, `foldr'`, and `toList` are not exposed yet,
      as they require upstream fixes for at least `containers` and
      `bytestring`, and are not required for defining basic instances.

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D236

comment:19 Changed 3 years ago by goldfire

See also comment:4:ticket:9568 and comment:5:ticket:9568 which were posted to the wrong ticket.

comment:20 in reply to:  19 Changed 3 years ago by hvr

Replying to goldfire:

See also comment:4:ticket:9568 and comment:5:ticket:9568 which were posted to the wrong ticket.

Thanks for noticing. With so many commits this was bound to happen... :-)


In 05cf18f883bf2d49b53a1d25cb57eff3333eb0c9/ghc:

Generalise (some of) Data.List to Foldables (re #9568)

This replaces the entities in Data.List conflicting with Data.Foldable
with re-exports of the generalised version from Data.Foldable.

As of this commit, the following compiles w/o error

    module XPrelude (module X) where

    import Control.Monad as X
    import Data.Foldable as X
    import Data.List as X
    import Prelude as X

Reviewed By: austin, dfeuer, ekmett

Differential Revision: https://phabricator.haskell.org/D229

In 1f7f46f94a95ab7fc6f3101da7c02529e1964f24/ghc:

Generalise Data.List/Control.Monad to Foldable/Traversable

This flips the switch and replaces the entities in
`Data.List`/`Control.Monad` conflicting with
`Data.{Foldable,Traversable}` with re-exports of the more general
versions.

As of this commit, the code below (which is also added as a test-case)
compiles w/o error.

    module XPrelude (module X) where

    import Control.Monad     as X
    import Data.Foldable     as X
    import Data.List         as X
    import Data.Monoid       as X
    import Data.Traversable  as X
    import Prelude           as X

This addresses #9568

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D235

comment:21 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 27b937e5012c902a513dbc3b6ae24bf490ce656e/ghc:

Fix windows breakage from 5ed12810e0972b1e due to import cycles

Refs #9586

comment:22 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 165072b334ebb2ccbef38a963ac4d126f1e08c96/ghc:

Adapt nofib submodule to #9586 changes

comment:23 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In 319703ee0c97c593be514222fdee06555816cda4/ghc:

Don't re-export `Alternative(..)` from Control.Monad (re #9586)

This was done in d94de87252d0fe2ae97341d186b03a2fbe136b04 to avoid orphans
but since a94dc4c3067c6a0925e2e39f35ef0930771535f1 moved `Alternative`
into GHC.Base, this isn't needed anymore.

This is important, as otherwise this would require a non-neglectable amount
of `Control.Monad hiding ((<|>), empty)` imports in user code.

The Haddock submodule is updated as well

Test Plan: partial local ./validate --fast, let Harbormaster doublecheck it

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D248

comment:24 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In a07ce1654ac5b8033f2daf9270c6e182415b69ca/ghc:

Generalise `Control.Monad.{when,unless,guard}`

Generalise `when`/`unless`from `Monad` to `Applicative` and `guard` from
`MonadPlus` to `Alternative` respectively.

This was made possible by the AMP and is somewhat related to #9586
(but generalising in the context of the AMP instead of the FTP)

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D253

comment:25 Changed 3 years ago by hvr

Description: modified (diff)

comment:26 in reply to:  18 Changed 3 years ago by rwbarton

Replying to Herbert Valerio Riedel <hvr@…>:

In b8f583928fa6cb5371a872fc73080d2002dd87d9/ghc:

Export `Monoid(..)`/`Foldable(..)`/`Traversable(..)` from Prelude

This finally exposes also the methods of these 3 classes in the Prelude
in order to allow to define basic class instances w/o needing imports.

This almost completes the primary goal of #9586

NOTE: `fold`, `foldl'`, `foldr'`, and `toList` are not exposed yet,
      as they require upstream fixes for at least `containers` and
      `bytestring`, and are not required for defining basic instances.

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D236

This patch seems to be unrelated to the scope of this ticket.

comment:27 in reply to:  24 ; Changed 3 years ago by rwbarton

Replying to Herbert Valerio Riedel <hvr@…>:

In a07ce1654ac5b8033f2daf9270c6e182415b69ca/ghc:

Generalise `Control.Monad.{when,unless,guard}`

Generalise `when`/`unless`from `Monad` to `Applicative` and `guard` from
`MonadPlus` to `Alternative` respectively.

This was made possible by the AMP and is somewhat related to #9586
(but generalising in the context of the AMP instead of the FTP)

Reviewed By: ekmett, austin

Differential Revision: https://phabricator.haskell.org/D253

Off-topic for this ticket but why not also generalize filterM, forever, ..., replicateM_? Are there hangups about the letter M in the names of some of these functions?

comment:28 in reply to:  27 ; Changed 3 years ago by dfeuer

Replying to rwbarton:

Off-topic for this ticket but why not also generalize filterM, forever, ..., replicateM_? Are there hangups about the letter M in the names of some of these functions?

filterM cannot be generalized to Traversable in any sensible way—it needs something stronger. forever and replicateM_ should be easy.

comment:29 in reply to:  28 Changed 3 years ago by rwbarton

Replying to dfeuer:

Replying to rwbarton:

Off-topic for this ticket but why not also generalize filterM, forever, ..., replicateM_? Are there hangups about the letter M in the names of some of these functions?

filterM cannot be generalized to Traversable in any sensible way—it needs something stronger. forever and replicateM_ should be easy.

I mean generalize from Monad to Applicative, not from [] to Traversable.

comment:30 Changed 3 years ago by thoughtpolice

Component: libraries/baseCore Libraries

Moving over to new owning component 'Core Libraries'.

comment:31 Changed 3 years ago by Herbert Valerio Riedel <hvr@…>

In ce23745147b9aab99187e266412efa27148a9b19/ghc:

Generalise `Control.Monad.{foldM,foldM_}` to `Foldable` (#9586)

With this change `Control.Monad.foldM` becomes an alias for
`Data.Foldable.foldlM`.

Reviewed By: austin, ekmett

Differential Revision: https://phabricator.haskell.org/D251

comment:32 Changed 2 years ago by hvr

Cc: core-libraries-committee@… added
Resolution: fixed
Status: newclosed

Let's close this; everything that was planned for milestone:7.10.1 has been implemented

comment:33 Changed 2 years ago by George

The description at the top says "An in-depth design-document is in the works." Was that done? If so, is there a link to it?

comment:34 Changed 2 years ago by ekmett

https://wiki.haskell.org/Foldable_Traversable_In_Prelude is the page we're grooming for that purpose.

comment:35 Changed 2 years ago by hvr

Keywords: report-impact added

comment:36 Changed 2 years ago by George

Given the ongoing discussion in e.g. the Libraries mailing list should the status still be closed? Are all the proposed changes in 7.10RC2? If so when will the 7.10 doc be updated to reflect them?

comment:37 Changed 2 years ago by George

Cc: George added

comment:38 Changed 2 years ago by ekmett

We are currently constructing a poll and summaries of two possible plans of action that will go out in the next day or so. Based on the results of that poll, which will likely run until the 28th or so, to give folks a couple of weeks to respond, Simon Peyton Jones and Simon Marlow will come to a decision on how we are going to proceed for 7.10.

comment:39 in reply to:  36 Changed 2 years ago by hvr

Replying to George:

If so when will the 7.10 doc be updated to reflect them?

Which part of the documentation are you referring to, btw?

comment:40 in reply to:  38 ; Changed 2 years ago by George

Thanks but I don't see an answer to my questions:

1) Should the status of this ticket still be closed? This issue doesn't show on

https://ghc.haskell.org/trac/ghc/wiki/Status/GHC-7.10.1 but the issue still appears to be open thus the referenced Status page doesn't give an indication of the true status of the release

2) Are all the proposed changes in 7.10RC2?

wrt doc I am referring to the GHC User's Guide and Hackage documentation such as https://hackage.haskell.org/package/base-4.7.0.2/docs/Data-List.html

comment:41 Changed 2 years ago by lelf

Cc: lelf added

comment:42 Changed 2 years ago by ekmett

Owner: hvr deleted
Resolution: fixed
Status: closednew

comment:43 Changed 2 years ago by ekmett

Owner: set to hvr

comment:44 Changed 2 years ago by ekmett

Status: newinfoneeded

comment:45 Changed 2 years ago by ekmett

I've re-opened this ticket while we seek feedback via

https://goo.gl/forms/XP1W2JdfpX

to connote its as-yet-ambiguous fate.

comment:46 in reply to:  40 Changed 2 years ago by hvr

Replying to George:

2) Are all the proposed changes in 7.10RC2?

wrt doc I am referring to the GHC User's Guide and Hackage documentation such as https://hackage.haskell.org/package/base-4.7.0.2/docs/Data-List.html

You can take a look at the base-4.8 candidate documentation for the mean-time which is fairly recent:

http://hackage.haskell.org/package/base-4.8.0.0/candidate

comment:47 Changed 2 years ago by George

Resolution: fixed
Status: infoneededclosed

It has been decided that we will move do this for 7.10.1, see https://mail.haskell.org/pipermail/libraries/2015-February/025009.html

Note: See TracTickets for help on using tickets.