- Libraries - Haskell.org

Re: Discussion: name for reversing fromList in Data.Sequence
by David Feuer 01 Sep '16

01 Sep '16

My concern is for what happens when such rules don't fire. If someone converts a large list to a sequence only to reverse it, then the badly-ordered sequence will end up being evacuated by the garbage collector unnecessarily, pushing up the next major collection. In contrast, I've used rewrite rules to fuse map with reverse; the worst case there is some extra churn in the nursery. That said, if others don't consider it important enough, or have enough faith that rules will fire in this case (which may very well be), I can go the rules route. On Sep 1, 2016 3:51 PM, "John Wiegley" <johnw(a)newartisans.com> wrote: >>>>> "DF" == David Feuer <david.feuer(a)gmail.com> writes: FD> I'd like to add a function DF> fromListReversing :: [a] -> Seq a Hi David, Perhaps rather than proliferating the libraries with fused compositions that are faster than their composites via (.), we could defer things like this to REWRITE rules. -- John Wiegley GPG fingerprint = 4710 CF98 AF9B 327B B80F http://newartisans.com 60E1 46C4 BD1A 7AC1 4BA2

1 1

Proposal: Add <&> to Data.Functor
by David Feuer 01 Sep '16

01 Sep '16

The <&> operator is rather popular: (<&>) :: Functor f => f a -> (a -> b) -> f b (<&>) = flip fmap Now that we have (&) in Data.Function, I think we should have (<&>) in Data.Functor.

8 7

Announcing containers 0.5.8.1
by David Feuer 31 Aug '16

31 Aug '16

There's a lot to see in this one. There are plenty of brand-new functions in Data.Map, Data.Set, and Data.Sequence, including a highly-optimized lens-inspired map alteration function and a brand-new API for merging maps efficiently. Several key map, set, and sequence functions have sped up considerably. The full change log is below. I have tried to give appropriate credit to all the non-maintainers who contributed to this release, some of whom made very major contributions indeed. If I missed anyone, please give a shout. General package changes: Remove all attempts to support nhc98 and any versions of GHC before 7.0. Integrate benchmarks with Cabal. (Thanks, Gabriel Gonzalez!) Make Cabal report required extensions properly, and stop using default extensions. Note that we do not report extensions conditionally enabled based on GHC version, as doing so would lead to a maintenance nightmare with no obvious benefits. Use BangPatterns throughout to reduce noise. This extension is now required to compile containers. Improve QuickCheck properties taking arbitrary functions by using Test.QuickCheck.Function.Fun instead of evil Show instances for functions. Expose several internal modules through Cabal (as requested by Edward Kmett). These remain completely unsupported. New exports and instances: Add alterF, restrictKeys, and withoutKeys to Data.Map and Data.IntMap. Add take, drop, splitAt, takeWhileAntitone, dropWhileAntitone, and spanAntitone for Data.Map and Data.Set. Thanks to Cale Gibbard for suggesting these. Add merge, mergeA, and associated merge tactics for Data.Map. Many thanks to Cale Gibbard, Ryan Trinkle, and Dan Doel for inspiring the merge idea and helping refine the interface. Add fromDescList, fromDescListWith, fromDescListWithKey, and fromDistinctDescList to Data.Map. Add fromDescList and fromDistinctDescList to Data.Set. Add Empty, :<|, and :|> pattern synonyms for Data.Sequence, as originally envisioned in the finger tree paper by Paterson and Hinze. Add adjust', (!?), lookup, chunksOf, cycleTaking, insertAt, deleteAt, intersperse, foldMapWithIndex, and traverseWithIndex for Data.Sequence. Derive Generic and Generic1 for Data.Tree.Tree, Data.Sequence.ViewL, and Data.Sequence.ViewR. Add foldTree for Data.Tree. (Thanks, Daniel Wagner!) Semantic changes: Make Data.Sequence.splitAt strict in its arguments. Previously, it returned a lazy pair. Fix completely erroneous definition of length for Data.Sequence.ViewR. Make Data.Map.Strict.traverseWithKey force result values before installing them in the new map. Make Data.Tree.drawTree handle newlines better. (Thanks, recursion-ninja!) Deprecations: All functions in Data.Map proper that have been documented as deprecated since version 0.5 or before now have DEPRECATED pragmas and will actually be removed after another cycle or two. Tree printing functions in Data.Map intended for library debugging are now deprecated. They will continue to be available for the foreseeable future in an internal module. Performance changes: Substantially speed up splitAt, zipWith, take, drop, fromList, partition, foldl', and foldr' for Data.Sequence. Special thanks to Lennart Spitzner for digging into the performance problems with previous versions of fromList and finding a way to make it really fast. Slightly optimize replicateA. Stop traverse from performing many unnecessary fmap operations. Most operations in Data.Sequence advertised as taking logarithmic time (including >< and adjust) now use their full allotted time to avoid potentially building up chains of thunks in the tree. In general, the only remaining operations that avoid doing more than they really need are the particular bulk creation and transformation functions that really benefit from the extra laziness. There are some situations where this change may slow programs down, but I think having more predictable and usually better performance more than makes up for that. Add rewrite rules to fuse fmap with reverse for Data.Sequence. Switch from hedge algorithms to divide-and-conquer algorithms for union, intersection, difference, and merge in both Data.Map and Data.Set. These algorithms are simpler, are known to be asymptotically optimal, and are faster according to our benchmarks. Speed up adjust for Data.Map. Allow map to inline, and define a custom (<$). This considerably improves mapping with a constant function. Remove non-essential laziness throughout the Data.Map.Lazy implementation. Slightly speed up deletion and alteration functions for Data.IntMap.

