January 2017 - Libraries

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

Re: Derived Functor instance for void types
by Ryan Scott 16 Jan '17

16 Jan '17

To be clear, if you have: data V a deriving Functor David is proposing in #13117 [1] that the derived instance use -XEmptyCase instead of the current error-based implementation: instance Functor V where fmap _ x = case x of {} This seems fine and well, but given that #13117 is basically a continuation of another discussion in #7401 [2], I feel like if we're going to tackle the issue of derived instances for empty data declaration, we should solve it for all stock classes. In particular, there are two thorny issues to consider here. What if we have this instead? data V2 deriving Eq What instance should this produce? Reid Barton proposed in #10577 [3] that it should be: instance Eq V2 where a == _ = case a of {} But we have a choice here, since (==) has multiple arguments! The definition could also conceivably be: instance Eq V2 where _ == b = case b of {} Is there a uniform policy we can decide for functions with multiple arguments like this? In fmap, it's unambiguous since there's only one argument of type f a. Another issue to consider is that if we adopted this convention for derived Eq instances for empty datatypes, we'd actually be going against the convention set for Data.Void. As noted in [4], this is the current Eq instance for Void: instance Eq Void where _ == _ = True I'm not proposing that we change this definition, since there are many good reasons to have it this way (see the thread in [5] for Edward Kmett's convincing argument in favor of the current Eq Void instance). Rather, I'm asking if we would be OK with having this discrepancy--that is, deriving Eq for your own Void2 type would produce a different instance. Personally, I'd be fine with it, but I think we should ask for the community's input as well. So sorry to hijack this thread, David, but we really should answer these two questions as well: 1. What do we do in ambiguous cases like derived (==) implementations for empty datatypes? 2. Are we fine with derived instances for empty datatypes sometimes being different than the corresponding instances for Data.Void? Ryan S. ----- [1] https://ghc.haskell.org/trac/ghc/ticket/13117 [2] https://ghc.haskell.org/trac/ghc/ticket/7401#comment:46 [3] https://ghc.haskell.org/trac/ghc/ticket/10577 [4] https://mail.haskell.org/pipermail/libraries/2015-July/025959.html [5] https://mail.haskell.org/pipermail/libraries/2015-July/025965.html

4 13

Re: Derived Functor instance for void types
by Ryan Scott 16 Jan '17

16 Jan '17

And to be clear, if we can resolve all these questions, I'd volunteer to implement the change to `deriving`'s behavior in GHC. Ryan S.

1 0

Derived Functor instance for void types
by David Feuer 16 Jan '17

16 Jan '17

Currently, if you write data V a deriving Functor GHC generates fmap _ _ = error "Void fmap" This seems quite unfortunate, because it loses potentially useful error information: fmap (+ 3) (error "Too many snozzcumbers!") throws "Void fmap", rather than the much more precise "Too many snozzcumbers!" I've opened Trac #13117 to fix this, but I figured I should double check that no one is opposed. David Feuer

3 3

Discussion: should we make liftA2 an Applicative method?
by David Feuer 15 Jan '17

15 Jan '17

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… [2] http://comonad.com/reader/2015/free-monoids-in-haskell/

7 8

Reexport GHC.Integer.Logarithms from base
by Andrew Martin 15 Jan '17

15 Jan '17

The packages integer-simple and integer-gmp each provide a module named GHC.Integer.Logarithms. In both packages, this module exports identical functions. The two useful ones are: 1. integerLog2# 2. integerLogBase# There is a third function wordLog2# that not as helpful since its implementation is trivial. It would be really nice to be able to use the two integer logarithm functions and only incur a dependency on base. The easiest way to accopmlish this would be to reexport the module from base. However, I'm fine with any other approach that ends up making these functions more accessible. Are there good reasons not to do this? Do others feel like this should/shouldn't be done? Thanks for any further input. -Andrew Martin

2 3

Default implementation of bitSize
by Andrew Martin 09 Jan '17

09 Jan '17

The bitSize typeclass method has been deprecated since 4.7. However, library author still have to implement it to avoid a warning. I propose that a default implementation using bitSizeMaybe be added. It would look like this: bitSize x = case bitSizeMaybe x of Nothing -> error "bitSize is deprecated and the type in question does not have a finite bit size" Just a -> a -- -Andrew Thaddeus Martin

2 1

ANN containers 0.5.9.1
by wren romano 08 Jan '17

08 Jan '17

-------------------------------------------- -- containers 0.5.9.1 -------------------------------------------- The containers package contains efficient general-purpose implementations of various basic immutable container types. The declared cost of each operation is either worst-case or amortized, but remains valid even if structures are shared. -------------------------------------------- -- Changes since 0.5.8.1 (2016-08-31) -------------------------------------------- The headline change is adding `merge` and `mergeA` for `Data.IntMap`. The versions for `Data.Map` were introduced in 0.5.8.1, so this change restores parity between the interfaces. With this in place we hope this version will make it into GHC 8.2. Other changes include: * Add instances for `Data.Graph.SCC`: `Foldable`, `Traversable`, `Data`, `Generic`, `Generic1`, `Eq`, `Eq1`, `Show`, `Show1`, `Read`, and `Read1`. * Add lifted instances (from `Data.Functor.Classes`) for `Data.Sequence`, `Data.Map`, `Data.Set`, `Data.IntMap`, and `Data.Tree`. (Thanks to Oleg Grenrus for doing a lot of this work.) * Properly deprecate functions in `Data.IntMap` long documented as deprecated. * Rename several internal modules for clarity. Thanks to esoeylemez for starting this process. * Make `Data.Map.fromDistinctAscList` and `Data.Map.fromDistinctDescList` more eager, improving performance. * Plug space leaks in `Data.Map.Lazy.fromAscList` and `Data.Map.Lazy.fromDescList` by manually inlining constant functions. * Add `lookupMin` and `lookupMax` to `Data.Set` and `Data.Map` as total alternatives to `findMin` and `findMax`. * Add `!?` to `Data.Map` as a total alternative to `!`. * Avoid using `deleteFindMin` and `deleteFindMax` internally, preferring total functions instead. New implementations of said functions lead to slight performance improvements overall. -------------------------------------------- -- Links -------------------------------------------- Hackage: http://hackage.haskell.org/package/containers GitHub: https://github.com/haskell/containers -- Live well, ~wren

1 0