Implement Traversable/Foldable-Burning-Bridges Proposal

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.

changed milestone to %7.10.1

changed weight to 5

added Ttask Trac import core libraries labels

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

Trac metadata

Trac field	Value
Differential revisions	→ D209

mentioned in commit c0fa383d

changed the description

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

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.

mentioned in commit 8b908365

mentioned in commit eae19112

mentioned in commit a94dc4c3

mentioned in commit af22696b

mentioned in commit b4060858

rwbarton mentions also scanl1 and scanr1.

mentioned in commit 3daf0023

mentioned in commit 1812898c

mentioned in commit ed65808c

Replying to [ticket:9586#comment:88309 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 (closed)

Trac metadata

Trac field	Value
Related	→ #9621 (closed)

mentioned in commit e7c16332

mentioned in commit 5ed12810

mentioned in commit b8f58392

See also #9568 (closed) and #9568 (closed) which were posted to the wrong ticket.

Replying to [ticket:9586#comment:88450 goldfire]:

See also #9568 (closed) and #9568 (closed) which were posted to the wrong ticket.

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

---

In [changeset:"05cf18f8/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 [changeset:"1f7f46f9/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

mentioned in commit 27b937e5

mentioned in commit 165072b3

mentioned in commit 319703ee

mentioned in commit a07ce165

changed the description

Replying to [#9586 (closed) Herbert Valerio Riedel <hvr@…>]:

In [changeset:"b8f58392/ghc"]: repository="ghc" revision="b8f583928fa6cb5371a872fc73080d2002dd87d9" 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 (closed)

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.

Replying to [#9586 (closed) Herbert Valerio Riedel <hvr@…>]:

In [changeset:"a07ce165/ghc"]: repository="ghc" revision="a07ce1654ac5b8033f2daf9270c6e182415b69ca" Generalise Control.Monad.{when,unless,guard}`

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

This was made possible by the AMP and is somewhat related to #9586 (closed) (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?

Replying to [ticket:9586#comment:88975 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.

Replying to [ticket:9586#comment:88982 dfeuer]:

Replying to [ticket:9586#comment:88975 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.

Moving over to new owning component 'Core Libraries'.

Trac metadata

Trac field	Value
Component	libraries/base → Core Libraries

mentioned in commit ce237451

closed

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

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed
CC	ekmett, hvr → core-libraries-committee@haskell.org, ekmett, hvr

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?

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

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?

Trac metadata

Trac field	Value
CC	core-libraries-committee@haskell.org, ekmett, hvr → George, core-libraries-committee@haskell.org, ekmett, hvr

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.

Replying to [ticket:9586#comment:96117 George]:

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

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

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

reopened

unassigned @hvr

Trac metadata

Trac field	Value
Resolution	ResolvedFixed → Unresolved

assigned to @hvr