August 2014 - Libraries

Re: [GHC] #9434: GHC.List.reverse does not fuse
by David Feuer 18 Aug '14

18 Aug '14

It looks like the following works at least reasonably well: {-# INLINE[0] revFlip #-} revFlip :: (a -> b -> b) -> b -> a -> b revFlip f b a = f a b {-# NOINLINE[1] reverse #-} reverse :: [a] -> [a] reverse xs = rv xs [] where rv [] r = r rv (y:ys) r = rv ys (y:r) {-# RULES "reverse" [~1] forall xs . reverse xs = build $ \c n -> foldl (revFlip c) n xs "reversePlain" [1] forall xs . foldr (\v fn z -> fn ((revFlip (:)) z v)) id xs [] = reverse xs #-} The complicated reversePlain rule actually fires, at least in my tests. If we miss a few, that may not be a disaster. I'm not at all confident that there's anything to be done about your concern about beta reduced forms without totally hosing other optimizations. David Feuer On Fri, Aug 15, 2014 at 3:22 PM, Dan Doel <dan.doel(a)gmail.com> wrote: > Yeah, I realized that part of the idea is for (the new) foldl to be defined > in terms of foldr, then inline (or rewrite), fuse, and get optimized. So > maybe you can't delay the foldl inlining. > > But it should be possible to recognize the foldr definition of foldl and > rewrite back, as long as the definition of foldl has appropriately > recognizable combinators instead of just lambda expressions. > > > On Fri, Aug 15, 2014 at 3:13 PM, David Feuer <david.feuer(a)gmail.com> wrote: >> >> I forgot about the flip! I wonder if I can even avoid NOINLINEing the >> foldl if I noninliningFlip and then bring it back from the resulting foldr. >> I'll have to try tonight. Thanks! >> >> On Aug 15, 2014 12:57 PM, "Dan Doel" <dan.doel(a)gmail.com> wrote: >>> >>> Make foldl's inline phased, and see what happens? >>> >>> Presumably the reason it doesn't have a phase limit yet is that it never >>> participated in any fusion before, so there was never a reason to not just >>> inline. >>> >>> Other than that it seems like: >>> >>> reverse xs >>> => rewrite >>> build (\c n -> foldl (noinlineFlip c) n xs) >>> => inline >>> foldl (noinlineFlip (:)) [] xs >>> => rewrite >>> reverse xs >>> >>> where I assume you need a special flip which may or may not exist in >>> these modules already. >>> >>> >>> On Fri, Aug 15, 2014 at 12:46 PM, David Feuer <david.feuer(a)gmail.com> >>> wrote: >>>> >>>> Yes, but I'm not sure how to do that, especially because foldl doesn't >>>> have the phased NOINLINE that foldr does. >>>> >>>> On Aug 15, 2014 12:45 PM, "Dan Doel" <dan.doel(a)gmail.com> wrote: >>>>> >>>>> Isn't this kind of thing fixed for other functions by rewriting back >>>>> into the direct recursive definition if no fusion happens? >>>>> >>>>> >>>>> On Fri, Aug 15, 2014 at 11:41 AM, David Feuer <david.feuer(a)gmail.com> >>>>> wrote: >>>>>> >>>>>> I'm having trouble when it doesn't fuse—it ends up with duplicate >>>>>> bindings at the top level, because build gets inlined n times, and the >>>>>> result lifted out. Nothing's *wrong* with the code, except that there are >>>>>> multiple copies of it. >>>>>> >>>>>> On Aug 15, 2014 10:58 AM, "GHC" <ghc-devs(a)haskell.org> wrote: >>>>>>> >>>>>>> #9434: GHC.List.reverse does not fuse >>>>>>> >>>>>>> -------------------------------------+------------------------------------- >>>>>>> Reporter: dfeuer | Owner: >>>>>>> Type: bug | Status: new >>>>>>> Priority: normal | Milestone: >>>>>>> Component: | Version: 7.9 >>>>>>> libraries/base | Keywords: >>>>>>> Resolution: | Architecture: >>>>>>> Unknown/Multiple >>>>>>> Operating System: | Difficulty: Easy (less >>>>>>> than 1 >>>>>>> Unknown/Multiple | hour) >>>>>>> Type of failure: Runtime | Blocked By: >>>>>>> performance bug | Related Tickets: >>>>>>> Test Case: | >>>>>>> Blocking: | >>>>>>> Differential Revisions: | >>>>>>> >>>>>>> -------------------------------------+------------------------------------- >>>>>>> >>>>>>> Comment (by simonpj): >>>>>>> >>>>>>> Great. Just check that when fusion ''doesn't'' take place, the >>>>>>> result is >>>>>>> good. And do a `nofib` comparison for good luck. Then submit a >>>>>>> patch. >>>>>>> >>>>>>> Thanks for doing all this work on fusion, David. >>>>>>> >>>>>>> Simon >>>>>>> >>>>>>> -- >>>>>>> Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9434#comment:2> >>>>>>> GHC <http://www.haskell.org/ghc/> >>>>>>> The Glasgow Haskell Compiler >>>>>> >>>>>> >>>>>> _______________________________________________ >>>>>> ghc-devs mailing list >>>>>> ghc-devs(a)haskell.org >>>>>> http://www.haskell.org/mailman/listinfo/ghc-devs >>>>>> >>>>> >>> >

2 2

Polymorphism in the Prelude
by Richard Eisenberg 17 Aug '14

17 Aug '14

Hi libraries, Let me try to sum up the general sentiment I've seen: Having lots of polymorphism in the Prelude is great, but for two problems: 1) It's very confusing to novices. 2) In the case of using Control.Category definitions: kind-polymorphism is not portable I wish to ignore (2) for now, as it's a smaller concern given that it affects only a portion of the proposed changes. As a way to mitigate (1), I have been thinking of proposing something almost exactly along the lines of http://comments.gmane.org/gmane.comp.lang.haskell.glasgow.user/23719 (thanks for posting that link -- saved me from writing up the same thing!). But, after reading that thread, I tend to agree that tweaking the module system seems the wrong way to deal with helping novices. In designing my own libraries, my general guideline is to make the easy thing easy and make the hard thing only slightly less easy. Spurred on by Erik Hesselink's comment (http://www.haskell.org/pipermail/libraries/2014-June/023174.html) what if we just have two versions of `base` modules, the "normal" one that exports more monomorphic definitions (which novices are more likely to use) and a "Poly" one that exports more polymorphic definitions. For example: {{{ {-# LANGUAGE NoImplicitPrelude #-} import Prelude.Poly import Data.List.Poly import Data.Foldable import Control.Monad.Poly }}} and then it just works. Pros: - Not disruptive to current status quo. - No change in error messages for novices. - Can actually be implemented without *any* changes to `base` -- I could upload this solution to Hackage today. Cons: - Maintaining two copies of export lists. - Needs NoImplicitPrelude pragma. - Overhead of remembering which modules have a "Poly" version and which don't. - Somewhat ugly. Even as I write this, I'm not sure that this is at all a good idea. But, to me, it's really intriguing that the solution is achievable today, with no difficulty. I would wager that if these Poly modules were out in the wild today, we might all grumble at them, but I don't know if there would be a movement to change the Prelude. Richard

19 32

Maintenance release of haskell-cgi?
by John Alfred Nathanael Chee 15 Aug '14

15 Aug '14

Hackage trustees, haskell-cgi [1] doesn't build with ghc 7.8.3. Two pull requests exist on github [2,3] and the maintainer (cc'd) is unresponsive. Can someone do a proxy release of haskell-cgi? Thanks. [1] https://github.com/andersk/haskell-cgi [2] https://github.com/andersk/haskell-cgi/pull/7 [3] https://github.com/andersk/haskell-cgi/pull/6 -- Love in Jesus Christ, John Alfred Nathanael Chee http://www.biblegateway.com/ http://web.cecs.pdx.edu/~chee/

