September 2014 - Libraries

Proposal: (breaking change to avoid fragile breakage) change the definition of foldr2, zip, and zipWith
by David Feuer 01 Oct '14

01 Oct '14

BACKGROUND TRAC: #9495 GHC's definition of foldr2 violates the spec of the Haskell Report, making some programs less defined than they should be, and does so in a way that is quite fragile, dependent on a number of different factors—that is, it is likely hard to debug. Details: The current "baseline" definition of foldr2 (before rewrite rules) does what the Report requires: foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c foldr2 k z = go where go [] _ys = z go _xs [] = z go (x:xs) (y:ys) = k x y (go xs ys) There are two rewrite rules, foldr2/left and foldr2/right, designed to allow foldr2 to fuse with build appearing in either the first or second list argument. foldr2/left is perfectly safe (as long as the build argument is legitimate). foldr2/right is not, as comments in the source partially explain. The problem shows up if you have something shaped like zip [1,7,42,5] (1:8:4:11:undefined) but where the second list (ending in undefined) is actually produced using build, and GHC chooses to fuse foldr2 with it. The Report requires the above to produce [(1,1),(7,8),(42,4),(5,11)], but GHC will instead produce (1,1):(7,8):(42,4):(5,11):_|_ This issue can make a program that works with -O0 fail with -O, and can cause fragility depending on exactly what fuses. SCOPE One obvious question is what kinds of build forms can cause problems. Many, like map and fromEnumTo, don't have enough power to be likely to cause trouble. Joachim Breitner, however, realized that the current implementation of filter has enough power to break things. So here's a complete example of code that will break with -O but not with -O0: {-# NOINLINE don'tFuse #-} don'tFuse = id p x = 100 `mod` x < 20 main = print $ zip (don'tFuse [10,9..1]) (filter p [10,9,..]) Things will only get worse if I succeed in my plan to bring unfoldr into the framework. SOLUTIONS 1. One solution, of course, is to eliminate unfoldr2/right, bringing GHC into compliance with the Report. I really like this idea, but Joachim thinks it is not worth the potential performance impact on code written before or without regard for the change. We both agree that a reasonable alternative is 3. Modify the baseline definition of unfoldr2 as follows: foldr2 :: (a -> b -> c -> c) -> c -> [a] -> [b] -> c foldr2 k z = go where go [] ys = ys `seq` z go _xs [] = z go (x:xs) (y:ys) = k x y (go xs ys) This should, we believe, make the baseline definition fail where the one fused by foldr2/right would fail, giving consistent semantics. WHAT MIGHT BREAK Code that currently works but will break with this change has two properties: 1. It relies on the asymmetry in foldr, zipWith, or zip to avoid running into bottom. 2. foldr2/right does not fire, either because the second list is not a good producer or because GHC applies the foldr2/left rule instead. That is, most of the code that this change will break is fragile under the current scheme. DISCUSSION PERIOD Standard two weeks.

3 4

Proposal: change the Bits instance for Bool to align with other basic types and support branchless calculations
by David Feuer 30 Sep '14

30 Sep '14

Currently, the (.&.) and (.|.) methods for Bool are short-circuiting, defined like this: instance Bits Bool where (.&.) = (&&) (.|.) = (||) Unlike the instances for Int, Word, etc., this gives short-circuiting behavior (conditionally lazy in the second operand). Unfortunately, this requires a conditional branch to implement, which can sometimes be bad. Since (&&) and (||) are readily available to anyone who wants short-circuiting, I propose that we use the following instead. Note that the Bits class does not specify anything about this aspect of instance behavior. x .&. y = tagToEnum# (dataToTag# x `andI#` dataToTag# y) x .|. y = tagToEnum# (dataToTag# x `orI#` dataToTag# y) The rest of the operations look like this: x `xor` y = tagToEnum# (dataToTag# x `xorI#` dataToTag# y) complement x = tagToEnum# (dataToTag# x `xorI#` 1#) shift x s = testBit x s rotate x _ = x -- I don't think we gain anything changing this one. bit 0 = True bit _ = False testBit x b = tagToEnum# (dataToTag# x `andI#` (dataToTag# b ==# 0#)) bitSizeMaybe _ = Just 1 bitSize _ = 1 isSigned _ = False popCount x = I# (dataToTag# x) instance FiniteBits Bool where finiteBitSize _ = 1 countTrailingZeros x = I# (dataToTag# x `xorI#` 1#) countLeadingZeros x = I# (dataToTag# x `xorI#` 1#)

