July 2013 - Libraries

Proposal: Strict scanl, scanl1 and mapAccumL
by Bas van Dijk 18 Jul '13

18 Jul '13

Hi, Data.List exports strict versions of foldl an foldl1. I think it should also export these strict versions of scanl, scanl1 and mapAccumL: scanl' :: (a -> b -> a) -> a -> [b] -> [a] scanl' f q ls = q : (case ls of [] -> [] x:xs -> let q' = f q x in q' `seq` scanl f q' xs) scanl1' :: (a -> a -> a) -> [a] -> [a] scanl1' f (x:xs) = scanl' f x xs scanl1' _ [] = [] mapAccumL' :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) mapAccumL' _ s [] = (s, []) mapAccumL' f s (x:xs) = (s'',y:ys) where (s', y ) = f s x (s'',ys) = s' `seq` mapAccumL' f s' xs Is there a good reason they're not included? Discussion deadline: 2 weeks (till Monday 26 November). Regards, Bas

9 18

System.Random - bugs? or am I just confused?
by Hans Georg Schaathun 18 Jul '13

18 Jul '13

Hi all, I have been digging into the System.Random module lately. Initially, I was concerned about the split method, but trying to understand the code and algorithm, there are a couple of other issues that bother me. I hope this is the right forum to ask about them ... I think at least some of them are bugs, but then, there may be some deliberate design choices which I don't see. If there aren't, I guess I will propose a patch. Any opinions? 1. The range of the Standard Generator. stdRange gives a lower bound of 0. As far as I can see, 0 is an impossible value. Should the range not start at 1? 2. randomIvalInteger. One error has already been noted in the comment. Is it not trivial to calculate b based on genRange? Is there some drawback which has prevented such a change? 3. randomIvalInteger again. The drawing of n random numbers, multiplying the ith one by b^i, before summing them all, would make sense to me if the n random numbers had range 0..b-1, and we started the sum at acc=0. As far as I can see, the pseudo-random have range 1..b+1 (assuming the standard generator), and the acc parameter to f starts at 1. Is this a bug? Or what am I missing? 4. A possible error is also indicated by a comment in iLogBase, where iLogBase b b = 2. Should the if-condition i < b be changed to i <= b? Or is it more tricky? Thanks a lot in advance, :-- George

3 2

Proposal: Slim base-5 API package
by Joachim Breitner 18 Jul '13

18 Jul '13

Hi, The problem =========== currently, base is a big beast that mixes a lot of different aspects, from really basic stuff like Data.List to quite specific system libraries like System.Console.GetOpt to gory GHC details such as GHC.Conc.Signal. There are various issues with this: * No implementation of a module included in base is able to use stuff from other libraries, like containers. There are even copies of container code in base. * Changes to the API of obscure modules like GHC.Conc.Signal require version bumps in base, which cause lots of depending packages to upload new version just to change their dependency. * The large expose surface of base makes refactoring like the actual split of the base implementation harder. * Compilers like haste or fay have a hard time providing a proper base, as many of the modules do not make sense in that setting. The suggestion ============== So I’d like to suggest that we turn the base package into a pure API package. This means that there will be no code in the package at all, only re-exports from other packages. The current code can then go into a base-ghc-impl package (or even many packages). Furthermore, the base package is stripped down to a sensible base API. Most, if not all, of the GHC package should go. There are other rather specific modules (Text.Show.Functions, Text.Read.Lex) where I am unsure whether they are useful in base. For such modules we will see if this is a good point to put them in a separate package. Also the module contents can be cleaned up at this point. The result should become base-5, and will hopefully be a more stable base library. „Below“ base-5 we can then wildly split and rearrange stuff, without disturbing our beloved users too much. Code that really needs the removed modules will have to build-depend on the implementing package and hence say „I really need these and I’m willing to pay by having to bump my dependencies more often.“ Way forward =========== If this is seen as mostly desirable here and by the maintainers, i.e. the committee that can become active ;-), the next step would be to identify a good base API. For that, we should study representative code on hackage: What modules from base have been importet, which functions are used. Based on that data I hope it will be clear what a good base is. Does someone have a tool around that can help with that? I guess compiling much of hackage with -ddump-minimal-imports and postprocessing that should work. If base-ghc-impl and base import the same module names (which would make sense), currently a library cannot depend on both libraries. This would be bad, as importing just one module from base-ghc-impl, and even only to test stuff, would require changing all imports (or use package imports). This can be avoided if we can add a feature GHC: Module re-exports. Similar to how GHC does not complain if the same definition is imported via different modules, it should not complain if the same Module is imported via different packages. A package re-export can either be an empty module import and exporting exactly one module, or an entry in the package metadata – but that’s an implementation detail. I have no roadmap with times at hand; maybe someone more knowledgeable of GHC and platform release processes and timings can comment on that. Dangers ======= The whole exercise will only be useful if afterwards, a large fraction of packages can actually use base and just base, and do not have to import the implementing packages directly. Hence the imports study in advance. There are lots of proposals floating around that modify base in a non-trivial manner. For some of them it might make sense to include them when bumping base to 5, but the danger is that there are too many, some of them rather intrusive, that it would hold up this proposal to decide on all of them. Also note that this proposal, if it goes as planned, will _not_ require code changes to _most_ packages. Which is good. Thanks for your attention, and please let us know what you think, Joachim -- Joachim “nomeata” Breitner mail(a)joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata(a)joachim-breitner.de • GPG-Key: 0x4743206C Debian Developer: nomeata(a)debian.org