2 5

Am I missing something about unfoldr?
by David Feuer 15 Aug '14

15 Aug '14

The current definition: unfoldr :: (b -> Maybe (a, b)) -> b -> [a] unfoldr f b = case f b of Just (a,new_b) -> a : unfoldr f new_b Nothing -> [] I haven't yet looked over the Core to see if GHC is able to do a worker/wrapper transformation to inline it, but we definitely want to inline it (in some appropriate phase), because doing so has the potential to erase the Maybes. It also isn't a good producer for foldr/build. However, if we (re)write it like this: unfoldrB f b c n = go b where go b = case f b of Just (a,new_b) -> a `c` go new_b Nothing -> n unfoldr f b = build (unfoldrB f b) then we get some really nice fusion: foldr c n (unfoldr f b) = foldr c n (build (unfoldrB f b)) = unfoldrB f b c n The list is gone, and there are no new closures or data structures in its place. As a side benefit, we could write groupBy as an unfoldr, and make it a somewhat better producer, especially when the groups are small. I don't *think* there's any way to make groupBy a good consumer for foldr/build, unfortunately.

4 10

Proposal: add unfoldr1 to the somewhere in base
by David Feuer 15 Aug '14

15 Aug '14

Way back in 2001, Shin-Cheng Mu proposed an unfoldr1 combinator: http://code.haskell.org/~dons/haskell-1990-2000/msg06775.html I discussed this a bit with shachaf in #haskell, and he noted that a similar function, with a slightly different but isomorphic type, appears in Edward Kmett's semigroups package as the unfoldr for NonEmpty. I propose that we add this. It can be written unfoldr1 :: (b -> (a, Maybe b)) -> b -> [a] unfoldr1 f b = go b where go b = case f b of (a, may_b) -> a : maybe [] go may_b With the appropriate RULES, it can be wrapped up in build and fuse properly. I'd love to see this written as an unfoldr instead. Does anyone know if that's possible?