9 40

Pre-proposal discussion: add a version of dropWhileEnd with different laziness properties to Data.List
by David Feuer 29 Sep '14

29 Sep '14

BACKGROUND: A somewhat common idiom I discovered digging around the GHC tree is the use of reverse . dropWhile p . reverse to remove some unwanted things from the end of a list. The lists involved tend to be short (e.g., file names, package names, lines of user input, etc.) and the amount removed from the end of the list tends to be short (a trailing newline, the last part of a filename, extra spaces, etc.). I initially intended to replace all of these with Data.List.dropWhileEnd p. Unfortunately, my benchmarking showed that this had a substantial negative impact on performance. Data.List.dropWhileEnd is defined like this: dropWhileEnd p = foldr (\x r -> if p x && null r then [] else x:r) [] This is lazy in the *spine* of the list--it can "flush its buffer" and produce list elements any time p x is found to be false. This is the best you can do if you need to process a very large list and don't want to have to load the whole thing into memory, and/or your predicate is *very* cheap. Unfortunately, it pays a steep price: for non-trivial p, it's strict in the *elements* of the list. This makes it unsuitable, from a performance standpoint, for most of the purposes for which I've seen reverse . dropWhile p . reverse used. CONCEPT: Add (by some name) a function that is lazy in the elements while strict in the spine: dropWhileEndLE :: (a -> Bool) -> [a] -> [a] -- specification: dropWhileEndLE p = reverse . dropWhile p . reverse dropWhileEndLE p = foldr (\x r -> if null r && p x then [] else x:r) [] This is a good bit faster than the double-reversing version, presumably because it presumably allocates its buffer stack on the GHC stack rather than spraying junk across the heap. If I were a Time Lord, I'd go back in time and add to the library, instead of dropWhileEnd as it is, a function with a name like takeUntilLastSatisfying p = dropWhileEnd (not . p) which has a name that explains better what it does, and I'd define dropWhileEnd to be dropWhileEndLE. But I'm not a Time Lord, so I'd like to hear what name or naming approach other people would recommend.

6 13

Discussion: Change the specification of rotateL for non-finite Bits, or move rotations to FiniteBits
by David Feuer 29 Sep '14

29 Sep '14

Problem: The documentation currently specifies that for non-finite Bits instances, rotate is the same as shift. This seems reasonable for Integer rotateR, but very strange for Integer rotateL. In particular: rotateL 5 (-1 :: Int) = -1 rotateL 5 (-1 :: Integer) = 16 Based on the concept that Integers represent two's complement out to infinity, rotating a negative integer left should fill with 1s, but it fills with 0s instead. Solutions: As stated in the subject, I think one reasonable solution is just to make rotateL fill with 1s for negative non-finite instances, and the other is to move rotations to FiniteBits, as was done with bitSize.

4 7

List of core libraries
by Thomas Miedema 29 Sep '14

29 Sep '14

Hello core libraries committee, on the library submissions page on the Haskell wiki it says: "The core libraries ... define basic APIs that are expected to be available in any Haskell implementation." Is this list of those core libraries and their maintainers up-to-date: http://www.haskell.org/haskellwiki/Library_submissions#The_Core_Libraries I am asking, since GHC 7.8.3 also includes: * binary * bytestring * filepath * haskeline * hoopl * integer-gmp * terminfo * transformers But they are not core libraries. Is that correct? And GHC 7.8.3 doesn't include: * mtl * parallel * primitive * random * vector But they are core libraries. Is that correct? Cheers, Thomas

5 14

Re: [core libraries] List of core libraries
by Edward Kmett 28 Sep '14

28 Sep '14

Herbert: Heretofore I'd been treating filepath as owned by Neil Mitchell, but that statement does sound like he's handed it off to the libraries process, which would make it a core-libraries issue if he doesn't want to deal with it. I'm copying him on this thread to get his opinion. I've also copied Andy Gill, to see if he has any opinions on the state of who owns update responsibility for hpc itself. Andy, Neil: Thoughts? Thomas: Thanks for forcing this issue to attention. -Edward On Sun, Sep 28, 2014 at 2:14 PM, Herbert Valerio Riedel <hvriedel(a)gmail.com> wrote: > On 2014-09-28 at 19:40:25 +0200, Thomas Miedema wrote: > > [...] > > > Ok, final question: What about filepath and hpc? Their .cabal files list > > libraries(a)haskell.org as maintainer, which usually means the Core > Libraries > > Committee. Should filepath be added to that list, and the maintainer for > > both filepath and hpc be set to the Core Libraries Committee? If not, who > > maintains filepath? > > This is supposed to be an answer, but rather additional data-points: > > As far as filepath is concerned: > > http://community.haskell.org/~ndm/filepath/ > > states > > | The library is now part of the core Haskell libraries, and since GHC > | 6.6.1 has been shipped with all major compilers. While I am the > | original author, changes are now made through the library submissions > | process. > > as for Hpc, if you look at its changelog over at > > http://git.haskell.org/packages/hpc.git/shortlog > > it's been effectively maintained by GHC HQ for the last couple of > years... >