4 14

Proposal: Add IsString instance for (Maybe a) to base
by Simon Hengel 15 Jul '13

15 Jul '13

Hi, what about adding instance IsString a => IsString (Maybe a) where fromString = Just . fromString It makes specifying optional String/Text/... values more convenient. Here is an example that uses System.Process.shell: Use shell "ls -l" { cwd = "/home/me" } instead of shell "ls -l" { cwd = Just "/home/me" } I'm not yet sure how essential it is. But I somehow can't see any issues with it. So why not? Cheers, Simon

15 22

Proposal: replace readMVar with atomicReadMVar, breaking BC
by Edward Z. Yang 15 Jul '13

15 Jul '13

GHC HEAD recently got a new primitive: atomicReadMVar#, which allows you to read MVars without first taking and then putting back (removing a nasty race where readMVar only works properly when there are no waiting putters). atomicReadMVar behaves differently from readMVar. The key differences are: - An atomicReadMVar op never causes an MVar to become "empty" at any point. This means less programs deadlock now. - An blocked atomicReadMVar is always served by the *first* putMVar to arrive (it cuts to the head of the queue), whereas readMVar obeyed the FIFO ordering. This means this program behaves differently: m <- newEmptyMVar forkIO $ takeMVar m threadDelay 100 forkIO $ print =<< readMVar m {- atomicReadMVar m -} threadDelay 100 putMVar m 1 putMVar m 2 -- readMVar: outputs 2 -- atomicReadMVar: outputs 1 It actually would not be too difficult to add support for atomicReadMVar which *does* respect the FIFO ordering but I don't have a sense when that would be useful. The general feeling Simon and I have is that everyone really wanted to make believe readMVar was atomicReadMVar, and so maybe we should break BC and make readMVar do the right thing. But it is probably worth some discussion, and I entreat you to think about the second point more carefully. Thanks, Edward

13 18

A single general modification function for Map and IntMap proposal
by Nikita Volkov 15 Jul '13

15 Jul '13

