July 2014 - Libraries

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

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

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

Haskell Platform 2014.2.0.0 Release Candidate 3
by Mark Lentczner 31 Jul '14

31 Jul '14

Small update to the Haskell Platfrom 2014.2.0.0 release: We have new Release Candidate 3 versions of the source tarball... and a new generic-linux bindist of the platform! - source tarball: haskell-platform-2014.2.0.0-srcdist-RC3.tar.gz <http://www.ozonehouse.com/mark/platform/haskell-platform-2014.2.0.0-srcdist…> - generic linux: haskell-platform-2014.2.0.0-unknown-linux-x86_64-RC3.tar.gz <http://www.ozonehouse.com/mark/platform/haskell-platform-2014.2.0.0-unknown…> *Windows and OS X users: There are no RC3 versions - as the RC2 versions seem to be holding up fine!* *General* - hptool (and hence ./platform.sh script) take a new --prefix parameter that is used for generic (non-OS X, non-Windows) builds: It sets the root under which haskell installations are located. Defaults to /usr/local/haskell. Everything will be placed in a directory named ghc-7.8.3-<arch> under this prefix. - activate-hs script for default Posix-like builds - small fixes to allow bootstrapping the platform with GHC 7.4 - README and LICENSE updated *Source Tarball* - all missing pieces now present - build platfrom from source tarball verified *Generic Linux Binary Dist* - Built from the GHC's generic Linux bindist for Deb 7 style systems - Complete tarball: this is all you need to install Haskell on a compatible system - Built on Ubuntu 12.04LTS - Tested on Ubuntu 14 - my system needed a symlink from libgmp.so to libgmp.so.10 - this seems to be an issue with the GHC bindist built components To install this: cd / sudo tar xvf ~/haskell-platform-2014.2.0.0-unknown-linux-x86_64-RC3.tar.gz sudo /usr/local/haskell/ghc-7.8.3-x8_64/bin/activate-hs This will finish the package registration, and install symlinks from /usr/local/bin for all the standard haskell command line tools. — Mark *shasum -a 256:* ab759ec50618f2604163eca7ad07e50c8292398a2d043fdc1012df161b2eb89a haskell-platform-2014.2.0.0-srcdist-RC3.tar.gz 0da6879ae657481849e7ec4e5d3c4c035e090824167f97434b48af297ec17cf9 haskell-platform-2014.2.0.0-unknown-linux-x86_64-RC3.tar.gz

1 0

RE: Overlapping and incoherent instances
by Niklas Haas 30 Jul '14

30 Jul '14

On Tue, 29 Jul 2014 16:29:45 +0000, Simon Peyton Jones <simonpj(a)microsoft.com> wrote: > CAN_OVERLAP and CAN_BE_OVERLAPPED? > > (instead of OVERLAPPING and OVERLAPPABLE) > > Or CAN-OVERLAP, CAN-BE-OVERLAPPED > > That’s ok with me if that’s what you all want! > > Simon For my 2¢, I think OVERLAPPING and OVERLAPPABLE are just fine - I immediately understood what each word meant, there's no ugly ‘_’ or ‘-’ to agonize about for eternity. I would be +1 on just keeping those names as-is. I'm neutral about whether or not I like OVERLAPS as a combination of both, I don't think that communicates quite clearly what's going on - but I do think it's important to have a way to not have to write both lengthy pragmas out.

2 1

inits in stream-fusion
by David Feuer 30 Jul '14

30 Jul '14

The inits function in the stream-fusion package has the same very bad performance bug as the one in base/Data.List. Presumably a similar fix should work, but some adjustments may be desirable--I don't know enough about the framework to say. David Feuer

1 0

Re: Proposal: Add strict iterate' (and a discussion of possible new RULES)
by David Feuer 30 Jul '14

30 Jul '14

I'm pushing hard to get unfoldr fixed ASAP, and looking to take advantage of that. Specifically, I like the idea of using the fusion that (I dearly hope) will come with unfoldr to make a variety of other things fuse that currently need their own special rules. I also want to extend fusion by one or two general rules. One that looks very good is similar to the rejected foldr/cons rule, but seems somewhat less likely to cause problems while still enhancing fusion in general: {-# RULES "cons/build" forall x (g::forall b . (a->b->b)->b->b) . x : build g = build (\c n -> x `c` g c n) #-} This will allow foldr/build fusion to look past conses. So for example, foldr f q (x : build g) will be rewritten (cons/build) to foldr f q (build (\c n -> x `c` g c n)) and then (fold/build) to (\c n -> x `c` g c n) f q This reduces to f x (g f q) A discussion about foldr k z (x1:x2:x3:...:x2000:build g), a possible way to fix it, and why I don't think it's important anyway. This means the same thing as foldr k z ([x1,x2,x3,...,x2000] ++ build g) The current ++ rule rewrites this to foldr k z (augment (\c n -> foldr c n [x1,...,x2000]) (build g)) Then foldr/augment: (\c n -> foldr c n [x1,..,x2000]) k (foldr k z (build g)) Then foldr/build: (\c n -> foldr c n [x1,...,x2000]) k (g k z) Then beta reduction: foldr k (g k z) [x1,...,x2000] So to take the example from earlier, foldr f q (x : build g) is currently bad, but foldr f q ([x] ++ build g) will end up foldr f (g f q) [x] and then in this case the foldr/single rule will give f x (g f q) but if more than one element were in the list, we'd end up with a fold over the literal list (not bad in general). This suggests a fix, but one that may be difficult to implement within GHCs stage framework as is (I'm not quite sure; someone who knows more about the system may see a way to do this, but I think it wants to happen before the ++ rule, which I think happens at the beginning of time): Translate x1:x2:x3:...:build g to [x1,x2,x3,...] ++ build g Then let everything else happen as usual. I think, however, that this is probably overkill. Just implement cons/build and tell users that if they want x1:x2:x3:....:x2000:foo not to expand under foldr then they need to write [x1,x2,x3,...,x2000]++foo instead.

1 0

Re: Overlapping and incoherent instances
by Felipe Lessa 29 Jul '14

29 Jul '14

On 29-07-2014 20:41, Stephen Paul Weber wrote: >> instance {-# OVERLAPPABLE #-} Show a => Show [a] where ... > >> instance {-# OVERLAPPING #-} Show [Char] where ... > > This, to me, is an admission that developers are not going to want to turn > overlapping on globally in general, and so the current language extensions > would not make sense to get adopted into the core language at any point. > I agree with this idea, and so would second the proposal mentioned at > <http://www.reddit.com/r/haskell/comments/2c136i/xoverlappinginstances_and_x…> > that a language extension that adds actual keywords to tag instances that > should be allowed to overlap be added, instead of resorting to pragmas. > This seems like an approach that could be useful in general and one could > imagine moving "past" an extension to the core language at some point, > potentially. OTOH, the pragma is mostly harmless for older GHC versions, while the keyword approach needs a preprocessor. -- Felipe.

1 0