- Libraries - Haskell.org

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

MonadZip for Data.Tree
by David Feuer 08 Jan '17

08 Jan '17

MonadZip doesn't really explain how strict mzipWith and (especially) munzip should be. For example, we could have munzip (Node (a, b) ts) = (Node a as, Node b bs) where (as, bs) = Data.List.unzip (map munzip ts) or we could make some or all of the pattern matches lazy, or we could use something lazier than Data.List.unzip, or we could make everything completely spine-strict (surely unwise). Does anyone have a particular preference, or a particular reason to prefer one choice over others? If not, I think we should go with the simple version above. David Feuer

3 4

Proposal: Add NonEmpty constructors to the Prelude
by Yitzchak Gale 05 Jan '17

05 Jan '17

In continuation of Simon Jakobi's proposal for a small incremental change to the Prelude to make it more conducive to partial-function-free programming, https://mail.haskell.org/pipermail/libraries/2016-December/027496.html and after some encouragement from the community on reddit, I propose adding the basic constructors of NonEmpty to the Prelude: nonEmpty, (:|), and the type constructor NonEmpty. In practice, users of NonEmpty will often still need a qualified import of Data.List.NonEmpty. But having the constructors available in the Prelude will make the use of NonEmpty more common, and will make programming without partial functions feel more natural and standard. Note: This proposal is separate from Simon's and should not interfere with the acceptance of Simon's. But it is related in that it attempts to achieve the same goals. Discussion period: Until the end of the discussion period of Simon's proposal. Thanks, Yitz

7 10

Proposal: merge either into transformers
by Roman Cheplyaka 03 Jan '17

03 Jan '17

I propose to add the sole module of the 'either' package[1], Control.Monad.Trans.Either, to the transformers package. It provides EitherT, a very basic and fundamental data type. The difference between EitherT and ErrorT is that the latter has an Error constraint, which is used to imlement 'fail'. Note that 'either' depends on the 'semigroupoids' and 'semigroup' packages to provide appropriate instances. The proposal is not to add those instances to 'transformers' to avoid additional dependencies. The instances can then be left in the 'either' package or moved to the 'semigroupoids' and 'semigroup' packages respectively. ('semigroupoids' already depends on 'transformers', while 'semigroups' does not). Compared to the 'either' package, Show, Read, Eq and Ord instances will be dropped to keep the code Haskell2010 (those instances require FlexibleInstances, FlexibleContexts, and UndecidableInstances). The patch is attached. [*] [*] against transformers-0.3.0.0, because the darcs version is not buildable (Control/Monad/Signatures.hs is not in the repository). Roman

22 72