2 4

Seeking comments on proposed fusion rules
by David Feuer 14 Aug '14

14 Aug '14

The rules: lpaste.net/108508 The boring explanation: As I mentioned earlier, we currently can't fuse things like foldr (x : build g) The foldr can't see the build. Earlier, I considered a simple cons/build rule that would rewrite x : build g to build (\c n -> x `c` g c n) I wasn't quite satisfied with this approach, largely because it treats foldr c n (x1 : x2 : ... : xn : build g) one way, and foldr c n ([x1, x2, ..., xn) : build g) another way. The former expands out the foldr, while the latter (via various rules involving augment) translates into a foldr over [x1, x2, ..., xn]. I therefore came up with the idea of translating x1:x2:...:xn:build g into [x1:x2:..:xn]++build g, and then letting the current rules do their thing. dolio and carter (in #ghc) were concerned about what would happen if fusion *didn't* occur, in which case the resulting code appears to be *worse*. So then I wrote some rules to fix that up, which actually look likely to be good rules in general. They turn [x1:x2:...:xn] ++ ys into x1:x2:...:xn:ys I ended up having to do more that I had originally expected in my rules, because they miss a phase they need (it may be possible to fix that; I'm not sure, because I'm very new to this business); I left comments showing each step of the translation. One thing of note is that I ended up using (by hand) the augment/augment rule that is commented out as probably not being useful. In my limited testing, the rules seem to do what they're supposed to (when I can understand the Core), and the profiler is very pleased.

3 5

Overlapping and incoherent instances
by Simon Peyton Jones 11 Aug '14

11 Aug '14