There is a list of problems with the current "Map" and "IntMap" modification interfaces: - they are filled with quirky and too specialized functions - they are not consistent in terms of how equally named functions behave: http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data… - they still don't cover some important scenarios of use Because of the above I have very often found myself in requirement for the following function: withItem :: (Ord k) => k -> (Maybe i -> (r, Maybe i)) -> Map k i -> (r, Map k i) withItem k f m = let item = Map.lookup k m (r, item') = f item m' = Map.update (const item') k m in (r, m') It covers all the imaginable scenarios of modification operations: delete, update, replace, - yet it also provides one with ability to extract the modified data and not only. The problem is that this implementation involves a repeated lookup for the same item: first with "lookup", then with "update" - but the "containers" library exposes no functionality to get around that. So I suggest to implement an efficient version of "withItem" in the library. This function turns out to be far more generalized than any of the currently present in the library, so it can become a basic building block for all sorts of modifying functions, including all the already existing ones, e.g.: alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a alter f k = snd . withItem k (\i -> ((), f i)) delete :: Ord k => k -> Map k a -> Map k a delete k = snd . withItem k (const ((), Nothing)) updateLookupWithKey :: (Ord k) => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a) updateLookupWithKey f k = withItem k $ \i -> case i of Just i -> case f k i of Nothing -> (Just i, Nothing) Just i' -> (Just i', Just i') _ -> (Nothing, Nothing) You can see how easy it makes to achieve any sort of specialized functionality. So, besides the evident benefits, this function can also become a replacement for a whole list of confusing specialized ones, thus greatly lightening the library. You might have also noticed how this function is based around the standard "a -> (b, a)" pattern of the "State" monad, thus making it easily composable with it using the "state" and "runState" functions. Summarizing, my suggestions are: 1. Implement an efficient version of "withItem" for lazy and strict versions of "Map" and "IntMap". 2. Change the order of parameters from "lambda -> key" to "key -> lambda". The "updateLookupWithKey" example implementation shows how this change can be benefitial. 3. Begin the deprecation process of the following functions: insertWith, insertWithKey, insertLookupWithKey, adjust, adjustWithKey, update, updateWithKey, updateLookupWithKey, alter. A deadline for discussion is set to 6 weeks. For a formatted version of this message please visit https://github.com/haskell/containers/issues/28.

11 18

Re: Proposal: Add IsString instance for (Maybe a) to base
by Gabriel Gonzalez 14 Jul '13

14 Jul '13

> To play devil's advocate, why? > > What does limiting IsString in this fashion gain anyone? It doesn't > complicate type inference any more than it already is. For any > applicative, there's the trivial instance > > instance (IsString a, Applicative t) => IsString (t a) where > fromString = pure . fromString > > which is conceptually a very simple step and is always total. > > Of course some functors admit other instances. I think some parser > libraries already provide IsString instances as a nice syntax on matching > string literals. A rule like this would invalidate those instances for no > particularly good reason I can see. There is a tension between the "Do what I say" approach to library design and the "Do what I mean" approach where the library guesses at the programmer's intention and tries to succeed at all cost, sometimes failing silently when it guesses wrong. The Haskell development philosophy seems to err on the side of avoiding mistakes, which leads me to favor asking the programmer to be explicit in this particular case and not auto-inserting `Just`s for them. Also, scope creep for type classes like `IsString` makes it more difficult to reason about what their methods mean. These more exotic `IsString` instances dilute the meaning and precision of the original type class. When I wrote a string in a program with `OverloadedStrings` enabled, the meaning used to be: "This is text". Then the meaning became: "This uses text internally, somewhere." As time goes on, I expect the meaning will eventually become: "This is convenient", whatever that means.

5 9

Re: Proposal: fix Enum Double instance
by John Lato 08 Jul '13

08 Jul '13

(apologies, meant this to go to libraries@ also) On Mon, Jul 8, 2013 at 1:03 PM, John Lato <jwlato(a)gmail.com> wrote: > Well, yes. But at least we'd have a library function enumFromStepTo that > works. I suggest that anyone who cares about floating-point precision is > going to be looking for a function with "Step" in the name for this anyway, > so they're likely to find the most useful function first. > > Further I suggest that anyone who uses enumFromThenTo deserves what they > get, particularly if they're using it on a type that doesn't admit a torsor > (and consequently the user is relying upon some implicit compiler-defined > torsor). > > > On Mon, Jul 8, 2013 at 12:39 PM, Edward Kmett <ekmett(a)gmail.com> wrote: > >> Rather that would be the extension required if you wanted to implement >> this as an overloadable method in the class. >> >> Implementing it separately and then wiring up enumFromThenTo in terms of >> it still leaves you with the annoying initial massive cancellation of your >> significand, so you wind up taking very precise steps of the wrong size. ;) >> >> -Edward >> >> On Sun, Jul 7, 2013 at 11:36 PM, Edward Kmett <ekmett(a)gmail.com> wrote: >> >>> Sadly this technically requires a language extension over Haskell >>> 98/2010: ConstrainedClassMethods >>> >>> >>> http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/type-class-extensio… >>> >>> GHC seems to be somewhat lax about requiring that extension on code in >>> practice these days, but it does have implications when it comes to other >>> approaches to implementing a compiler for Haskell. >>> >>> -Edward >>> >>> >>> On Sun, Jul 7, 2013 at 11:18 PM, John Lato <jwlato(a)gmail.com> wrote: >>> >>>> My understanding was that the proposal required enumFromStepTo as a >>>> separate function (i.e. not a class method) with a Num constraint on the >>>> types. So the function wouldn't be available for Ordering or derived Enum >>>> instances unless they also had a Num instance. >>>> >>>> John >>>> >>>> >>>> On Mon, Jul 8, 2013 at 10:46 AM, Edward Kmett <ekmett(a)gmail.com> wrote: >>>> >>>>> There is a pretty big potential problem with this. >>>>> >>>>> Not every type that is enumerable admits a torsor where you can talk >>>>> about forward differences. >>>>> >>>>> What would the enumFromStepTo function mean for, say, Ordering or for >>>>> most derived Enum instances? >>>>> >>>>> -Edward >>>>> >>>>> On Sun, Jul 7, 2013 at 12:17 PM, Edward A Kmett <ekmett(a)gmail.com>wrote: >>>>> >>>>>> +1 from me. >>>>>> >>>>>> The massive cancellation destroying significant figures of >>>>>> significand in enumFromThenTo has always driven me nuts. >>>>>> >>>>>> Sent from my iPhone >>>>>> >>>>>> On Jul 5, 2013, at 8:50 AM, Twan van Laarhoven <twanvl(a)gmail.com> >>>>>> wrote: >>>>>> >>>>>> > Hello All, >>>>>> > >>>>>> > >>>>>> > I would like to make a counterproposal in the Enum Double debate: >>>>>> Instead of deprecating or removing the instances, how about just fixing >>>>>> them? >>>>>> > >>>>>> > A perfect instance for Enum Double is not possible, because >>>>>> arithmetic is inexact. But you can actually get awfully close. I.e. instead >>>>>> of allowing the final value to be at most step/2 past the end, we can allow >>>>>> it to be at most about 2e-16*step past the end. In many practical >>>>>> applications this is close enough to not be a problem. >>>>>> > >>>>>> > >>>>>> > >>>>>> > Now for some more detail on the design: >>>>>> > >>>>>> > * First of all, Haskell's enumFromThenTo is stupid, because >>>>>> calculating step=then-from destroys numerical accuracy. So I will focus on >>>>>> implementing a function enumFromStepTo. You can still implement >>>>>> enumFromThenTo on top of it. But it might also make sense to expose >>>>>> enumFromStepTo. >>>>>> > >>>>>> > * It is possible to write an exact instance for Rational. It is IMO >>>>>> unacceptable that Haskell currently does not use this correct instance. I >>>>>> will use this Rational instance as a baseline for comparison. >>>>>> > >>>>>> > instance EnumFromStepTo Rational where >>>>>> > enumFromStepTo f s t >>>>>> > | s >= 0 && f <= t = f : enumFromStepTo (f + s) s t >>>>>> > | s < 0 && f >= t = f : enumFromStepTo (f + s) s t >>>>>> > | otherwise = [] >>>>>> > >>>>>> > * Writing a loop naively, by recursing with from' = from+step will >>>>>> result in accumulating the error of the addition. On the other hand, >>>>>> Doubles can represent integer numbers exactly up to 2^53, so it is better >>>>>> to use values from+i*step. >>>>>> > >>>>>> > * Assume for simplicity that step>0. The stopping condition will >>>>>> then be of the form from+i*step-to > 0. When this quantity is 0 then the >>>>>> final value should be included, otherwise it shouldn't be. >>>>>> > >>>>>> > * Now for an error analysis. Assume that we start with >>>>>> > f,s,t :: Rational >>>>>> > and call >>>>>> > let f' = fromRational f >>>>>> > let s' = fromRational s >>>>>> > let t' = fromRational t >>>>>> > enumFromThenTo f' s' t' >>>>>> > >>>>>> > The fromRational function rounds a rational number to the nearest >>>>>> representable Double. The relative error in f' is therefore bounded by abs >>>>>> (f-f') ≤ ε * abs f, where ε is the half the maximum distance between two >>>>>> adjacent doubles, which is about 1.11e-16. similarly for s' and t'. the >>>>>> result of an addition or multiplication operation will also be rounded to >>>>>> the nearest representable Double. >>>>>> > >>>>>> > So, the total error in our stopping condition is bounded by >>>>>> > err(f+i*s-t) >>>>>> > ≤ ε * abs f -- representing f >>>>>> > + ε * i * abs s -- representing s, amplified by i >>>>>> > + ε * i * abs s -- error in calculating (*), i * s >>>>>> > + ε * abs (f + i*s) -- error in calculating (+), f + (i*s) >>>>>> > + ε * abs t -- representing t >>>>>> > + ε * abs (f + i*s - t) -- error in calculating (-) >>>>>> > >>>>>> > Note that the last term of the bound is the thing we are bounding. >>>>>> So we can handle that by picking a slightly larger epsilon, eps = ε/(1-ε). >>>>>> > >>>>>> > This leads to the following implementation of enumFromStepTo: >>>>>> > >>>>>> > enumFromStepToEps eps !f !s !t = go 0 >>>>>> > where >>>>>> > go i >>>>>> > | s >= 0 && x <= t = x : go (i+1) >>>>>> > | s < 0 && x >= t = x : go (i+1) >>>>>> > | abs (x - t) < eps * bound = [x] >>>>>> > | otherwise = [] >>>>>> > where >>>>>> > x = f + i * s >>>>>> > bound = abs f + 2 * abs (i * s) + abs t + abs x >>>>>> > >>>>>> > with eps = 1.12e-16 :: Double >>>>>> > or eps = 5.97e-8 :: Float >>>>>> > >>>>>> > I have done extensive experiments with this implementation and many >>>>>> variants, and I believe it will work in all cases. >>>>>> > >>>>>> > Now for enumFromTo, i.e. step=1 we could make a special case, since >>>>>> we know that step is exactly equal to 1, so there is no representation >>>>>> error. We could get rid of the multiplication, and replace i*s by 0 in the >>>>>> error calculation. >>>>>> > >>>>>> > Another issue that remains is enumFromThenTo. If we take >>>>>> > step = then - from >>>>>> > then the relative error in step is bounded by >>>>>> > |step' - step| ≤ ε * (|then| + |from| + |then - from|). >>>>>> > This error gets multiplied by i, so it can unfortunately become >>>>>> quite large. >>>>>> > >>>>>> > I think it would be best if we use the more general >>>>>> > >>>>>> > enumFromStepToEps' !eps !f !s !sErr !t = go 0 >>>>>> > where >>>>>> > go i >>>>>> > | s >= 0 && x <= t = x : go (i+1) >>>>>> > | s < 0 && x >= t = x : go (i+1) >>>>>> > | abs (x - t) < eps * bound = [x] >>>>>> > | otherwise = [] >>>>>> > where >>>>>> > x = f + i * s >>>>>> > bound = abs f + abs (i * s) + abs (i * sErr) + abs t + abs x >>>>>> > >>>>>> > enumFromStepTo f s t = enumFromStepToEps' eps f s s t >>>>>> > enumFromTo f t = enumFromStepToEps' eps f 1 0 t >>>>>> > enumFromThenTo f h t = enumFromStepToEps' eps f (h - f) >>>>>> > (abs h + abs f + abs (h - f)) t >>>>>> > >>>>>> > >>>>>> > I have also looked at what other language implementations do. So >>>>>> far I have found that: >>>>>> > * Octave uses a similar method, with the bound >>>>>> > 3 * double_epsilon * max (abs x) (abs t), >>>>>> > which is less tight than my bound. >>>>>> > see >>>>>> http://hg.savannah.gnu.org/hgweb/octave/file/787de2f144d9/liboctave/array/R… >>>>>> > >>>>>> > * numpy just uses an array with length ceil((to-from)/step) >>>>>> > see >>>>>> https://github.com/numpy/numpy/blob/master/numpy/core/src/multiarray/ctors.… >>>>>> > It therefore suffers from numerical inaccuracies: >>>>>> > $ python >>>>>> > >>> from numpy import arange >>>>>> > >>> notone = 9/7. - 1/7. - 1/7. >>>>>> > >>> notone >>>>>> > 1.0000000000000002 >>>>>> > >>> len(arange(1,1)) >>>>>> > 0 >>>>>> > >>> len(arange(1,notone)) >>>>>> > 1 >>>>>> > >>>>>> > >>>>>> > In summary: >>>>>> > * change Enum Rational to the always correct implementation >>>>>> > * change Enum Double and Enum Float to the almost-always correct >>>>>> implementation propose above. >>>>>> > * (optional) expose the enumFromStepTo function. >>>>>> > >>>>>> > >>>>>> > >>>>>> > Twan >>>>>> > >>>>>> > _______________________________________________ >>>>>> > Libraries mailing list >>>>>> > Libraries(a)haskell.org >>>>>> > http://www.haskell.org/mailman/listinfo/libraries >>>>>> >>>>> >>>>> >>>>> _______________________________________________ >>>>> Libraries mailing list >>>>> Libraries(a)haskell.org >>>>> http://www.haskell.org/mailman/listinfo/libraries >>>>> >>>>> >>>> >>> >> >

