- Libraries - Haskell.org

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

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