- Libraries - Haskell.org

What top-level names are “allocated”?
by Wolfgang Jeltsch 17 Feb '17

17 Feb '17

Hi! When uploading a new version of grapefruit-frp yesterday, I got the following warning from cabal-install: > Exposed modules use unallocated top-level names: FRP This made me wonder which top-level names are actually “allocated”. I tried to find this out from the Cabal sources, but the GitHub search functionality revealed no occurrences of the word “unallocated”. Regarding my concrete case, I think it would be good to change “FRP” to “Reactive”, which is what Reactive Banana is using, for example. However, is “Reactive” an “allocated” top-level name? All the best, Wolfgang

5 5

Proposal: Add a Void1 :: * -> * type to base
by Michael Walker 15 Feb '17

15 Feb '17

Hi, Recently I found myself in need of a type like Void, but taking a type parameter, so I wrote up a fairly simple implementation inspired by Data.Void: {-# LANGUAGE DeriveDataTypeable #-} {-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE EmptyCase #-} {-# LANGUAGE StandaloneDeriving #-} data Void1 a deriving Generic deriving instance Data a => Data (Void1 a) instance Ix (Void1 a) where range _ = [] index _ = absurd1 inRange _ = absurd1 rangeSize _ = 0 instance Typeable a => Exception (Void1 a) instance Eq (Void1 a) where _ == _ = True instance Ord (Void1 a) where compare _ _ = EQ instance Read (Void1 a) where readsPrec _ _ = [] instance Semigroup (Void1 a) where a <> _ = a instance Show (Void1 a) where show = absurd1 instance Functor Void1 where fmap _ = absurd1 instance Foldable Void1 where foldMap _ = absurd1 instance Traversable Void1 where traverse _ = absurd1 absurd1 :: Void1 a -> b absurd1 v = case v of {} (If we step outside the realm of base, this type is also a Contravariant and a Comonad) I left this sitting alone in a Utils module until last night when I saw someone ask in #haskell if there was "a Void1 type defined in some central place". So, in case this is of more general interest, I propose that a module Data.Functor.Void be added to base. Another colour to paint this bikeshed would be "VoidF", rather than "Void1". Also, this could be added to Data.Void rather than be a new module, but I think it's more sensible to include in the Data.Functor hierarchy, perhaps with a re-export from Data.Void. Discussion period: 2 weeks (ending Wed, 1st March) -- Michael Walker (http://www.barrucadu.co.uk)

3 2

Discussion: Implementation of fromList for Data.Set and Data.Map
by David Feuer 12 Feb '17

12 Feb '17

Currently, the implementations of fromList for Data.Set and Data.Map try to take advantage of inputs with some prefix in strictly increasing order. It uses the fast (O (n)) fromDistinctAscList algorithm for the strictly ascending prefix, and then falls back on the slower (O (n log n)) naive algorithm for the rest. For Data.Set, this works roughly like the implementation sketched at the bottom of this message. This whole thing strikes me as a bit odd: changing just the first element of the input list can have a substantial impact on the overall performance. In my opinion, there are two reasonable ways to implement this function: 1. Don't bother to try to take advantage of preexisting ordering. This is the simplest option, and will probably be fastest for lists with little preexisting order. 2. Try to take advantage of sorted ascending and descending "runs". A simple version would be to break up the input list into ascending and descending segments (merging duplicates on the fly), use fromDistinctAscList or fromDistinctDescList to convert each segment, and combine the segments using set unions. This option will be slower for totally unsorted lists, but should degrade much more gradually than the current algorithm as disorder is added. Wren suggests that there may be other variations on the same theme that we could consider. Should we A. Switch to 1 (and offer 2 by another name) B. Switch to 2 (and offer 1 by another name?) C. Leave fromList alone and offer 2 by another name Note that option 1 can be implemented quite easily outside the library using insert and foldl'; option 2 is not something users should be expected to write themselves. If we add names, what should those be? Thanks, David Feuer Current implementation sketch: fromList :: Ord a => [a] -> Set a fromList xs = foldl' (flip insert) sortedSet unsortedList where sortedSet = fromDistinctAscList sortedList (sortedList, unsortedList) = spanStrictlyAscending xs spanStrictlyAscending [] = ([], []) spanStrictlyAscending (x : xs) = x : go x xs where go prev (n : ns) | prev < n = first (n :) $ go n ns go _ ns = ([], ns)

4 5

Proposal: Make minimumBy and maximumBy go through foldl1
by David Laing 09 Feb '17

09 Feb '17

Hi all, I'm proposing that the implementations of minimumBy and maximumBy be changed from using foldl1 to foldr1. I found this in a GHC trac ticket[0] labelled 'Newcomer' that has more details / discussion on that. The points that stand out to me are: - the Haskell report says that those methods should be implemented in terms of foldl1 (although as instance methods of Foldable there might be some wiggle room there) - it helps solves a space leak (which at first glance feels like it might be a more common problem than the options that foldl1 removes) - from the discussion on the ticket, it seemed to be an agreeable middle ground As a side note: there have been a few proposals in the past to switch these functions to use foldl', which seemed to have stalled. I don't know what the etiquette is around bringing up minor variations on old proposals again, so I apologise if I've breached some kind of protocol here. Although I guess I've already breached one protocol by pushing a patch to Phabricator for review without getting sign-off from the Core Libraries Committee, so at least I'm being even handed with my clumsiness :) Cheers, Dave [0] https://ghc.haskell.org/trac/ghc/ticket/10830

