February 2018 - Libraries

Proposal: Remove Semigroup and Monoid instances for Data.Map, Data.IntMap, Data.HashMap
by David Feuer 17 Feb '18

17 Feb '18

Many people have recognized for years that the Semigroup and Monoid instances for Data.Map, Data.IntMap, and Data.HashMap are not so great. In particular, when the same key is present in both maps, they simply use the value from the first argument, ignoring the other one. This somewhat counter-intuitive behavior can lead to bugs. See, for example, the discussion in Tim Humphries's blog post[*]. I would like do do the following: 1. Deprecate the Semigroup and Monoid instances for Data.Map.Map, Data.IntMap.IntMap, and Data.HashMap.HashMap in the next releases of containers and unordered-containers. 2. Remove the deprecated instances. 3. After another several years (four or five, perhaps?), make a major release of each package in which the instances are replaced with the following: instance (Ord k, Semigroup v) => Semigroup (Map k v) where (<>) = Data.Map.Strict.unionWith (<>) instance (Ord k, Semigroup v) => Monoid (Map k v) where mempty = Data.Map.Strict.empty instance Semigroup v => Semigroup (IntMap v) where (<>) = Data.IntMap.Strict.unionWith (<>) instance Semigroup v => Monoid (IntMap v) where mempty = Data.IntMap.Strict.empty instance (Eq k, Hashable k, Semigroup v) => Semigroup (HashMap k v) where (<>) = Data.HashMap.Strict.unionWith (<>) instance (Eq k, Hashable k, Semigroup v) => Monoid(HashMap k v) where mempty = Data.HashMap.Strict.empty Why do I want the strict versions? That choice may seem a bit surprising, since the data structures are lazy. But the lazy versions really like to leak memory, making them unsuitable for most practical purposes. The big risk: Someone using old code or old tutorial documentation could get subtly wrong behavior without noticing. That is why I have specified an extended period between removing the current instances and adding the desired ones. Alternatives: 1. Remove the instances but don't add the new ones. I fear this may lead others to write their own orphan instances, which may not even all do the same thing. 2. Write separate modules with newtype-wrapped versions of the data structures implementing the desired instances. Unfortunately, this would be annoying to maintain, and also annoying to use--packages using the unwrapped and wrapped versions will use different types. Manually wrapping and unwrapping to make the different types work with each other will introduce lots of potential for mistakes and confusion. Discussion period: three weeks. [*] http://teh.id.au/posts/2017/03/03/map-merge/index.html

19 33

Proposal: Make size (from 'unordered-containers') run in constant time
by Alexandre Rodrigues 17 Feb '18

17 Feb '18

Greetings; This email's purpose is to request comments from this mailing list regarding a PR to ‘unordered-containers’ (here: https://github.com/tibbe/unordered-containers/pull/170) This PR modifies the existing code so that ‘size’ can calculate the size of a ‘Hash{Map, Set}’ in constant time instead of linear, which is its current performance. To avoid making this message too large, the benchmarking results are not included here, but you may find them in the PR’s discussion. In short, a penalty of about 10% to functions in the library may be expected, and both ‘filterWithKey’ and ‘fromListWith’ are much slower, which is an issue I’d like to solve. If this PR is mediocre, if you have any suggestions to make it better, or any other comment, please reply to this email. I'd like to thank David Feuer and Niklas Hambüchen for the many improvements suggested to this PR, and Johan Tibell for writing an excellent library.

1 0

Disabling deprecated functions
by David Feuer 14 Feb '18

14 Feb '18