1 0

Proposal: Add `restriction` to Data.Map and Data.IntMap
by David Feuer 25 Aug '16

25 Aug '16

Cale Gibbard proposes the following: Data.IntMap.restriction :: IntSet -> IntMap a -> IntMap a Data.Map.restriction :: Ord k => Set k -> Map k a -> Map k a In each case, the map is filtered to contain only the keys that are also found in the set. This can be implemented efficiently using a slightly stripped-down version of Data.Map.intersection. David Feuer

15 27

Re: Can we deprecate the debugging functions in Data.Map?
by David Feuer 23 Aug '16

23 Aug '16

Let me revise that slightly: the valid function is also potentially useful for people using mapMonotonic and similar "unsafe" functions, so I guess that one should remain. On Aug 23, 2016 4:26 PM, "David Feuer" <david.feuer(a)gmail.com> wrote: For reasons I can't fathom, Data.Map exports the functions showTree, showTreeWith, and valid, all of which seem to be intended for debugging the map implementation. No user should ever need these abstraction-smashing functions unless they're monkeying around with mergeWithKey. If these functions are deprecated, they'll still be available from the "internal" module Data.Map.Base. Data.Map.Base will be exposed through Cabal at the request of Edward Kmett, although it will remain hidden from Haddock and completely unsupported. David

2 1

Can we deprecate the debugging functions in Data.Map?
by David Feuer 23 Aug '16

23 Aug '16

For reasons I can't fathom, Data.Map exports the functions showTree, showTreeWith, and valid, all of which seem to be intended for debugging the map implementation. No user should ever need these abstraction-smashing functions unless they're monkeying around with mergeWithKey. If these functions are deprecated, they'll still be available from the "internal" module Data.Map.Base. Data.Map.Base will be exposed through Cabal at the request of Edward Kmett, although it will remain hidden from Haddock and completely unsupported. David

3 2

Re: Proposal: Deprecate decodeUtf8
by Henning Thielemann 22 Aug '16

22 Aug '16

On Mon, 22 Aug 2016, Pavlo Kerestey wrote: > ...By the way - the Idea to have a separate WARNING for partial > functions would be really great. This way the head, and co. could be > marked and used when a quick hack or test is needed, but won't make it > into production with -Werror -Wall. This has been discussed before: https://ghc.haskell.org/trac/ghc/ticket/8064 For now I am using HLint to spot usage of typical non-total functions.

1 0

Re: Proposal: Deprecate decodeUtf8
by Henning Thielemann 22 Aug '16

22 Aug '16

On Mon, 22 Aug 2016, Pavlo Kerestey wrote: > In my opinion decodeUtf8 is an example of "there is nothing obvously > wrong" with it. I think I was lazy to copy it from StackOverflow once or > twice as a solution to `ByteString -> Text` but have not checked the > docs. I was just not careful and forgot that it is not so pure. It is pure (in the sense of purely functional), but it is not total.

1 0

Names for general merge tactics in Data.Map
by David Feuer 21 Aug '16

21 Aug '16

