- Libraries - Haskell.org

Discussion: expand documentation of amap for IArray
by David Feuer 14 Nov '14

14 Nov '14

The current documentation for Data.Array.IArray.amap says what it does, but doesn't say anything about how it should (and shouldn't!) be used. Specifically, it does not implement amap/amap or amap/coerce rules, and it probably cannot do so safely if the IArray instance does not satisfy the appropriate lens-like laws. Thus the most appropriate way to use this function is probably to implement the Functor instance for an IArray type, using type-specific RULES. It's probably *not* such a hot idea to use this amap directly. I don't know if all that should be crammed, with explanation, into the Haddocks or if there's a better way to handle it. David

1 0

Monoid instance for IO
by Gabriel Gonzalez 14 Nov '14

14 Nov '14

I would like to add the following `Monoid` instance for `IO` to `Data.Monoid`: ``` instance Monoid a => Monoid (IO a) where mempty = pure mempty mappend = liftA2 mappend ``` I describe the benefit of this particular instance in this blog post: http://www.haskellforall.com/2014/07/equational-reasoning-at-scale.html ... and Conal Elliot describes the general trick of recursively lifting `Monoid` instances in his type class morphisms paper: http://conal.net/papers/type-class-morphisms/type-class-morphisms-long.pdf The primary benefit of the `Monoid` instance is that it chains well with other `Monoid` instances in `base` to create derived `Monoid` instances. The following types are examples of useful derived `Monoid` instances: ``` IO () -- Because `()` is a `Monoid` a -> IO () -- Because `a -> r` is a `Monoid` if `r` is a `Monoid` IO (a -> IO ()) -- This comment explains the utility of this instance: http://www.reddit.com/r/haskell/comments/22bn1m/monads_lifting_join_and_sid… ``` Here are other alternatives that I considered: **Alternative A)** Define a newtype for the `Monoid` instance, either specialized to `IO`: ``` newtype IOMonoid a = IOMonoid { getIOMonoid :: IO a } deriving (Functor, Applicative, Monad) instance Monoid a => Monoid (IOMonoid a) where mempty = pure mempty mappend = liftA2 mappend ``` ... or generalized to all applicatives: ``` newtype LiftMonoid f a = LiftMonoid ( getLiftMonoid :: f a } instance (Applicative f, Monoid a) => Monoid (LiftMonoid f a) where ... ``` I prefer not to use a newtype because the principle benefit of a `Monoid` instance for `IO` is for the derived instances. Using the example `IO (a -> IO ())` type, suppose that I had two values of that type which I wanted to mappend: ``` m :: IO (a -> IO ()) n :: IO (a -> IO ()) ``` Using newtypes (either one), I'd have to write: ``` getNewtype (Newtype (fmap (fmap Newtype) m) <> Newtype (fmap (fmap Newtype) n)) ``` ... instead of just: ``` m <> n ``` **Alternative B)** Provide a different `Monoid` instance for `IO`, such as one that uses concurrency There are two issues with this approach: 1. There is not a well-defined semantics for non-`STM` concurrency that we could use to prove the `Monoid` laws 2. Even if there were a well-defined semantics, it would be better suited as an `Alternative` instance instead of a `Monoid` instance To clarify the latter point, Peaker convinced me [[ http://www.reddit.com/r/haskell/comments/2guo44/what_is_wrong_with_the_mono… | here ]] that for certain `Applicative`s it's worth distinguishing the behavior of the `Alternative` instance from the behavior of the `Monoid` instance. The `Monoid` instance can recursively delegate to the `Monoid` instance of the `Applicative`'s type parameter, whereas the `Alternative` instance cannot. I also created a task on phabricator here since I'm used to the Github style of discussing issues on the repository issue tracker: https://phabricator.haskell.org/T55?workflow=create

7 6

Proposal: Make GHC.Arr.listArray slightly stricter to allow fusion
by David Feuer 14 Nov '14

14 Nov '14

Currently, GHC.Arr.listArray is pretty lazy: listArray (1,3) $ [1,2,3] ++ undefined will work perfectly fine. This is actually lazier than the current array: array (1,3) $ [(1,1), (2,2), (3,3)] ++ undefined = undefined Unfortunately, I don't think it's possible to make listArray fuse with a list producer while preserving quite that level of laziness. If we're willing to be slightly stricter, however, I think everything works. Specifically, I propose that we allow listArray (length xs) (xs ++ _|_) = _|_ The resulting listArray code is below. {-# INLINE mylistArray #-} listArray :: Ix i => (i,i) -> [e] -> Array i e listArray (l,u) es = runST (ST $ \s1# -> case safeRangeSize (l,u) of { n@(I# n#) -> case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) -> let fillFromList y r i# s3# | isTrue# (i# ==# n#) = s3# | otherwise = case writeArray# marr# i# y s3# of s4# -> r (i# +# 1#) s4# in case foldr fillFromList (\_ s# -> s#) es 0# s2# of s5# -> done l u n marr# s5# }})

3 4

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