The time has come to remove some deprecated functions from containers. As many know, lots of people ignore deprecation warnings. That means there are probably plenty of people still using the deprecated functions. Right now, the functions work, and give deprecation warnings telling users what alternatives to use. If I simply remove the functions, users will suddenly have to *actually* do something to fix their code, but they *won't* be given any useful information about how to do it. Ideally, GHC would add a REMOVED pragma, but I don't see any sign that that's happening. Pondering that conundrum today, I came up with something that seems to *mostly* solve the problem: -- We need this class to defer the type error to the call site, rather -- than getting it at the definition site. I think it basically takes advantage -- of the delayed resolution GHC uses to support overlapping instances, -- which is kind of gross. class Error (e :: ErrorMessage) instance TypeError e => Error e insertWith' :: Error ('Text "Data.IntMap.insertWith' is gone. Use Data.IntMap.Strict.insertWith.") => (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a insertWith' _ _ _ _ = undefined Now if someone is still using Data.IntMap.insertWith', they'll get an error message, but a useful one. Great! But there are two downsides: 1. An unqualified, unrestricted import of the module will still use up a perfectly good name for as long as the export is still there. 2. User-defined type errors have only existed since GHC 8.0. So for earlier versions, I'd probably need to just remove the functions, in which case the exports depend on the GHC version, which is unfortunate. In these *particular* cases, I suspect the benefits of this hack outweigh the downsides, because unqualified and unrestricted imports of Data.Map and Data.IntMap are fairly rare. What are others' thoughts on the matter? David

1 1

Re: Proposal: Remove Semigroup and Monoid instances for Data.Map, Data.IntMap, Data.HashMap
by Daniel Cartwright 13 Feb '18

13 Feb '18

I am strongly in favour of this as well. I do not like the newtype approach, I think backwards-*incompatibility* with four to five year-old (or two to three year-old) code is OK. On Tue, Feb 13, 2018 at 3:04 PM, Daniel Cartwright <chessai1996(a)gmail.com> wrote: > I am strongly in favour of this as well. I do not like the newtype > approach, I think backwards-*incompatibility* with four to five year-old > (or two to three year-old) code is OK. > > On Tue, Feb 13, 2018 at 2:59 PM, David Feuer <david.feuer(a)gmail.com> > wrote: > >> I don't think the old proposal was really the right way. >> >> On Tue, Feb 13, 2018 at 2:54 PM, Mario Blažević <mblazevic(a)stilo.com> >> wrote: >> > +1. But whatever happened to your proposal from last May? I don't think >> > there were any objections to it. Would the two proposals be combined, or >> > have you decided to drop the previous one? >> > >> > https://mail.haskell.org/pipermail/libraries/2017-May/028036.html >> > >> > On 2017-05-25 12:55 PM, David Feuer wrote: >> >> A lot of people have wrappers around Data.Map and Data.IntMap to give >> >> them more useful (Semigroup and) Monoid instances. I'd like to add such >> >> wrappers to containers. What we need to be able to do that are *names* >> >> for the new modules. I can't think of any, so I'm reaching out to the >> >> list. Please suggest names! Another question is whether we should take >> >> the opportunity of new modules to modernize and streamline the API a >> >> bit. I'd like, at least, to separate "safe" from "unsafe" functions, >> >> putting the unsafe ones in .Unsafe modules. >> > >> > >> > >> > On 2018-02-13 02:33 PM, David Feuer wrote: >> >> >> >> Many people have recognized for years that the Semigroup and Monoid >> >> instances for Data.Map, Data.IntMap, and Data.HashMap are not so >> >> great. In particular, when the same key is present in both maps, they >> >> simply use the value from the first argument, ignoring the other one. >> >> This somewhat counter-intuitive behavior can lead to bugs. See, for >> >> example, the discussion in Tim Humphries's blog post[*]. I would like >> >> do do the following: >> >> >> >> 1. Deprecate the Semigroup and Monoid instances for Data.Map.Map, >> >> Data.IntMap.IntMap, and Data.HashMap.HashMap in the next releases of >> >> containers and unordered-containers. >> >> >> >> 2. Remove the deprecated instances. >> >> >> >> 3. After another several years (four or five, perhaps?), make a major >> >> release of each package in which the instances are replaced with the >> >> following: >> >> >> >> instance (Ord k, Semigroup v) => Semigroup (Map k v) where >> >> (<>) = Data.Map.Strict.unionWith (<>) >> >> instance (Ord k, Semigroup v) => Monoid (Map k v) where >> >> mempty = Data.Map.Strict.empty >> >> >> >> instance Semigroup v => Semigroup (IntMap v) where >> >> (<>) = Data.IntMap.Strict.unionWith (<>) >> >> instance Semigroup v => Monoid (IntMap v) where >> >> mempty = Data.IntMap.Strict.empty >> >> >> >> instance (Eq k, Hashable k, Semigroup v) => Semigroup (HashMap k v) >> >> where >> >> (<>) = Data.HashMap.Strict.unionWith (<>) >> >> instance (Eq k, Hashable k, Semigroup v) => Monoid(HashMap k v) >> where >> >> mempty = Data.HashMap.Strict.empty >> >> >> >> Why do I want the strict versions? That choice may seem a bit >> >> surprising, since the data structures are lazy. But the lazy versions >> >> really like to leak memory, making them unsuitable for most practical >> >> purposes. >> >> >> >> The big risk: >> >> >> >> Someone using old code or old tutorial documentation could get subtly >> >> wrong behavior without noticing. That is why I have specified an >> >> extended period between removing the current instances and adding the >> >> desired ones. >> >> >> >> Alternatives: >> >> >> >> 1. Remove the instances but don't add the new ones. I fear this may >> >> lead others to write their own orphan instances, which may not even >> >> all do the same thing. >> >> >> >> 2. Write separate modules with newtype-wrapped versions of the data >> >> structures implementing the desired instances. Unfortunately, this >> >> would be annoying to maintain, and also annoying to use--packages >> >> using the unwrapped and wrapped versions will use different types. >> >> Manually wrapping and unwrapping to make the different types work with >> >> each other will introduce lots of potential for mistakes and >> >> confusion. >> >> >> >> Discussion period: three weeks. >> >> >> >> [*] http://teh.id.au/posts/2017/03/03/map-merge/index.html >> >> _______________________________________________ >> >> Libraries mailing list >> >> Libraries(a)haskell.org >> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >> >> >> > >> > _______________________________________________ >> > Libraries mailing list >> > Libraries(a)haskell.org >> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >> _______________________________________________ >> Libraries mailing list >> Libraries(a)haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >> > >

3 2

Proposal: Debug.Trace.traceWith
by Kris Nuttycombe 10 Feb '18

10 Feb '18

When using Debug.Trace for debugging, a very common operation is to prefer to trace only some subset or function of an intermediate result. As a consequence, I propose adding the following function to Debug.Trace: traceWith :: (Show b) => (a -> b) -> a -> a traceWith f a = trace (show $ f a) a While it's trivial to define, I have found this to be one of the most useful functions in my trace-based debugging toolkit, hence my proposal that it be added to base. It generalizes `traceShowId` in a meaningful and useful fashion. As this is the first such proposal I've put forth, please let me know if I'm doing anything wrong with it! Thanks, Kris Nuttycombe

5 8

Proposal: accum and accumArray strictness
by David Feuer 09 Feb '18

09 Feb '18

The documentation for accumArray is currently broken [*]. According to the documentation: According to the documentation, > If the accumulating function is strict, then 'accumArray' is strict in > the values, as well as the indices, in the association list. Thus, > unlike ordinary arrays built with 'array', accumulated arrays should > not in general be recursive. I believe that purported strictness is desirable, because it prevents thunks from accumulating when we use the passed function. But the strictness *isn't really there*. accumArray never forces any values whatsoever! The same is true of accum, but that function does not document its strictness. I propose that we change both the implementation and documentation. For accumArray, I think we should say that the resulting array is strict in the initial value and in each result of applying the accumulating function, and indicate that each element of the resulting array will be in WHNF. For accum, I think we should say that the resulting array is strict in each value in the initial array and in each result of applying the accumulating function, and indicate that each element of the resulting array will be in WHNF. We thereby guarantee that we can accumulate strictly, which is important for performance, and I think being strict in the initial value(s) makes for simpler reasoning than only being strict in the results of the combining function. [*] https://ghc.haskell.org/trac/ghc/ticket/14785 David Feuer

1 1

Formal verification of containers
by Joachim Breitner 08 Feb '18

08 Feb '18

Hi containers maintainers, you might have already read it between the lines, but some people here at Penn are currently using hs-to-coq to translate the containers library to Coq and verify it. We just reached a milestone by verifying a portion of Data.IntSet large enough to instantiate Coq’s FSetInterface: https://github.com/antalsz/hs-to-coq/blob/master/examples/containers/theori… There is work on verifying Data.Set as well: https://github.com/antalsz/hs-to-coq/blob/master/examples/containers/theori… Isn’t that exciting? It raises the question whether there is value in integrating these proofs in some way into the development process of containers. One could imagine adding a job to travis that translates container’s master into Coq and checks if the proofs go through. On the one hand, that’s of course great, because it’d make containers one of the most thoroughly verified pieces of Haskell in use out there. On the other hand, we’d have to choose the least bad of a bunch of bad options when it comes to future contributions (I am listing unfeasible options as well): - we essentially freeze the code - we’d lose the verification again quickly, once someone makes a non- trivial change to the code - we’d have to restrict contributions to those who are able to update the proofs - we’d still welcome contributions that break the proofs, but let them sit in pull requests until someone updates the proofs on the PR and then merge - (maybe a bit far fetched, but who knows) we get funding to pay someone to keep the proofs in sync, without slowing down other contributions I honestly don’t know which of these are the most viable, or if none of them make any sense and we should not hook up the verification with container’s development. What do you think? Cheers, Joachim -- Joachim Breitner mail(a)joachim-breitner.de http://www.joachim-breitner.de/

5 13

Preventing double-free error with `stablePtr`
by Gershom B 06 Feb '18

06 Feb '18

I was just reading Roman Cheplyaka’s very interesting blog-post here: https://ro-che.info/articles/2018-02-03-stableptr-undefined-behavior. As he points out, the docs for `freeStablePtr` say "if the stable pointer is passed to deRefStablePtr or freeStablePtr, the behaviour is undefined.” And indeed we can observe weird behavior as a result of sucn an error. A deRef of a stable pointer is arguably the sort of sharp-edge we know how to code to avoid. But a double free is a bit trickier. Would it be worth adding a bit more overhead to make such an operation idempotent? Additionally, would it be worthwhile to add `withStablePtr` to the `Foreign.StablePtr` module? I imagine there are cases that it won’t cover, but it would at least encourage good discipline in the cases that it does handle. The evident utility of such a function is witnessed by its existence in a few different codebases, not least the Win32 library ( https://hackage.haskell.org/package/Win32-2.6.2.0/docs/System-Win32-Types.h… ) Cheers, Gershom

4 3

generalize type of Data.Set.unions from List to Foldable
by Johannes Waldmann 05 Feb '18

05 Feb '18

Dear Libraries, I propose this change for containers: have: unions :: [ Set a ] -> Set a want: unions :: Foldable f => f (Set a) -> Set a and similar for unions in IntSet, Map, IntMap. Since this affects the public API, contributor guidelines require to go through this mailing list. See https://github.com/haskell/containers/issues/520 NB: the only other places in Data.Set (etc.) where a list occurs in an argument position are the from*List[With] functions. - J.W.

7 13

Removing bitSize
by David Feuer 04 Feb '18

04 Feb '18

The long-deprecated bitSize method of the Bits class is slated to be removed in base-4.11 (GHC 8.4). There is one remaining question: should we replace it with a *function* by that name with a FiniteBits constraint? I don't feel very strongly either way, but Ryan Scott seems in favor and Edward Kmett seems opposed. So it seems best to bring it to the libraries list and let the CLC make the call. If the function is added, it would look like this: bitSize :: FiniteBits a => a -> Int bitSize = finiteBitSize The biggest downside I see is that we might one day want to reuse the name for something with a better type, such as bitSize :: forall proxy a. FiniteBits a => proxy a -> Int bitSize _ = finiteBitSize (undefined :: a) or bitSize :: forall a. FiniteBits a => Tagged a Int bitSize = Tagged (finiteBitSize (undefined :: a)) or (with type applications) bitSize :: forall a. FiniteBits a => Int bitSize = finiteBitSize (undefined :: a) Thanks, David Feuer

5 5