6 8

Announcing containers 0.5.8.2, 0.5.9.2, and 0.5.10.1
by David Feuer 06 Feb '17

06 Feb '17

I had not planned to make any additional releases before GHC 8.2, but bugs forced my hand. In particular, Tom Smalley discovered major bugs in Data.IntMap.restrictKeys and Data.IntMap.withoutKeys. A mistake I made adding those functions to the test suite prevented the problem from being discovered. This affects both 0.5.8.1 and 0.5.9.1, both of which are now deprecated. I believe both the functions and the test suite are now working as intended. In a less frightening bug fix, Ryan Scott fixed a discrepancy between the Show1 instance for Data.Tree and its Show instance. This affected version 0.5.9.1. I also fixed misdirected Haddock links in 0.5.9.1. Version 0.5.10.1 comes with one new feature: Data.Sequence has a MonadZip instance. Thanks also to Simon Jakobi for removing the meaningless stability annotations. David Feuer

1 0

minor broken link in binary submodule
by Takenobu Tani 06 Feb '17

06 Feb '17

Dear libraries, I'm reporting about minor broken link in source comment. There is a broken link in `libraries/binary/src/Data/Binary/Get.hs`. --- <http://www.haskell.org/ghc/docs/latest/html/users_guide/ pragmas.html#unpack-pragma> +-- <http://www.haskell.org/ghc/docs/latest/html/users_guide/ glasgow_exts.html#unpack-pragma> Regards, Takenobu

1 0

Selection Monad
by Jakub Daniel 02 Feb '17

02 Feb '17

Hello, I apologize in case this is not the right place to bring this question/proposal up. Some time ago I stumbled upon the Selection Monad [1] (also referred to as Search from the search package on hackage). Its relation to the Continuation Monad and the usefulness demonstrated in [1] made me wonder whether it would be nice to include Selection Monad in the core libraries along the Continuation Monad (in mtl and transformers) with all the business of selections attaining continuations. I can imagine the pattern to be too little recognised to justify such an addition, yet the theoretical connection to the Continuation Monad seems to be an interesting one and worth being addressed. Best, Jakub Daniel [1] Jules Hedges. *Monad transformers for backtracking search*. In *Proceedings of MSFP 2014. *https://arxiv.org/abs/1406.2058

3 3

Random Number Update
by Dominic Steinitz 31 Jan '17

31 Jan '17