1 0

Proposal (long term): Remove (/=) from Eq; change the semantics of (==) for floating point
by David Feuer 25 Sep '14

25 Sep '14

As Edward Kmett explained to me, (/=) is currently needed in Eq to support IEEE floating point semantics for (==) and (/=). As I see it, those semantics are badly broken from the perspective of what Eq is supposed to mean, and really should be supported using special functions (eqIEEE and neqIEEE or whatever), whereas the most appropriate Eq instance for floating point would be something more like instance Eq Double where x == y = decodeFloat x == decodeFloat y If this is (eventually) done, that would allow us to remove (/=) from Eq, reducing its dictionary to a single member, (==), improving efficiency when the type is not statically known. David

7 9

Pre-Proposal: Add Validation somewhere easily accessible
by Joseph Abrahamson 25 Sep '14

25 Sep '14

The “purely applicative Either” is Either with a new Applicative interface which can no longer take a corresponding Monad interface. I have personally reinvented it over and over although it is perhaps commonly known as Validation: data Validation e a = Invalid e | Valid a deriving ( Show, Functor, … ) instance Monoid e => Applicative (Validation e) where pure = Valid Invalid e1 <*> Invalid e2 = Invalid (e1 <> e2) Invalid e1 <*> _ = Invalid e1 <*> Invalid e2 = Invalid e2 Valid f <*> Valid a = Valid (f a) -- No corresponding Monad It could be perhaps better implemented as a newtype wrapper over Either to facilitate rapid conversion to the more common type. Validation appears in its own package developed by Tony Morris and Nick Partridge. It also exists in Jonathan Sterling’s Vinyl package under the name Data.Vinyl.Idiom.Validation.Result. Gabriel Gonzalez has also told me that he’d be happy to add it to his `errors` package if a PR was made. The common use for Validation is to traverse over a structure and accumulate errors throughout it. In other words, failures should not halt the process and we can think of each operation as occurring in parallel. Not only is Validation a good example of an “Applicative without a Monad” its also a very useful practical type. I would like to build a proposal to include Validation in some form in a common package. Despite the misalignment with the name, `transformers` seems like a plausible target, though I fear changes to that package are rarely worth the pain. Suggestions on implementation and target package are welcome. Pending informative feedback, I will try to write a true proposal within 2 weeks. Thanks everyone, Joseph Joseph

10 20

Proposal: Add a few extra members to Foldable and Traversable classes
by David Feuer 21 Sep '14

21 Sep '14

To go along with Herbert Valerio Riedel's moving functions from Foldable and Traversable to Prelude, I realized that `null` and `size` make sense for all Foldables; Reid W. Barton noted that these can have optimized implementations for many containers. He also noted that scanl1 and scanr1 make sense for general Traversables. I therefore propose: Add `null` and `size` to the Foldable class. Default implementations: null = foldr (\_ _ -> False) True size = foldl' (\acc _ -> acc+1) 0 Add `scanl1` and `scanr1` to the Traversable class. Default implementations are a little less simple. David

10 24

Proposal: Use time rather than old-time in directory
by Ian Lynagh 16 Sep '14

16 Sep '14

Hi all, This proposal is to change directory to use the time package rather than the old-time package. This will hopefully be a significant step towards actually making the transition in general. I'm not sure if POSIXTime or UTCTime is the better type to use. Does anyone know? I started off with UTCTime, then switched to POSIXTime as UTCTime didn't have a Show instance. I've since found that actually UTCTime has both Show and Read instances, but they are orphaned. So actually, if UTCTime is the better type then switching back to UTCTime would allow us to fix this comment in hpc: -- We would rather use ClockTime in Mix, but ClockTime has no Read instance and simplify the code slightly. Attached are patches for directory, hpc and ghc. Suggested discussion period: Until 5th Nov 2011. Thanks Ian

14 35