As I described previously, I've come up with general merge functions for Data.Map to replace the problematic mergeWithKey (which I desire to deprecate and remove). I have provisional names for the functions, and also for the "merge tactics" that go with them and their types. I would like to get whatever feedback I can before actually adding these. I'd like to try to make a release including these functions within approximately two weeks, so prompt responses will be appreciated. Note that the names of the "merge tactics" break with the tradition of offering plain functions and WithKey versions. To cut down on the already-large API, only key-passing versions will be provided (unless people object strongly). This has a small potential efficiency cost, but it cuts the API in half. The most general function is generalMergeA :: (Applicative f, Ord k) => WhenMissing f k a c -> WhenMissing f k b c -> WhenMatched f k a b c -> Map k a -> Map k b -> f (Map k c) and the pure version is generalMerge :: Ord k => SimpleWhenMissing k a c -> SimpleWhenMissing k b c -> SimpleWhenMatched k a b c -> Map k a -> Map k b -> Map k c where type SimpleWhenMissing = WhenMissing Identity type SimpleWhenMatched = WhenMatched Identity WhenMissing and WhenMatched are "merge tactics" explaining what to do with elements in various situations. WhenMissing explains what to do with keys present in one map but not the other, while WhenMatched explains what to do with keys present in both maps: WhenMissing f k x z is an abstract representation of a function of type k -> x -> f (Maybe z) WhenMatched f k x y z is an abstract representation of a function of type k -> x -> y -> f (Maybe z) So in principle, we have generalMergeA ~::~ (Applicative f, Ord k) => (k -> a -> f (Maybe c)) -> (k -> b -> f (Maybe c)) -> (k -> a -> b -> f (Maybe c)) -> Map k a -> Map k b -> f (Map k c) By using these abstract merge tactics instead of functions, we gain the ability to perform various optimizations. At present, only the WhenMissing optimizations are performed (they seem to be the most important), but we may choose to add WhenMatched optimizations in the future to enhance sharing. There are various ways to construct the merge tactics. The most general are currently called traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) -> WhenMissing f k x y and zipWithMaybeAMatched :: Applicative f => (k -> x -> y -> f (Maybe z)) -> WhenMatched f k x y z These directly convert functions into merge tactics with the corresponding types. There are various others that are simpler and/or faster. Generally, the pure tactics have the advantage of being able to process a whole subtree in a single Applicative action. Non-Maybe tactics have the advantage of skipping balance checks. dropMissing and preserveMissing are especially important because they can skip over whole subtrees, either pruning them or leaving them alone. Pure: dropMissing :: Applicative f => WhenMissing f k x y -- dropMissing :: SimpleWhenMissing k x y preserveMissing :: Applicative f => WhenMissing f k x x -- preserveMissing :: SimpleWhenMissing k x x mapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k x y -- mapMaybeMissing :: (k -> x -> Maybe y) -> SimpleWhenMissing k x y mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y -- mapMissing :: (k -> x -> y) -> SimpleWhenMissing k x y filterMissing :: Applicative f => (k -> x -> Bool) -> WhenMissing f k x x -- filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing k x x zipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) -> WhenMatched f k x y z -- zipWithMaybeMatched :: (k -> x -> y -> Maybe z) -> SimpleWhenMatched k x y z zipWithMatched :: Applicative f => (k -> x -> y -> z) -> WhenMatched f k x y z -- zipWithMatched :: (k -> x -> y -> z) -> SimpleWhenMatched k x y z Applicative: traverseMissing :: Applicative f => (k -> x -> f y) -> WhenMissing f k x y filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x x zipWithAMatched :: Applicative f => (k -> x -> y -> f z) -> WhenMatched f k x y z Thanks, David Feuer

4 11

Proposal: Deprecate decodeUtf8
by Niklas Hambüchen 20 Aug '16

20 Aug '16

I propose to add a deprecation pragma to the partial function Data.Text.decodeUtf8. I see checks or decoding failure accidentally omitted from production code every week. I claim decodeUtf8 to be *the* most abused partial function in the current Haskell ecosystem (with `head` and `tail` at least everybody knows they should feel bad when typing them down). decodeUtf8' with custom error message is a better solution in all cases I have seen and can come up with. I therefore propose: * Add deprecation pragma to decodeUtf8 * Do it with Text.Lazy and *16/*32 functions too * But keep them indefinitely (we don't want to break compiles) I believe that deprecating decodeUtf8 will result in lots of useful warnings across the world every day and less software crashing at runtime. Discussion period 2 months. Thanks!

12 18