- Libraries - Haskell.org

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

Re: Add Zero and One to Data.Functor (mirroring V1, U1)
by Ryan Scott 26 Jan '17

26 Jan '17

You linked to the Trac issue [1], but for the purposes of motivating this proposal, I think it's important that we reiterate why you want this. First of all, I think we should be clear that you're proposing to add these in the modules: * Data.Functor.One * Data.Functor.Zero Right? Not literally "Data.Functor", as the title might mislead you into believing. Also, for a reason why you might want these - there are currently analogs in the GHC.Generics [2] module: * data U1 a = U1 -- isomorphic to One * data V1 a -- isomorphic to Zero But this is an unfortunate situation, since I'd rather not recommend that folks import a generics library to use what should be general-purpose datatypes. Now, as for the proposal itself: * I'm weakly +1 in favor of Zero. I think it'd be nice to have a proper * -> * counterpart to Void in base (that isn't V1, obviously). * I'm weakly -1 in favor of One, simply because we already have Data.Proxy, which came first. Ryan S. ----- [1] https://ghc.haskell.org/trac/ghc/ticket/13177 [2] http://hackage.haskell.org/package/base-4.9.1.0/docs/GHC-Generics.html

4 4

Add Zero and One to Data.Functor (mirroring V1, U1)
by Baldur Blöndal 26 Jan '17

26 Jan '17

Deadline of 2 weeks. Original discussion: ⁽¹⁾ data Zero a data One a = One Same definitions as in ‘trivia’ package,⁽²⁾ if a consensus is reached we can update the documentation for Free:⁽³⁾ “Free Zero” is isomorphic to Identity. “Free One” is isomorphic to Maybe. ⁽¹⁾ https://ghc.haskell.org/trac/ghc/ticket/13177 ⁽²⁾ https://hackage.haskell.org/package/trivia ⁽³⁾ https://hackage.haskell.org/package/free-4.12.4/docs/Control-Monad-Free.html

2 1

Proposal: Introduce GHC.TypeNats module with natVal :: forall n proxy. KnownNat n => proxy n -> Natural
by Oleg Grenrus 24 Jan '17

24 Jan '17

Currently we have in the GHC.TypeLits module natVal :: forall n proxy. KnowNat n => proxy n -> Integer However, the result integer is never negative. Numeric.Natural module is in base since base-4.8.0.0. --- I propose that we introduce new module GHC.TypeNats with natVal and natVal' natVal :: forall n proxy. KnownNat n => proxy n -> Natural and natVal' :: forall n. KnownNat n => Proxy# n -> Natural and other KnownNat related terms and type families. --- This change would propagate to give more precise type to someNatVal: someNatVal :: Natural -> SomeNat which is currently someNatVal :: Integer -> Maybe SomeNat --- The alternative would be to change the types in GHC.TypeLits, but - it would be breaking change - hard to shim (where new module is implementable for older base, in e.g. base-compat) - we lose opportunity to separate Nat and Symbol data kinds --- Additionally we'd deprecate the GHC.TypeLits natVal, natVal' and someNatVal --- As related "nice to know", `Nat` and `Natural` "agree" on negation: > (1 - 2) :: Natural *** Exception: arithmetic underflow > natVal (Proxy :: Proxy (1 - 2)) <interactive>:9:1: error: • No instance for (KnownNat (1 - 2)) arising from a use of ‘natVal’ • In the expression: natVal (Proxy :: Proxy (1 - 2)) In an equation for ‘it’: it = natVal (Proxy :: Proxy (1 - 2)) --- The change is quite straightforward to do, and I'm willing to implement it even for GHC 8.2 Oleg Grenrus

3 3

Discussion: traversing roots and leaves
by David Feuer 23 Jan '17

23 Jan '17

My proposal to move liftA2 into the Applicative class should help get fmaps out of internal nodes in traverse implementations. But there are still two trouble spots: 1. The smaller trouble spot is at the root, when dealing with newtype wrappers. For example, the simplest way to write traverse for Data.Sequence.Seq would be instance Traversable Seq where traverse f (Seq xs) = Seq <$> traverse f xs The extra fmap may not be free. Today, the only fix is to manually inline the definition of the underlying traversal and manually fuse the fmaps. It works, but it's gross! We could work around this easily using an extra Traversable method: mapTraversed :: Applicative f => (t b -> r) -> (a -> f b) -> t a -> f r but that wouldn't help with the larger problem below. 2. Leaves are really painful. Data structures that store at most one element per leaf make obvious traversals expensive. For example, in Data.Map, the obvious implementation would be instance Traversable (Map k) where traverse _ Tip = pure Tip traverse f (Bin s k v l r) = liftA3 (Bin s k) (f v) (traverse f l) (traverse f r) The trouble is that we would generate a slew of `pure Tip`s that we'd then have to combine. For instance, (Bin 1 k v Tip Tip) would give liftA3 (Bin 1 k) (f v) (pure Tip) (pure Tip) Today we work around this by looking ahead at the children of the element we're considering, so we get fmap (\v' -> Bin 1 k v' Tip Tip) (f v) instead, which is still pretty lousy but better. It makes me rather sad to have to write disgustingly ugly Traversable instances just to avoid silly performance issues like this. Does anyone have an idea for fixing (2), and ideally simultaneously taking care of (1)? Thanks, David Feuer

