November 2014 - Libraries

Proposal: bring BBP to Arrays
by David Feuer 13 Nov '14

13 Nov '14

It looks like Array and IArray have missed some important BBP bits. In particular, we have great ways to build arrays out of lists, but not out of other Foldables. I think we can fix IArray by adding new methods. I think we can fix up Array by adding some functions to Data.Array or by sticking Data.Foldable underneath GHC.Arr and sticking them in there (the low-level fiddling involved would be a better match for GHC.Arr).

3 3

Re: PROPOSAL: Add 'Natural' type to base:Data.Word
by Gershom B 13 Nov '14

13 Nov '14

Let me throw in one key bikeshed to be painted. I don't like the fact that subtraction on naturals is a partial operation as proposed. I would much prefer saturated subtraction where for y > x, x - y = 0. This prior discussion on -cafe tends towards such a definition as being 'universally better' https://www.haskell.org/pipermail/haskell-cafe/2011-March/090265.html Here is my motivation for saturated subtraction: On all non-bottom calculations, it agrees. On calculations that are bottom under partial subtraction, it nonetheless gives a mathematically meaningful and useful result in a coherent way. As a general principle, I think our goal should be to make base more total, not less. The arguments cited in the thread from Runciman's "What About the Natural Numbers" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.3442) are also fairly compelling in this regard. -g > Herbert Valerio Riedel wrote: >>> I hereby suggest to add a type for encoding term-level naturals... >>> to `base:Data.Word` module > > +1 > > because Edward, who is the current leading purveyor of term-level > nats, is in favor. > > Roman Cheplyaka wrote: >> Yeah, having Natural in Data.Word feels unnatural to me. > > Agreed. I'm not sure what the solution is though. I'd be in > favor if someone comes up with something decent. > *However* > I'd be strongly opposed to letting any kind of bikeshedding > getting in the way of Herbert's proposal. > > Thanks, > Yitz

5 5

Re: [GHC] #9781: Make list monad operations fuse
by Kim-Ee Yeoh 11 Nov '14

11 Nov '14

>From the patch fragment at https://phabricator.haskell.org/D455?id=1311#inline-3123 What's the justification for expanding out the definition of mapM from "sequence . map f" into do-notation and duplicated code? Observe how mapM now duplicates code from sequence. The absence of benchmarks is bad enough. What's worse is that the given excuse boils down to "Pity the poor compiler! Let's take over its work instead. Like, just in case, you know." This optimization work needs to take place at a higher level, with deep understanding of existing compiler transformations. Otherwise, it's all a code-muddying crapshoot in the dark. -- Kim-Ee On Tue, Nov 11, 2014 at 2:22 PM, GHC <ghc-devs(a)haskell.org> wrote: > #9781: Make list monad operations fuse > -------------------------------------+------------------------------------- > Reporter: dfeuer | Owner: dfeuer > Type: task | Status: patch > Priority: normal | Milestone: 7.10.1 > Component: Core | Version: 7.9 > Libraries | Keywords: > Resolution: | Architecture: Unknown/Multiple > Operating System: | Difficulty: Unknown > Unknown/Multiple | Blocked By: > Type of failure: Runtime | Related Tickets: > performance bug | > Test Case: | > Blocking: | > Differential Revisions: Phab:D455 | > -------------------------------------+------------------------------------- > > Comment (by Herbert Valerio Riedel <hvr@…>): > > In [changeset:"4923cea56345060faaf77e4c475eac6aa3c77506/ghc"]: > {{{ > #!CommitTicketReference repository="ghc" > revision="4923cea56345060faaf77e4c475eac6aa3c77506" > Define list monad operations using comprehensions > > Define list monad operations using list comprehensions. Code using monad > operations with lists did not fuse fully. Writing list code with `do` > notation or `(>>=)` and `(>>)` operations could allocate more than > equivalent code using list comprehensions. > > Define `mapM` directly, instead of using `sequence` and `map`. This > leads to substantially less allocation in `cryptarithm2`. > > Addresses #9781 > > Reviewed By: ekmett, nomeata > > Differential Revision: https://phabricator.haskell.org/D455 > }}} > > -- > Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9781#comment:4> > GHC <http://www.haskell.org/ghc/> > The Glasgow Haskell Compiler > _______________________________________________ > ghc-tickets mailing list > ghc-tickets(a)haskell.org > http://www.haskell.org/mailman/listinfo/ghc-tickets >

3 4

Implementation of "until"
by David Feuer 09 Nov '14

09 Nov '14

I got to looking at the `until` function (in GHC.Base): -- | @'until' p f@ yields the result of applying @f@ until @p@ holds. until :: (a -> Bool) -> (a -> a) -> a -> a until p f = go where go x | p x = x | otherwise = go (f x) This function doesn't immediately *appear* to be strict in its third argument (`x`), but it actually is: 1. If `p` is lazy, then either it's `const True`, so `until p f x = x`, or it's `const False`, so `until p f x = _|_`. In the first case, it's certainly strict in `x`, and in the second case, it goes into an infinite loop, so it's trivially strict in `x`. 2. If `p` is not lazy, then `until` is obviously strict in `x`. I wondered, therefore, whether there might be some benefit, for strictness analysis, to redefining `until`, either like this: until p f = \ !y -> go y where go x | p x = x | otherwise = go (f x) or (probably not) like this: until p f = go where go !x | p x = x | otherwise = go (f x) The only *semantic* change here is that it can, potentially, replace an infinite loop with an exception. GHC definitely analyses the strictness differently; what I can't tell is whether this will actually help it produce better code in some cases. Specifically, the current `until` implementation gets Str=DmdType <C(S),C(U)><L,C(U)><L,U>, whereas the modified ones get Str=DmdType <C(S),C(U)><L,C(U)><S,1*U>, I don't actually know how to read these, but I can see they're different in the third argument. The two alternatives are also analyzed differently, with the `go` function getting different strictness info. I would speculate, however, that the one that modifies `go` could lead to double-forcing in the loop in some cases, which would presumably be bad. David

