- Libraries - Haskell.org

Request (and self-nomination) for maintainers: monoidal-containers
by Fumiaki Kinoshita 14 Jun '21

14 Jun '21

There has been little response to the issues and PRs lately[0] so I request for an additional maintainership. I'm willing to do it unless anyone else steps forward. Apparently @ali-abrar is the current maintainer so I CC'd him. [0] https://github.com/bgamari/monoidal-containers

2 3

Re: [Haskell-cafe] Optimizing Eq instances with reallyUnsafePtrEquality#
by David Feuer 11 Jun '21

11 Jun '21

As far as I'm concerned, nonreflexive instances are not supported by `containers` at all. If your == isn't reflexive, you just need to assume that anything with an Eq constraint might behave arbitrarily badly. On Fri, Jun 11, 2021, 10:27 AM Simon Jakobi via Haskell-Cafe < haskell-cafe(a)haskell.org> wrote: > Thanks for the feedback everyone! :) > > The gist I get is that using pointer equality is not free, but it can > make sense when > > 1. two objects are particularly likely to be the same; > 2. establishing equality by other means (e.g. structural equality) is > particularly expensive > > The usecases I now have in mind are: > > * Lookups in unordered-containers: Since keys are only ==-d when their > hashes are equal, it seems that the likelihood that they are in fact > the same object should be fairly good. I think we can ignore the issue > of irreflexive instances here, because the lookup logic already > requires reflexivity. > > * The Eq instances of containers' Set and IntSet types and of HashSet > from unordered-containers. These instances seem particularly > expensive, and Set and HashSet already require reflexivity. I don't > think we can apply the same optimizations to the Eq instances of the > various Map types, because we might run into irreflexive values there. > > * Eq for lazy ByteStrings – another expensive instance. The instance > for strict ByteStrings already makes use of pointer equality. > > Cheers, > Simon > > > > > > > > > Am Di., 8. Juni 2021 um 18:51 Uhr schrieb Sebastiaan Joosten > <sjcjoosten+haskell(a)gmail.com>: > > > > The containers library uses this trick: > > > https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0d… > > It mentions the useful hint to evaluate the arguments to WHNF before > calling PtrEquality. > > The function ptrEq is used here (for instance): > > > https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0d… > > The places where ptrEq is used in that file, its purpose seems to be to > reduce memory by reusing existing data-structures, which I suppose also > helps with performance. > > Surprisingly enough (at least to me) ptrEq is not used in the Eq > instance there: > > > https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0d… > > > > Outside of GHC, there are some (pure) languages that extensively make > use of this principle and it's too cool not to mention: > > The programming language Elm does this in its generated code (at least > when generating JavaScript): https://github.com/elm/compiler/ > > The theorem proving environment ACL2 uses this principle for memoizing > functions, fast 'Map's ('dictionaries' in python lingo, 'alist' or > association-list in ACL2 lingo), as well as fast equality. As a LISP > dialect, all data-structures are pairs (called CONS). In ACL2, the function > 'HONS' (hashed CONS) will construct a pair if it does not already exist, > and otherwise it returns a pointer to the already existing object. The > point of using HONS in ACL2 is to only perform pointer comparison, without > needing to do any other equality check. > > General background information: > https://www.cs.utexas.edu/~ragerdl/acl2-manual/index.html?topic=ACL2____HON… > > The equality test: > https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo… > > And there is of course a function to create a 'normed object': > https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo… > > Note that the ACL2 approach only works because it is supported by the > run time system (the implementation needs to access 'all data in memory') > so it won't work in Haskell (assuming you're not writing your own RTS). > > > > Hope this helps. > > > > On Tue, Jun 8, 2021 at 10:47 AM Joachim Durchholz <jo(a)durchholz.org> > wrote: > >> > >> Am 08.06.21 um 16:25 schrieb Simon Jakobi via Haskell-Cafe: > >> > Hi everyone! > >> > > >> > In > https://github.com/haskell-unordered-containers/unordered-containers/issues… > >> > we're wondering whether certain Eq instances, for example record types > >> > or strings, could be optimized by including a pointer equality check > >> > that detects when an object is compared with itself. > >> > >> You have to be aware that the pointer comparison itself does not come > >> for free. Execution prediction means that the "happy path" may be so > >> rare it's not loaded into the CPU cache and you might end with a slower > >> system - the case is somewhat pathological but not so rare that you can > >> just assume that it will not happen to you. > >> A lot also depends on whether the data to be compared needs to be loaded > >> anyway. If yes, the pointer comparison won't give you any gains, it will > >> be just one instruction more to execute, creating more execution unit > >> contention inside the CPU. If no, then obviously the pointer comparison > >> will help. > >> > >> In the end, you need to benchmark to see if it helps you. > >> And you cannot usefully benchmark unless you have also nailed down all > >> performance-relevant compiler and runtime options, which you do only if > >> you have exhausted all other optimization possibilities. > >> > >> IOW if it complicates your code, don't do it - unless you are already > >> long past the point where code reusability has taken a back seat to raw > >> optimization. > >> > >> Regards, > >> Jo > >> _______________________________________________ > >> Haskell-Cafe mailing list > >> To (un)subscribe, modify options or view archives go to: > >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > >> Only members subscribed via the mailman list are allowed to post. > > > > _______________________________________________ > > Haskell-Cafe mailing list > > To (un)subscribe, modify options or view archives go to: > > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > > Only members subscribed via the mailman list are allowed to post. > _______________________________________________ > Haskell-Cafe mailing list > To (un)subscribe, modify options or view archives go to: > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > Only members subscribed via the mailman list are allowed to post.

2 1

Re: [Haskell-cafe] Optimizing Eq instances with reallyUnsafePtrEquality#
by Simon Jakobi 11 Jun '21

11 Jun '21

(CC'ing the libraries list again) Am Fr., 11. Juni 2021 um 16:26 Uhr schrieb Simon Jakobi <simon.jakobi(a)googlemail.com>: > > Thanks for the feedback everyone! :) > > The gist I get is that using pointer equality is not free, but it can > make sense when > > 1. two objects are particularly likely to be the same; > 2. establishing equality by other means (e.g. structural equality) is > particularly expensive > > The usecases I now have in mind are: > > * Lookups in unordered-containers: Since keys are only ==-d when their > hashes are equal, it seems that the likelihood that they are in fact > the same object should be fairly good. I think we can ignore the issue > of irreflexive instances here, because the lookup logic already > requires reflexivity. > > * The Eq instances of containers' Set and IntSet types and of HashSet > from unordered-containers. These instances seem particularly > expensive, and Set and HashSet already require reflexivity. I don't > think we can apply the same optimizations to the Eq instances of the > various Map types, because we might run into irreflexive values there. > > * Eq for lazy ByteStrings – another expensive instance. The instance > for strict ByteStrings already makes use of pointer equality. > > Cheers, > Simon > > > > > > > > > Am Di., 8. Juni 2021 um 18:51 Uhr schrieb Sebastiaan Joosten > <sjcjoosten+haskell(a)gmail.com>: > > > > The containers library uses this trick: > > https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0d… > > It mentions the useful hint to evaluate the arguments to WHNF before calling PtrEquality. > > The function ptrEq is used here (for instance): > > https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0d… > > The places where ptrEq is used in that file, its purpose seems to be to reduce memory by reusing existing data-structures, which I suppose also helps with performance. > > Surprisingly enough (at least to me) ptrEq is not used in the Eq instance there: > > https://github.com/haskell/containers/blob/30ccbaa201043109bf1ee905c66ccd0d… > > > > Outside of GHC, there are some (pure) languages that extensively make use of this principle and it's too cool not to mention: > > The programming language Elm does this in its generated code (at least when generating JavaScript): https://github.com/elm/compiler/ > > The theorem proving environment ACL2 uses this principle for memoizing functions, fast 'Map's ('dictionaries' in python lingo, 'alist' or association-list in ACL2 lingo), as well as fast equality. As a LISP dialect, all data-structures are pairs (called CONS). In ACL2, the function 'HONS' (hashed CONS) will construct a pair if it does not already exist, and otherwise it returns a pointer to the already existing object. The point of using HONS in ACL2 is to only perform pointer comparison, without needing to do any other equality check. > > General background information: https://www.cs.utexas.edu/~ragerdl/acl2-manual/index.html?topic=ACL2____HON… > > The equality test: https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo… > > And there is of course a function to create a 'normed object': https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/index-seo… > > Note that the ACL2 approach only works because it is supported by the run time system (the implementation needs to access 'all data in memory') so it won't work in Haskell (assuming you're not writing your own RTS). > > > > Hope this helps. > > > > On Tue, Jun 8, 2021 at 10:47 AM Joachim Durchholz <jo(a)durchholz.org> wrote: > >> > >> Am 08.06.21 um 16:25 schrieb Simon Jakobi via Haskell-Cafe: > >> > Hi everyone! > >> > > >> > In https://github.com/haskell-unordered-containers/unordered-containers/issues… > >> > we're wondering whether certain Eq instances, for example record types > >> > or strings, could be optimized by including a pointer equality check > >> > that detects when an object is compared with itself. > >> > >> You have to be aware that the pointer comparison itself does not come > >> for free. Execution prediction means that the "happy path" may be so > >> rare it's not loaded into the CPU cache and you might end with a slower > >> system - the case is somewhat pathological but not so rare that you can > >> just assume that it will not happen to you. > >> A lot also depends on whether the data to be compared needs to be loaded > >> anyway. If yes, the pointer comparison won't give you any gains, it will > >> be just one instruction more to execute, creating more execution unit > >> contention inside the CPU. If no, then obviously the pointer comparison > >> will help. > >> > >> In the end, you need to benchmark to see if it helps you. > >> And you cannot usefully benchmark unless you have also nailed down all > >> performance-relevant compiler and runtime options, which you do only if > >> you have exhausted all other optimization possibilities. > >> > >> IOW if it complicates your code, don't do it - unless you are already > >> long past the point where code reusability has taken a back seat to raw > >> optimization. > >> > >> Regards, > >> Jo > >> _______________________________________________ > >> Haskell-Cafe mailing list > >> To (un)subscribe, modify options or view archives go to: > >> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > >> Only members subscribed via the mailman list are allowed to post. > > > > _______________________________________________ > > Haskell-Cafe mailing list > > To (un)subscribe, modify options or view archives go to: > > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > > Only members subscribed via the mailman list are allowed to post.

1 0

Who is responsible for Mtl?
by Carter Schonwald 10 Jun '21

10 Jun '21

I thought several folks had stepped up to do release maintainership, but perhaps life and other stuff has intervened? There’s definitely stuff that it’s lagging behind transformers on, and if the adhoc policies made over the course of 2020 are supposed to be normative, perhaps a dialogue about who has the time, sensibilities and taste to give mtl the love it needs should be had. The last release was in 2018 and I suspect ultimately the folks who had intended to give it care over the past year have been busy with other commitments (very valid). But it’s such a pervasively important package that needs to stay coordinated with transformers and soemtimes base that it needs an active caring hand who has time for it. To be clear, I don’t want to. But I think this is worth actually discussing.

2 1

Optimizing Eq instances with reallyUnsafePtrEquality#
by Simon Jakobi 08 Jun '21

08 Jun '21

Hi everyone! In https://github.com/haskell-unordered-containers/unordered-containers/issues… we're wondering whether certain Eq instances, for example record types or strings, could be optimized by including a pointer equality check that detects when an object is compared with itself. Does anyone here have experience with such an optimization? Has this been considered before, for example in GHC's deriving machinery? One complication seems to be the correct handling of fields with irreflexive instances, for example Float and Double. In such a case, pointer equality doesn't imply "==-equality". I'm looking forward to hearing your thoughts on this! :) Cheers, Simon

1 0

Give MonadTrans a QuantifiedConstraints superclass
by Baldur Blöndal 06 Jun '21

06 Jun '21

This is to advertise the proposal (https://gitlab.haskell.org/ghc/ghc/-/issues/19922) to add a superclass to the MonadTrans type class in Control.Monad.Trans. A Monad transformer 'trans' lifts a 'Monad m' to a 'Monad (trans m)'. This proposal code-ifies that with a superclass constraint: class (forall m. Monad m => Monad (trans m)) => MonadTrans trans where .. This is the main motiviating example of the Quantified Class Constraints paper https://gkaracha.github.io/papers/quantcs.pdf

8 13

Data.Traversable documentation MR 5873
by Viktor Dukhovni 02 Jun '21

02 Jun '21

I hope it is acceptable on this list to solicit feedback on a documentation MR for the base library, specifically the Data.Traversable module: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5873 The rewrite touches a lot of text, and so most of you are likely to not find time for the full review that it perhaps deserves. But I hope that one or two of you would be inclined to give it a go. In addition to the specifics of the exposition, both in Data.Traversable, and in Data.Foldable I'm opting for a somewhat new layout of the module documentation, with just a brief blurb at the top, then all the function synopses, and only after all that the detailed prose and laws, which were historically at the top of each module's documentation. I think the "prose last" format is more suitable for the typical user who wants to quickly glance at the documentation of a single function, or see what functions are in the module. The detailed exposition is for those who want to take the time to be introduced to the relevant concepts. Section headings and links make it possible to navigate to the overview if one is instead interested in the introductory prose. I hope this format is a step in the right direction, or if not, this is a good opportunity to correct the document structure. Lastly, a comment in the MR asks whether it would be a good idea to tweak the definitions of mapAccumL and mapAccumR to "amp up" the use of coercions in the hope of a performance payoff. See proposed patch below... -- Viktor. diff --git a/libraries/base/Data/Traversable.hs b/libraries/base/Data/Traversable.hs index db7e548325..6871e411a0 100644 --- a/libraries/base/Data/Traversable.hs +++ b/libraries/base/Data/Traversable.hs @@ -432,8 +432,10 @@ forM = flip mapM -- >>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5] -- ("012345",["0","01","012","0123","01234"]) -- -mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) -mapAccumL f s t = runStateL (traverse (StateL . flip f) t) s +type TraverseL t s a b = (a -> StateL s b) -> t a -> StateL s (t b) +mapAccumL :: forall t s a b. Traversable t + => (s -> a -> (s, b)) -> s -> t a -> (s, t b) +mapAccumL f s t = coerce (traverse :: TraverseL t s a b) (flip f) t s -- |The 'mapAccumR' function behaves like a combination of 'fmap' -- and 'Data.Foldable.foldr'; it applies a function to each element of a structure, @@ -450,8 +452,10 @@ mapAccumL f s t = runStateL (traverse (StateL . flip f) t) s -- >>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5] -- ("054321",["05432","0543","054","05","0"]) -- -mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) -mapAccumR f s t = runStateR (traverse (StateR . flip f) t) s +type TraverseR t s a b = (a -> StateR s b) -> t a -> StateR s (t b) +mapAccumR :: forall t s a b. Traversable t + => (s -> a -> (s, b)) -> s -> t a -> (s, t b) +mapAccumR f s t = coerce (traverse :: TraverseR t s a b) (flip f) t s -- | This function may be used as a value for `fmap` in a `Functor` -- instance, provided that 'traverse' is defined. (Using

2 1

Give MonadTrans a QuantifiedConstraints superclass
by Baldur Blöndal 02 Jun '21

02 Jun '21

This is to advertise the proposal (https://gitlab.haskell.org/ghc/ghc/-/issues/19922) to add a superclass to the MonadTrans type class in Control.Monad.Trans. A Monad transformer 'trans' lifts a 'Monad m' to a 'Monad (trans m)'. This proposal code-ifies that with a superclass constraint: class (forall m. Monad m => Monad (trans m)) => MonadTrans trans where .. This is the main motiviating example of the Quantified Class Constraints paper https://gkaracha.github.io/papers/quantcs.pdf Without it composition (·) as described in the paper can't be defined. Uses include deriving MonadTrans via the composition of two MonadTransformers: type Ok :: MonadTransformer newtype Ok m a = Ok (Int -> Int -> m a) deriving (Functor, Applicative, Monad) via (ReaderT Int · ReaderT Int) m :: Type -> Type deriving MonadTrans via ReaderT Int · ReaderT Int :: MonadTransformer

1 0

Proposal: Determining whether a Bits instance is FiniteBits
by Zemyla 28 May '21

28 May '21

Every Bits instance has to know that whether it's a FiniteBits instance as well, due to bitSizeMaybe. Therefore, it should also be able to tell a program that it is in fact a FiniteBits instance. There should be a function added to Data.Bits.Bits: withFiniteBits :: Bits a => a -> (FiniteBits a => r) -> r -> r The default should be withFiniteBits _ _ x = x, at least for the next several versions. bitSizeMaybe can be defined as bitSizeMaybe x = withFiniteBits x (Just (finiteBitSize x)) Nothing once everyone is on board with properly defining the value.

4 6

Re: Enum and bounded instances for (,) and Either
by Carter Schonwald 27 May '21

27 May '21

This raises a good point: enum as it currently exists is pretty bad and not well behaved ! On Sat, May 15, 2021 at 10:54 AM Zemyla <zemyla(a)gmail.com> wrote: > We can't write instances of Enum for (,) and Either until we have total > versions of pred and succ. > > On Wed, May 12, 2021, 20:11 Carter Schonwald <carter.schonwald(a)gmail.com> > wrote: > >> *while we could >> >> Perhaps we should provide these flavors via new types and thus folks >> could still benefit from these instances by way of deriving via ? >> >> On Wed, May 12, 2021 at 6:38 PM Carter Schonwald < >> carter.schonwald(a)gmail.com> wrote: >> >>> isnt there also the issue that while we good provide newtypes for >>> various choices of product of enum instance => enum of products, there >>> literally quite easily 3 valid instances we could concoct (and many more >>> besides) >>> >>> "row by row" >>> "column by column" >>> "diagonalization" >>> etc? >>> that is: each of these is just as valid? >>> >>> On Wed, May 12, 2021 at 5:46 PM Edward Kmett <ekmett(a)gmail.com> wrote: >>> >>>> Nothing indicates that minBound is >= 0. >>>> >>>> So if you want to deal with a modulus properly you need to deal with a >>>> modulus of something like maxBound - minBound + 1 (after appropriately >>>> upcasting intermediate results to a large enough type to contain that >>>> range). >>>> >>>> You also run into range issues pretty early on, and then scenarios like >>>> the instances for Float that are even wonkier. >>>> >>>> If toEnum/fromEnum went to a larger type (Integer or Natural) and we >>>> didn't have the wonkier Float instances and the like this would be a much >>>> easier sell. As it is I find myself rather uncomfortable with the shakiness >>>> of the foundations this thing rests upon. >>>> >>>> Sent from my iPhone >>>> >>>> On May 12, 2021, at 10:53 AM, Sandy Maguire <sandy(a)sandymaguire.me> >>>> wrote: >>>> >>>> >>>> Hi all, >>>> >>>> Found myself puzzled the other day when I wanted an (Enum a, Enum b) >>>> => Enum (a, b) instance, and was distraught that it didn't exist. >>>> >>>> The following is a reasonable implementation: >>>> >>>> >>>> instance (Bounded b, Enum a, Enum b) => Enum (a, b) where >>>> fromEnum (a, b) = (fromEnum (maxBound @b) + 1) * fromEnum a + >>>> fromEnum b >>>> toEnum n = >>>> let bound = fromEnum (maxBound @b) + 1 >>>> b = n `rem` bound >>>> a = n `div` bound >>>> in (toEnum a, toEnum b) >>>> >>>> And, while we're at it, might as well add canonical instances for >>>> Either: >>>> >>>> >>>> instance (Bounded a, Bounded b) => Bounded (Either a b) where >>>> minBound = Left minBound >>>> maxBound = Right maxBound >>>> >>>> instance (Bounded a, Enum a, Enum b) => Enum (Either a b) where >>>> toEnum i = >>>> let bound = fromEnum (maxBound @a) + 1 >>>> in case i < bound of >>>> True -> Left $ toEnum i >>>> False -> Right $ toEnum $ i - bound >>>> fromEnum (Left a) = fromEnum a >>>> fromEnum (Right b) = fromEnum b + fromEnum (maxBound @a) + 1 >>>> >>>> Are there any reasons these instances are missing from base? >>>> >>>> Cheers, >>>> Sandy >>>> >>>>> >>>>> _______________________________________________ >>>> 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 >> >

1 0