1 0

Proposal: Warn when using Enum instance of Float or Double
by harry 08 Jul '13

08 Jul '13

The Enum instances for Float and Double have dubious semantics which cause endless confusion, e.g. http://stackoverflow.com/questions/13203471/the-math-behind-1-0999999999999…, http://stackoverflow.com/questions/9810002/floating-point-list-generator, http://stackoverflow.com/questions/7290438/haskell-ranges-and-floats, http://stackoverflow.com/questions/10328435/how-to-solve-floating-point-num…, and many more. I would therefore like to propose that the usage of an Enum instance of Float or Double generate a compiler warning, such as "The Enum instance of Float is subject to rounding errors". Deadline: 2 weeks. Pedantic question: Should it be the Enum instance _of_ Float or _for_ Float? -- View this message in context: http://haskell.1045720.n5.nabble.com/Proposal-Warn-when-using-Enum-instance… Sent from the Haskell - Libraries mailing list archive at Nabble.com.

12 20

Foldable/Traversable
by harry 01 Jul '13

01 Jul '13

Was there any conclusion on importing Foldable/Traversable into Prelude? The consensus seems to have been mostly in favour, but I can't find any Trac ticket for it. -- View this message in context: http://haskell.1045720.n5.nabble.com/Foldable-Traversable-tp5732253.html Sent from the Haskell - Libraries mailing list archive at Nabble.com.

3 2