I wanted to give an update on the status of random numbers in Haskell. 1. It is well known that the random number generator package https://hackage.haskell.org/package/random gives unexpected results. 2. Most people do *not* use it. I believe https://hackage.haskell.org/package/mwc-random is a popular choice but developers are free to use e.g. Mersenne Twister, PCG (Permuted Congruential Generator), TF (ThreeFish) and many others. 3. Approximately 2 years, I made a proposal to replace the algorithm within random (https://hackage.haskell.org/package/random) with that used by tf-random (https://hackage.haskell.org/package/tf-random) which is used by QuickCheck. In summary, the response to this was that someone should do more research with the result that nothing happened. 4. In the meantime, random (https://hackage.haskell.org/package/random) is *no longer* a core library. It's just a library with the same status as e.g. mwc-random. However, it has one difference: it uses the name for its module: "System.Random". Other RNGs use "System.Random.MWC", "System.Random.PCG", "System.Random.Mersenne" etc. As a maintainer of random (https://hackage.haskell.org/package/random) my proposal now is to deprecate all of it. I am not clear what the policy is on namespace usage. Could every RNG use the module name "System.Random"? Or is this somehow reserved? If the latter then I propose that *nothing* uses this name and that all RNGs should add a suffix indicating which algorithm they use. I note that the Haskell Platform contains tf-random so users of this will still be able to generate (better) random numbers. If someone comes along in the future, as I hope they do, and implements e.g. Guy Steele's splitmix algorithm then this can occupy the name "System.Random.Splitmix" and have the package name "random-splitmix". The advantages of doing this are: 1. Neophyte (and experienced) Haskellers do not accidentally use an RNG which gives unexpected results. 2. No-one will any longer be able to write blogs or papers about this embarrassing aspect of Haskell. I believe the co-maintainer of random (https://hackage.haskell.org/package/random) Carter Schonwald, has a different view on this matter but it is best he speaks for himself rather than me imperfectly trying to reflect his thinking. Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com

11 13

Win32 non-backwards compatible API change
by Tamar Christina 27 Jan '17

27 Jan '17

Hi All, I want to revive and push forward a change first proposed in 2014 for an API change in the Win32 package. The discussion at that time took place here https://github.com/haskell/win32/issues/24 In short, In the Windows API it is common that when a function accepts a pointer to something, that NULL also be valid and defaults to some action. Such an example is the FindWindow call. https://msdn.microsoft.com/en-us/library/windows/desktop/ms633499(v=vs.85).… HWND WINAPI FindWindow( _In_opt_ LPCTSTR lpClassName, _In_opt_ LPCTSTR lpWindowName ); In this case, both the ClassName and the WindowName are allowed to be NULL. The Haskell binding to this function is findWindow :: String -> String -> IO (Maybe HWND). So we've lost the ability to use the default parameters. The proposal is to change such functions to accept Maybe: findWindow :: String -> String -> IO (Maybe HWND) becomes findWindow :: Maybe String -> Maybe String -> IO (Maybe HWND) Which also would more accurately match the original API. This is of course a backwards incompatible change. Any objections to this change? Thanks, Tamar

3 4

Re: Random Number Update
by Dominic Steinitz 26 Jan '17

26 Jan '17