2 2

Proposal: make liftA2 an Applicative method?
by David Feuer 23 Jan '17

23 Jan '17

Since most of the feedback on my suggestion has been positive, I figured I'd upgrade it to an official proposal. Let's do this! On Jan 14, 2017 4:49 PM, "David Feuer" <david.feuer(a)gmail.com> wrote: Right now, we define liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c liftA2 f x y = f <$> x <*> y For some functors, like IO, this definition is just dandy. But for others, it's not so hot. For ZipList, for example, we get liftA2 f (ZipList xs) (ZipList ys) = ZipList $ zipWith id (map f xs) ys In this particular case, rewrite rules will likely save the day, but for many similar types they won't. If we defined a custom liftA2, it would be the obviously-efficient liftA2 f (ZipList xs) (ZipList ys) = ZipList $ zipWith f xs ys The fmap problem shows up a lot in Traversable instances. Consider a binary leaf tree: data Tree a = Bin (Tree a) (Tree a) | Leaf a The obvious way to write the Traversable instance today is instance Traversable Tree where traverse _f Tip = pure Tip traverse f (Bin p q) = Bin <$> traverse f p <*> traverse f q In this definition, every single internal node has an fmap! We could end up allocating a lot more intermediate structure than we need. It's possible to work around this by reassociating. But it's complicated (see Control.Lens.Traversal.confusing[1]), it's expensive, and it can break things in the presence of infinite structures with lazy applicatives (see Dan Doel's blog post on free monoids[2] for a discussion of a somewhat related issue). With liftA2 as a method, we don't need to reassociate! traverse f (Bin p q) = liftA2 Bin (traverse f p) (traverse f q) The complication with Traversable instances boils down to an efficiency asymmetry in <*> association. According to the "composition" law, (.) <$> u <*> v <*> w = u <*> (v <*> w) But the version on the left has an extra fmap, which may not be cheap. With liftA2 in the class, we get a more balanced law: If for all x and y, p (q x y) = f x . g y, then liftA2 p (liftA2 q u v) = liftA2 f u . liftA2 g v [1] https://hackage.haskell.org/package/lens-4.15.1/docs/ Control-Lens-Traversal.html#g:11 [2] http://comonad.com/reader/2015/free-monoids-in-haskell/

3 2

Adding foldMap implementation to instance Foldable Maybe
by Eric Mertens 19 Jan '17

19 Jan '17

Hello, Independently of a blog post I just noticed tonight on reddit, http://www.snoyman.com/blog/2017/01/follow-up-mapm <http://www.snoyman.com/blog/2017/01/follow-up-mapm> I observed a stack overflow in some code I was working with due to a recursive call inside the function argument of for_ The code was a more complicated version of: go = for_ someMaybe $ \m -> m >> go It was wrong in thinking that this could be efficient because there’s an extra operation to set the result to a (). I thought I might try working around this with the following code. for__ :: (Applicative f, Foldable t) => t a -> (a -> f ()) -> f () for__ xs f = unApp (foldMap (coerce f) xs) newtype App f = App { unApp :: f () } instance Applicative f => Monoid (App f) where mempty = App (pure ()) mappend (App x) (App y) = App (x *> y) Unfortunately the instance for Foldable for Maybe does not provide an implementation of foldMap, it only provides foldl and foldr. This means that the derived foldMap implementation attempts to mappend an extra mempty because the default implementation of foldMap is <>foldMap <http://hackage.haskell.org/package/base-4.9.1.0/docs/src/Data.Foldable.html…> <>f <http://hackage.haskell.org/package/base-4.9.1.0/docs/src/Data.Foldable.html…> = foldr <http://hackage.haskell.org/package/base-4.9.1.0/docs/src/Data.Foldable.html…> (mappend <http://hackage.haskell.org/package/base-4.9.1.0/docs/src/GHC.Base.html#mapp…> . <http://hackage.haskell.org/package/base-4.9.1.0/docs/src/GHC.Base.html#.> f <http://hackage.haskell.org/package/base-4.9.1.0/docs/src/Data.Foldable.html…>) mempty <http://hackage.haskell.org/package/base-4.9.1.0/docs/src/GHC.Base.html#memp…> With an explicit implementation of foldMap for the Maybe type (and maybe there are others that we’ve missed, for__ above can be stack efficient. So I propose that we add an explicit implementation of foldMap to the Foldable Maybe instance foldMap _ Nothing = mempty foldMap f (Just x) = f x Best regards, Eric Mertens

2 1