4 4

Discussion: fold the Alts
by David Feuer 08 Nov '14

08 Nov '14

We've had First and Last in Data.Monoid for some time, and we now have Alt as well. Unfortunately, we don't have nice convenient functions for using them, the way we have sum and product to use Sum and Product. So we're stuck with funny-looking constructions like listToMaybe . mapMaybe f for lists, and nothing good for other containers. My thought (the names firstAlt and lastAlt would absolutely have to be changed to accommodate non-catch Alternatives, but I'm not inspired at present): firstAlt, lastAlt :: (Foldable f, Alternative m) => (a -> m b) -> f a -> m b firstAlt f = getAlt #. foldMap (Alt #. f) lastAlt f = getAlt #. getDual #. foldMap (Dual #. Alt #. f) where (#.) :: Coercible b c => (b -> c) -> (a -> b) -> (a -> c) f #. g = coerce g This specializes to Maybe very nicely: firstMaybe :: Foldable f => (a -> Maybe b) -> f a -> Maybe b firstMaybe = firstAlt lastMaybe :: Foldable f => (a -> Maybe b) -> f a -> Maybe b lastMaybe = lastAlt

2 5

Proposal: Change the signature of mkWeakMVar
by Edward Kmett 07 Nov '14

07 Nov '14

We've had a ticket languishing in the trac for a couple of years that probably belongs as a libraries proposal: https://ghc.haskell.org/trac/ghc/ticket/7285#comment:6 To summarize it here: In base 4.6 addMVarFinalizer is deprecated in favour of mkWeakMVar of type mkWeakMVar :: MVar a -> IO () -> IO (Weak (MVar a)) This type makes it inherently non-compositional. For instance, if we have a larger datatype T that contains an MVar somewhere inside then there in no way to define mkWeakT in terms of mkWeakMVar; instead, mkWeakT would have to be defined along the lines of mkWeakT :: T a -> IO () -> IO (Weak (T a)) mkWeakT m@(MkT (MVar m#) _) f = IO $ \s -> case mkWeak# m# m f s of (# s1, w #) -> (# s1, Weak w #) It would be better if the type of mkWeakMVar would change to mkWeakMVar :: MVar a -> v -> Maybe (IO ()) -> IO (Weak v) (i.e., following mkWeak rather than mkWeakPtr). (The same comment goes for related functions such as mkWeakIORef.) I'm personally in favor of the change, but wanted to seek wider community feedback. Thoughts? Discussion Period: 2 Weeks

3 5

Question about the PVP regarding changing A.B when no entities are removed/changed
by José Pedro Magalhães 07 Nov '14

07 Nov '14

Hello all, The PVP <https://www.haskell.org/haskellwiki/Package_versioning_policy> seems to allow changing the A.B version numbers in a package even when no entities are removed/changed; the phrasing is (my emphasis): if only new bindings, types, classes, non-orphan instances or modules (but > see below) were added to the interface, then A.B *may* remain the same However, it seems to require changing the C nonetheless: but the new C *must* be greater than the old C As an example, I (mistakenly) released generic-deriving-1.7.0 <https://hackage.haskell.org/package/generic-deriving-1.7.0> after having added one function to it, bumping it from 1.6.3. If my interpretation of the PVP is correct, this change didn't follow the PVP only because I did not increase the C. Had I named it 1.7.4, it would have followed the PVP. (Oddly enough, 0.5.4 would have followed the PVP too!) I think this is a bit odd. Shouldn't we either: 1) Require that A.B remain the same when no entities are removed/changed, or 2) Only require the C to be greater if the A.B remained the same? Thanks, Pedro

8 7

Discussion: remove the Applicative superclass from Alternative
by David Feuer 07 Nov '14

07 Nov '14

Currently, Applicative is a superclass of Alternative. Unfortunately, the *only* laws for Alternative are the monoid laws. Sensible sets of laws have been proposed in the past, but unfortunately *none* of them cover all the current important instances. Thus we have a rather awkward situation where Alternative is a subclass of Applicative, but there's no real way to take advantage of that fact. There are essentially no useful functions that would end up with signatures that look like p :: (Applicative f, Alternative f) => ... I'm wondering, therefore, what people think of the idea of making Alternative entirely independent—just a version of Monoid with a different kind. class Alternative f where empty :: f a (<|>) :: f a -> f a -> f a A second option would be to go with a Functor superclass for Alternative; that might save some typing over the independent Alternative, and it comes with the free theorem fmap f empty = empty

4 9

asum really needs to go into the Foldable class (or something)
by David Feuer 05 Nov '14

05 Nov '14

The current definition is "biased", using foldr and <|> instead of foldMap and the new Alt. This is a bit awkward in the post-BBP world, but we also don't want to just debias it across the board, because if the Foldable is holding lists, the debiased version will be very bad. More generally, there are a number of Foldable members that are very awkward, pleading for MPTC, because the sane implementations depend on both the container type and the element type. I know we're pushing right up against the deadline for 7.10.1, but the current situation is making me very nervous. David

3 9

add Storable a => Storable (Ratio a) and Storable a => Storable (Complex a) to base
by Carter Schonwald 04 Nov '14

04 Nov '14

Getting those two into base for 7.10 would be quite nice. I think this will mostly impact folks who maintain numerical computing libraries, such as myself, and even then, I think this would be a change well worth having! discussion period 1 week (because I'd like to get it OK'd with plenty of time before the merge window for 7.10 finally closes)

10 22