Friends One of GHC's more widely-used features is overlapping (and sometimes incoherent) instances. The user-manual documentation is here<http://www.haskell.org/ghc/docs/latest/html/users_guide/type-class-extensio…>. The use of overlapping/incoherent instances is controlled by LANGUAGE pragmas: OverlappingInstances and IncoherentInstances respectively. However the overlap/incoherent-ness is a property of the *instance declaration* itself, and has been for a long time. Using LANGUAGE OverlappingInstances simply sets the "I am an overlapping instance" flag for every instance declaration in that module. This is a Big Hammer. It give no clue about *which* particular instances the programmer is expecting to be overlapped, nor which are doing the overlapping. It brutally applies to every instance in the module. Moreover, when looking at an instance declaration, there is no nearby clue that it might be overlapped. The clue might be in the command line that compiles that module! Iavor has recently implemented per-instance-declaration pragmas, so you can say instance {-# OVERLAPPABLE #-} Show a => Show [a] where ... instance {-# OVERLAPPING #-} Show [Char] where ... This is much more precise (it affects only those specific instances) and it is much clearer (you see it when you see the instance declaration). This new feature will be in GHC 7.10 and I'm sure you will be happy about that. But I propose also to deprecate the LANGUAGE pragmas OverlappingInstances and IncoherentInstances, as way to encourage everyone to use the new feature instead of the old big hammer. The old LANGUAGE pragmas will continue to work, of course, for at least another complete release cycle. We could make that two cycles if it was helpful. However, if you want deprecation-free libraries, it will entail a wave of library updates. This email is just to warn you, and to let you yell if you think this is a bad idea. It would actually not be difficult to retain the old LANGUAGE pragmas indefinitely - it just seems wrong not to actively push authors in the right direction. These deprecations of course popped up in the test suite, so I've been replacing them with per-instance pragmas there too. Interestingly in some cases, when looking for which instances needed the pragmas, I found...none. So OverlappingInstances was entirely unnecessary. Maybe library authors will find that too! Simon

18 36

Foldr/build fusion and reverse
by David Feuer 11 Aug '14

11 Aug '14

Currently, reverse does not participate at all. This law looks eminently exploitable: foldr c n (reverse xs) = foldl (flip c) n xs foldr c n $ reverse $ build xs =

1 0

Proposal: Add Data.Semigroup to base, as a superclass of Monoid
by John Wiegley 11 Aug '14

11 Aug '14

1. I propose that we add the following package to base: http://hackage.haskell.org/packages/archive/semigroups/0.9.2/doc/html/Data-… This is somewhat in the spirit of the AMP proposal: further improving the correctness of our algebraic abstractions. 2. That we make Semigroup a superclass of Monoid, so that (minimally): class Semigroup a where (<>) :: a -> a -> a class Semigroup a => Monoid a where mempty :: a mconcat :: [a] -> a mconcat = foldr (<>) mempty mappend :: Semigroup a => a -> a -> a mappend = (<>) 3. (Optional, recommended) There are other useful functions that can be added to Semigroup, such as sconcat and times1p, but I will let Edward speak to whether those should be proposed at this time. 4. (Optional, recommended) That we fix the Monoid instance for Maybe to be: instance Semigroup a => Semigroup (Maybe a) where Just x <> Just y = Just (x <> y) _ <> _ = Nothing instance Semigroup a => Monoid (Maybe a) where mempty = Nothing For some clarification on what semigroups are and why we'd want to change Monoid, I excerpt here a selection from Brent Yorgey's "Monoids and Variations" paper: Semigroups A semigroup is like a monoid without the requirement of an identity element: it consists simply of a set with an associative binary operation.... Of course, any monoid is automatically a semigroup (by forgetting about its identity element). In the other direction, to turn a semigroup into a monoid, simply add a new distinguished element to serve as the identity, and extend the definition of the binary operation appropriately. This creates an identity element by definition, and it is not hard to see that it preserves associativity.... Adding a new distinguished element to a type is typically accomplished by wrapping it in Maybe. One might therefore expect to turn an instance of Semigroup into an instance of Monoid by wrapping it in Maybe. Sadly, Data.Monoid does not define semigroups, and has a Monoid instance for Maybe which requires a Monoid constraint on its argument type... This is somewhat odd: in essence, it ignores the identity element of [the type] and replaces it with a different one. -- John Wiegley FP Complete Haskell tools, training and consulting http://fpcomplete.com johnw on #haskell/irc.freenode.net

9 9

Proposal: Add strict iterate'
by David Feuer 10 Aug '14

10 Aug '14

I think most if not all applications of iterate would prefer to accumulate strictly—iterating a constant function is not very useful and the spine of the result of iterate is always the same. Unlike unfoldr, which has enough strictness built in to allow its caller to decide whether to accumulate strictly, iterate is entirely lazy. I therefore propose: iterate' :: (a -> a) -> a -> [a] iterate' f b = unfoldr go b where go x = x `seq` Just (x, f x)

6 8