summaryrefslogtreecommitdiff
path: root/libraries/base/Data/Foldable.hs
Commit message (Collapse)AuthorAgeFilesLines
* Make modules in base stable.Hécate Moonlight2022-02-281-1/+1
| | | | fix #18963
* Drop O(n^2) warning on concatViktor Dukhovni2021-12-091-3/+0
|
* A few more typosViktor Dukhovni2021-12-091-6/+7
|
* Fix typo and outdated link in Data.FoldableViktor Dukhovni2021-12-091-3/+3
| | | | | | | | Amazing nobody had reported the "Foldabla" typo. :-( The Traversable docs got overhauled, leaving a stale link in Foldable to a section that got replaced. Gave the new section an anchor and updated the link.
* Use italic big-O notation in Data.FoldableViktor Dukhovni2021-12-071-18/+18
|
* More specific documentation of foldr' caveatsViktor Dukhovni2021-12-071-3/+17
|
* List-monomorphic `foldr'`Viktor Dukhovni2021-12-071-1/+2
| | | | | | | | | | | | | While a *strict* (i.e. constant space) right-fold on lists is not possible, the default `foldr'` is optimised for structures like `Seq`, that support efficient access to the right-most elements. The original default implementation seems to have a better constant factor for lists, so we add a monomorphic implementation in GHC.List. Should this be re-exported from `Data.List`? That would be a user-visible change if both `Data.Foldable` and `Data.List` are imported unqualified...
* Revert "Data.List specialization to []"Matthew Pickering2021-12-031-1/+3
| | | | | | | | | | This reverts commit bddecda1a4c96da21e3f5211743ce5e4c78793a2. This implements the first step in the plan formulated in #20025 to improve the communication and migration strategy for the proposed changes to Data.List. Requires changing the haddock submodule to update the test output.
* Insert warnings in the documentation of dangerous functionsTom Sydney Kerckhove2021-10-151-0/+11
|
* Explain Endo, Dual, ... in lawsViktor Dukhovni2021-10-051-2/+40
|
* Adopt David Feuer's explantion of foldl' via foldrViktor Dukhovni2021-10-051-22/+31
|
* Minor wording tweaks/fixesViktor Dukhovni2021-10-051-21/+19
|
* Note elem ticket 20421Viktor Dukhovni2021-10-051-0/+4
|
* Note linear `elem` costViktor Dukhovni2021-10-051-10/+55
| | | | | This is a writeup of the state of play for better than linear `elem` via a helper type class.
* Address some Foldable documentation nitsViktor Dukhovni2021-10-051-14/+18
| | | | | | - Add link to laws from the class head - Simplify wording of left/right associativity intro paragraph - Avoid needless mention of "endomorphisms"
* Fix cut/paste typo foldrM should be foldlMViktor Dukhovni2021-07-021-1/+1
|
* Improve wording of fold[lr]M documentation.Viktor Dukhovni2021-06-021-53/+77
| | | | | | | | | | | | | | | The sequencing of monadic effects in foldlM and foldrM was described as respectively right-associative and left-associative, but this could be confusing, as in essence we're just composing Kleisli arrows, whose composition is simply associative. What matters therefore is the order of sequencing of effects, which can be described more clearly without dragging in associativity as such. This avoids describing these folds as being both left-to-right and right-to-left depending on whether we're tracking effects or operator application. The new text should be easier to understand.
* Implement list `fold` and `foldMap` via mconcatKoz Ross2021-04-101-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | - This allows specialized mconcat implementations an opportunity to combine elements efficiently in a single pass. - Inline the default implementation of `mconcat`, this may result in list fusion. - In Monoids with strict `mappend`, implement `mconcat` as a strict left fold: * And (FiniteBits) * Ior (FiniteBits) * Xor (FiniteBits) * Iff (FiniteBits) * Max (Ord) * Min (Ord) * Sum (Num) * Product (Num) * (a -> m) (Monoid m) - Delegate mconcat for WrappedMonoid to the underlying monoid. Resolves: #17123 Per the discussion in !4890, we expect some stat changes: * T17123(normal) run/alloc 403143160.0 4954736.0 -98.8% GOOD This is the expected improvement in `fold` for a long list of `Text` elements. * T13056(optasm) ghc/alloc 381013328.0 447700520.0 +17.5% BAD Here there's an extra simplifier run as a result of the new methods of the Foldable instance for List. It looks benign. The test is a micro benchmark that compiles just the derived foldable instances for a pair of structures, a cost of this magnitude is not expected to extend to more realistic programs. * T9198(normal) ghc/alloc 504661992.0 541334168.0 +7.3% BAD This test regressed from 8.10 and 9.0 back to exponential blowup. This metric also fluctuates, for reasons not yet clear. The issue here is the exponetial blowup, not this MR. Metric Decrease: T17123 Metric Increase: T9198 T13056
* Change foldl' to inline when partially applied (#19534)James Foster2021-04-071-14/+23
| | | | | And though partially applied foldl' is now again inlined, #4301 has not resurfaced, and appears to be resolved.
* Address review feedback on chiralityViktor Dukhovni2021-04-011-11/+45
| | | | Also added nested foldr example for `concat`.
* Chiral foldable caveatsViktor Dukhovni2021-04-011-3/+37
|
* Data.List specialization to []Oleg Grenrus2021-04-011-3/+1
| | | | | | | - Remove GHC.OldList - Remove Data.OldList - compat-unqualified-imports is no-op - update haddock submodule
* Rectify the haddock markup surrounding symbols for foldl' and foldMap'Hécate Moonlight2021-02-181-23/+23
| | | | closes #19365
* Add instances for GHC.Tuple.SoloBen Gamari2021-01-271-0/+4
| | | | | | | | | | | | | | | The `Applicative` instance is the most important one (for array/vector/sequence indexing purposes), but it deserves all the usual ones. T12545 does silly 1% wibbles both ways, it seems, maybe depending on architecture. Metric Increase: T12545 Metric Decrease: T12545
* Third pass on doctest corrections.Oleg Grenrus2021-01-171-0/+2
| | | | With `-K500K` rts option stack overflows are more deterministic
* Remove references to ApplicativeDo in the base haddocksHécate2021-01-131-1/+1
|
* Correct more doctestsOleg Grenrus2021-01-101-0/+4
|
* More tidy synopses, and new generative recursionViktor Dukhovni2021-01-091-69/+260
| | | | | | | | - Further correction and reconcialation with new overview of the existing synopses. Restored some "Tree" examples. - New section on generative recursion via Church encoding of lists.
* Reconcile extant synopses with new overview proseViktor Dukhovni2021-01-091-186/+323
| | | | | | | | | | | - Renamed new "update function" to "operator" from synopses - More accurate divergence conditions. - Fewer references to the Tree structure in examples, which may not have the definition close-by in context in other modules, e.g. Prelude. - Improved description of foldlM and foldrM - More detail on Tree instance construction - Misc fixes
* More truthful synopsis examplesViktor Dukhovni2021-01-091-11/+14
|
* New overview of Foldable classViktor Dukhovni2021-01-091-47/+731
| | | | Also updated stale external URL in Traversable
* Apply suggestion to libraries/base/Data/Foldable.hschessai2020-11-301-1/+1
|
* Apply suggestion to libraries/base/Data/Foldable.hschessai2020-11-301-1/+1
|
* Optimisations in Data.Foldable (T17867)chessai2020-11-301-20/+28
| | | | | | | | | | | | | This PR concerns the following functions from `Data.Foldable`: * minimum * maximum * sum * product * minimumBy * maximumBy - Default implementations of these functions now use `foldl'` or `foldMap'`. - All have been marked with INLINEABLE to make room for further optimisations.
* GHC.Core.Opt renamingSylvain Henry2020-04-181-1/+1
| | | | | | | | | | | * GHC.Core.Op => GHC.Core.Opt * GHC.Core.Opt.Simplify.Driver => GHC.Core.Opt.Driver * GHC.Core.Opt.Tidy => GHC.Core.Tidy * GHC.Core.Opt.WorkWrap.Lib => GHC.Core.Opt.WorkWrap.Utils As discussed in: * https://mail.haskell.org/pipermail/ghc-devs/2020-April/018758.html * https://gitlab.haskell.org/ghc/ghc/issues/13009#note_264650
* doc (Foldable): Add examples to Data.FoldableJulien Debon2020-04-141-3/+470
| | | | See #17929
* Annotate the non-total function in Data.Foldable as suchHécate2020-03-221-0/+20
|
* Modules: Core operations (#13009)Sylvain Henry2020-03-181-1/+1
|
* Add Monad instances to `(,,) a b` and `(,,,) a b c`Fumiaki Kinoshita2019-10-041-0/+2
|
* Typeset Big-O complexities with Tex-style notation (#16090)Sven Tennie2019-04-171-2/+2
| | | | E.g. use `\(\mathcal{O}(n^2)\)` instead of `/O(n^2)/`.
* Update Trac ticket URLs to point to GitLabRyan Scott2019-03-151-4/+4
| | | | | This moves all URL references to Trac tickets to their corresponding GitLab counterparts.
* A few typofixesGabor Greif2019-01-231-1/+1
|
* Fix typo in Foldable docsSimon Jakobi2018-12-071-1/+1
|
* Add missing since annotationsVictor Nawothnig2018-11-291-0/+18
| | | | | | | | | | | | Reviewers: hvr, bgamari, RyanGlScott Reviewed By: RyanGlScott Subscribers: RyanGlScott, rwbarton, carter GHC Trac Issues: #15930 Differential Revision: https://phabricator.haskell.org/D5379
* Add a strict version of foldMap to FoldableSimon Jakobi2018-10-151-0/+6
| | | | | | | | | | | | | | Summary: Original proposal by Andrew Martin: https://mail.haskell.org/pipermail/libraries/2018-June/028852.html Reviewers: andrewthad, hvr, bgamari, alpmestan, tdammers Reviewed By: bgamari, alpmestan, tdammers Subscribers: alpmestan, rwbarton, thomie, carter Differential Revision: https://phabricator.haskell.org/D4924
* Make sure forM_ and related functions fuse cleanlySebastian Graf2018-09-171-8/+102
| | | | | | | | | | | | | | | | | | | | | | | | | | Summary: It was revealed in #8763 that it's hard to come up with a list fusion helper for `efdtIntFB` that doesn't duplicated occurrences of `c`, which is crucial in guaranteeing that it is inlined. Not inlining `c` led to spoiled join points, in turn leading to unnecessary heap allocation. This patch tackles the problem from a different angle: Fixing all consumers instead of the less often used producer `efdtIntFB` by inserting an INLINE pragma in the appropriate places. See https://ghc.haskell.org/trac/ghc/ticket/8763#comment:76 and the new Note [List fusion and continuations in 'c']. A quick run of NoFib revealed no regression or improvements whatsoever. Reviewers: hvr, bgamari, simonpj Reviewed By: simonpj Subscribers: simonpj, rwbarton, carter GHC Trac Issues: #8763 Differential Revision: https://phabricator.haskell.org/D5131
* Fix ambiguous/out-of-scope Haddock identifiersAlec Theriault2018-08-211-2/+2
| | | | | | | | | | | | | | | | | This drastically cuts down on the number of Haddock warnings when making docs for `base`. Plus this means more actual links end up in the docs! Also fixed other small mostly markup issues in the documentation along the way. This is a docs-only change. Reviewers: hvr, bgamari, thomie Reviewed By: thomie Subscribers: thomie, rwbarton, carter Differential Revision: https://phabricator.haskell.org/D5055
* Fix example in `asum` docsSimon Jakobi2018-07-161-1/+1
|
* base: Add missing instances for Data.Ord.DownBen Gamari2018-06-191-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Specifically: * MonadFix * MonadZip * Data * Foldable * Traversable * Eq1 * Ord1 * Read1 * Show1 * Generic * Generic1 Fixes #15098. Reviewers: RyanGlScott, hvr Reviewed By: RyanGlScott Subscribers: sjakobi, rwbarton, thomie, ekmett, carter GHC Trac Issues: #15098 Differential Revision: https://phabricator.haskell.org/D4870
* base: Introduce Data.Monoid.Apchessai2018-05-271-0/+4
| | | | | This data type witnesses the lifting of a monoid into an applicative pointwise.
View Lorry Controller Status