I’ll try and address the points. 1. I proposed a low cost solution as advocated by Sven and Henrik about 2 years ago, that of using tf-random. This was rejected because apparently better RNGs might exist. Now as we all know there is no such thing as the best RNG. My reasoning for tf-random was that if it were good enough for QuickCheck then it would certainly be good enough for naive users. A case of the best driving out the good? Not that best exists in this case. 2. QuickCheck were bitten very hard! 3. > Prelude> import System.Random > Prelude System.Random> let dieRoll = fst . randomR (1,6) . mkStdGen :: Int -> Int > Prelude System.Random> map dieRoll [1..20] > [6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6] 4. In addition to the problems adumbrated above, random also has a range > Prelude System.Random> newStdGen >>= return . genRange > (1,2147483562) which makes it fail even testu01’s SmallCrush if used naively. random *may* work in certain cases but I would strongly advise against using it when there are so many other packages without the above problems. I would also add that for e.g. MCMC it is often very hard to see if something is working or not working because of the Monte Carlo noise; something apparently working does not necessarily validate a particular RNG. I can’t say I agree with the reasoning that it is better to carry on using something that could be giving incorrect results silently rather than breaking things so that people can take action. Anyhow as I have already said I feel I have done my bit for the Haskell Community. I agree with Carter that this is out of scope for the Core Libraries Committee. I wish you all luck and will step down from being maintainer. > On 25 Jan 2017, at 11:26, libraries-request(a)haskell.org <mailto:libraries-request@haskell.org> wrote: > > Send Libraries mailing list submissions to > libraries(a)haskell.org <mailto:libraries@haskell.org> > > To subscribe or unsubscribe via the World Wide Web, visit > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries> > or, via email, send a message with subject or body 'help' to > libraries-request(a)haskell.org <mailto:libraries-request@haskell.org> > > You can reach the person managing the list at > libraries-owner(a)haskell.org <mailto:libraries-owner@haskell.org> > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Libraries digest..." > > > Today's Topics: > > 1. Re: Selection Monad (Jakub Daniel) > 2. Add Zero and One to Data.Functor (mirroring V1, U1) > (Baldur Blöndal) > 3. Re: Random Number Update (Sven Panne) > 4. Re: Random Number Update (Henning Thielemann) > 5. Re: Random Number Update (Andreas Abel) > 6. Re: Random Number Update (Henrik Nilsson) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Tue, 24 Jan 2017 17:23:58 +0000 > From: Jakub Daniel <jakub.daniel(a)gmail.com <mailto:jakub.daniel@gmail.com>> > To: Eric Mertens <emertens(a)gmail.com <mailto:emertens@gmail.com>> > Cc: libraries(a)haskell.org <mailto:libraries@haskell.org> > Subject: Re: Selection Monad > Message-ID: > <CACaCNTSj5T0GnGkWgk_VO8vaL4dZYao16QUTCvYMXvsAyUw1oQ(a)mail.gmail.com <mailto:CACaCNTSj5T0GnGkWgk_VO8vaL4dZYao16QUTCvYMXvsAyUw1oQ@mail.gmail.com>> > Content-Type: text/plain; charset="utf-8" > > Hi Eric, > > Just to clarify, my question was not about endorsing another library but > rather extending the ones currently maintained by the committee with > definition of a notion closely related to what is already contained in the > libraries. It just so happens that Edward Kmett implemented the notion in a > standalone library. However to me it does not make much sense to include > ContT but not SelT (currently under the name Search) in the core libraries, > despite their connection. I understand if this does not change the answer > though. > > Best Regards, > Jakub Daniel > > > > On Tue, 24 Jan 2017 at 17:39 Eric Mertens <emertens(a)gmail.com <mailto:emertens@gmail.com>> wrote: > >> Hi Jakub, >> >> The core libraries committee helps maintain libraries that are already >> critical to the Haskell ecosystem. It doesn’t select new libraries to be >> recommended to users. It’s possible that the search package is a hidden gem >> that more people need to know about. To accomplish that people will need to >> write software using it, market it with blog posts, and bring it up in >> discussions. >> >> Best Regards, >> Eric Mertens >> >> On Jan 24, 2017, at 5:57 AM, Jakub Daniel <jakub.daniel(a)gmail.com <mailto:jakub.daniel@gmail.com>> wrote: >> >> Hello, >> >> I apologize in case this is not the right place to bring this >> question/proposal up. Some time ago I stumbled upon the Selection Monad [1] >> (also referred to as Search from the search package on hackage). Its >> relation to the Continuation Monad and the usefulness demonstrated in [1] >> made me wonder whether it would be nice to include Selection Monad in the >> core libraries along the Continuation Monad (in mtl and transformers) with >> all the business of selections attaining continuations. I can imagine the >> pattern to be too little recognised to justify such an addition, yet the >> theoretical connection to the Continuation Monad seems to be an interesting >> one and worth being addressed. >> >> Best, >> >> Jakub Daniel >> >> [1] Jules Hedges. *Monad transformers for backtracking search*. In *Proceedings >> of MSFP 2014. *https://arxiv.org/abs/1406.2058 <https://arxiv.org/abs/1406.2058> >> >> _______________________________________________ >> Libraries mailing list >> Libraries(a)haskell.org <mailto:Libraries@haskell.org> >> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries> >> >> >> >

3 2