June 2016 - Libraries

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

Proposal: add liftA4 and liftA5 to match liftM4 and liftM5
by David Feuer 15 Jul '16

15 Jul '16

Since Applicative is supposed to be important now, I figure we should get these in.

12 33

Proposal for containers: Add 'lookup' function to Data.Set
by Nicolas Godbout 15 Jul '16

15 Jul '16

WHAT It is proposed to add a ‘lookup' function on 'Set' in the "containers" package. Feedback during the next two weeks is welcome. The function > lookup :: Ord a => a -> Set a -> Maybe a is almost indentical to the 'member' function but, in addition, returns the value stored in the set. WHY The point of this proposal is to facilitate program-wide data sharing. The 'lookup' function gives access to a pointer to an object already stored in a Set and equal to a given argument. The 'lookup' function is a natural extension to the current 'lookupLT', 'lookupGT', 'lookupLE' and 'lookupGE' functions, with obvious semantics. Example use case: In a parser, the memory footprint can be reduced by collapsing all equal strings to a single instance of each string. To achieve this, one needs a way to get a previously seen string (internally, a pointer) equal to a newly parsed string. Amazingly, this is very difficult with the current "containers" library interface. One current option is to use a Map instead, e.g., 'Map String String' which stores twice as many pointers as necessary. HOW The git pull request at https://github.com/haskell/containers/pull/291 contains the straight-forward implementation of the 'lookup’ function on 'Set', with test cases, as a patch against the current containers master branch. Salutations, Nicolas.

16 32

Notification: adding adjust' to Data.Sequence (rage on!)
by David Feuer 30 Jun '16

30 Jun '16

This is not a proposal. I know that for reasons I don't know, the decision was made to move extra-strict functions for the other containers into separate .Strict modules. I greatly dislike the result of that decision (both from the API standpoint and especially from a maintenance standpoint), but I'm not arguing to change that. However, I am adding an extra-strict function to Data.Sequence, with the following non-negotiable semantics: adjust' f i xs = case xs !? i of Nothing -> xs Just x -> let !x' = f x in update i x' xs This will provide an efficient way to adjust a sequence element without risking thunk chains and memory leaks. I'm sure some people will be angry. I just wanted to make sure no one says I snuck this in behind their back.

1 0

User-friendly access to SmallArray# and SmallMutableArray#
by David Feuer 28 Jun '16

28 Jun '16

The only user-friendly wrappers I can find for SmallArray# and SmallMutableArray# are in Data.Discrimination.Internal.SmallArray in the discrimination package. What are the chances that we could get something like that in the array package, or possibly some other GHC boot package? I can't use discrimination in containers! David

3 4

How bad would it be for containers to depend on transformers?
by David Feuer 23 Jun '16

23 Jun '16

Currently, containers does not depend on transformers, so it has to duplicate its functionality or just do without. Since transformers is also a GHC boot package, I believe it should be feasible to make containers depend on it. To what extent would that reduce parallelizability of GHC builds or otherwise make people mad? David

2 1

Proposal: add ReadPrec-based functions to Read1/Read2
by Ryan Scott 21 Jun '16

21 Jun '16

GHC 8.0 added the Data.Functor.Classes module [1] to base, and with it the Read1 and Read2 typeclasses. The current definition of Read1 is this: class Read1 f where liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a) liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [f a] There's a pretty big problem with this definition: it uses ReadS (a synonym for String -> [(a, String)]). This sort of parser is very slow (the docs even admit as such [2]), and moreover, the actual Read typeclass on which Read1 is based tries to avoid using it whenever possible. The Read typeclass has this definition currently: class Read a where readsPrec :: Int -> ReadS a readList :: ReadS [a] readPrec :: ReadPrec a readListPrec :: ReadPrec [a] Where ReadPrec is a much more efficient parser datatype. When deriving Read instances, GHC defines them in terms of readPrec, and gives the other methods default definitions that leverage readPrec. For the sake of consistency, I propose adding analogous methods to Read1 and Read2 that use the ReadPrec datatype. For example, here is how I would change Read1: class Read1 f where liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a) liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [f a] liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (f a) liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [f a] And similarly for Read2. Here is a full gist [3] with a sketch of what the new Read1/Read2 definitions would look like, including what the default definitions of the other methods would be. Ryan S. ----- [1] http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Functor-Classes.h… [2] http://hackage.haskell.org/package/base-4.9.0.0/docs/Text-ParserCombinators… [3] https://gist.github.com/RyanGlScott/7cdd11d6aa878e4229acf1a682beb1fc

4 3

bit sets in IntSet vs. Integer
by Henning Thielemann 20 Jun '16

20 Jun '16

In my set-cover package I make extensive use of bit vectors. I tested both IntSet and Integer for this purpose. In GHC-7.4.2 Integer was visibly faster than IntSet, but in GHC-7.8.4 and later, IntSet clearly wins over Integer. I guess this can be attributed to IntSet using BitMaps at the leaves since containers-0.5. However, on a 64-bit machine a BitMap is a Word64. I wondered whether we could get further speedup by using a vector type. E.g. AVX processors could perform bit manipulations on 256 bit words. Do the bit operations on Integer make use of vector instructions?

3 9

ANN: eccrypto, aka Hecc, hF2
by Marcel Fourné 15 Jun '16

15 Jun '16

Dear Haskell Community! It was a long~ish time ago I released hecc[1], which had an unfortunate but funny (to me) name, later together with hF2[2]. Since I have neither released hyperelliptic curve crypto support, nor my pairing based crypto, a generalising change in names would be in order. Today I am releasing eccrypto[3], which contains the code of both (to allow easier refactoring of new ideas) and something new: A pure Haskell, timing-attack resistant Ed25519[4] implementation! ...well, a very rough one at least. The code is not "done", gives wrong results, is _very_ slow, but it might serve as reading material as well as a primer what I plan to do in the future. I do not plan to add embedded C or assembler code, but plan to make the code comparatively fast to some common implementations as well as timing attack resistant (see: [5]), even if it will never be as fast as the best code used in contemporary benchmarks. Sadly, due to health issues, I am not able to work on said code and have not been for a time longer than I care to admit. All comments are welcome, but I will not be able to guarantee answers. ;) Best of wishes to a thriving community, Marcel Fourné [1]: https://hackage.haskell.org/package/hecc [2]: https://hackage.haskell.org/package/hF2 [3]: https://hackage.haskell.org/package/eccrypto [4]: https://ed25519.cr.yp.to/ [5]: https://mail.haskell.org/pipermail/haskell-cafe/2015-February/118213.html

1 0

Proposal: add fromRight and fromLeft to Data.Either
by Anton Felix Lorenzen 13 Jun '16

13 Jun '16

When working with Either, I am often missing two simple functions: fromRight :: Either a b -> b fromLeft :: Either a b -> a It has been implemented a couple of times: http://hayoo.fh-wedel.de/?query=fromRight But I don't want to depend on yet another library for such a basic function. Could it be added? Anton

13 14

Re: Request: Add sortOn to Data.Sequence
by David Feuer 11 Jun '16

11 Jun '16

I think thIs is an interesting idea, generally. There seem to be two situations that may call for separate functions. If the "key" type can be stored in an unboxed mutable array, then it seems likely desirable to sort using such an array. Otherwise, we can use the existing sortBy as suggested. On Jun 10, 2016 12:30 PM, "Alan Isaac" <alan.isaac(a)gmail.com> wrote: REQUEST ------- The request is to add `sortOn` to Data.Sequence. `sortOn f` would be equivalent to `sortBy . comparing f`, but would offer a performance advantage by using a Schwartzian transform to only evaluate `f` once for each element in the input sequence. BACKGROUND ---------- Adding `sortOn` to `Data.List` was proposed at least as early as 2008: http://www.haskell.org/pipermail/libraries/2008-October/010797.html It was added in 2014, in response to this feature request: https://ghc.haskell.org/trac/ghc/ticket/9004 RATIONALES ---------- - convenience - performance: faster than `sortBy` - safety: encourages (although does not require) reliance on existing instances of Ord - interface consistency (specifically, when comparing to Data.List) Comment: it is certainly possible to pick at each of these rationales. See the discussion here: http://stackoverflow.com/questions/37691898/why-is-sortby-so-oddly-unconstr… SCOPE ----- Introduces no new dependencies except possibly on `Data.Ord.comparing`. SOLUTIONS ----------- The implementation in Data.List is:: sortOn :: Ord b => (a -> b) -> [a] -> [a] sortOn f = map snd . sortBy (comparing fst) . map (\x -> let y = f x in y `seq` (y, x)) An analogous implementation is possible for Data.Sequence. However, this request does not propose a specific implementation. WHAT MIGHT BREAK ---------------- No anticipated breakage. _______________________________________________ Libraries mailing list Libraries(a)haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

2 1

foldl' semantic change
by David Feuer 11 Jun '16

11 Jun '16

The semantics of foldl' for lists were changed between base 4.7 and base 4.8. Specifically, foldl' became strict in the initial value of its accumulator. I opened http://ghc.haskell.org/trac/ghc/ticket/12173 to report this. The change was entirely accidental, according to Joachim Breitner. However, Duncan Coutts indicated he is pleased with the change. I don't personally have a dog in this race, but I feel very strongly about three things: 1. The strictness should be fully documented, both in Haddock and the next Haskell Report (the Haskell 2010 Report does not go into sufficient detail to support either choice). 2. There should be *one* meaning of foldl' in base. Thus the default Foldable instance should match the ones for lists and arrays. 3. The containers package should be consistent with base in this regard.

5 7

Proposal: Add // for Data.Sequence
by Alan Isaac 11 Jun '16

11 Jun '16

BACKGROUND ---------- Data.Array provides (//) for incremental array updates. Data.Sequence lacks this useful functionality. SCOPE ----- Doing this efficiently may require that Data.Sequence access Data.IntMap. (It currently does not.) David Feuer commented: We may need to add some more splitting functions to Data.IntMap, if it supports them, but we probably want to do so anyway to match up with Data.Map. SOLUTIONS ----------- David Feuer offered the following implementation sketch. (See https://github.com/haskell/containers/issues/262) Collect all requested changes into an IntMap, then use something similar to Data.Sequence.splitMap with Data.IntMap.split to spread them through the tree. David Feuer commented: splitMap itself is overkill, because we'll likely be able to preserve whole subtrees. WHAT MIGHT BREAK ---------------- No anticipated breakage.

1 1

Proposal reminder: Add functions to get consecutive elements to Data.List
by Johan Holmquist 08 Jun '16

08 Jun '16

The discussion period for this proposal is near (31 of May). So far I count 1 for and 2 against the proposal. Joachim Breitner made a good enumeration of some advantages of adding these to base. Here is an enumeration of pros: * Availability in Data.List gives this pattern a common name. * A common name for this makes code easier to read and decreases the risk of getting the definition wrong. * The argument won't have to be repeated, hence making it easier to chain the functions. * List-fusion potential. Tobias Florek pointed out that `zip <*> tail` can be used to define this inline without the need for repeating the argument and made a reference to the Fairbairn threshold. This is elegant, but I am afraid that people might consider this obscure code golfing if used. Cheers Johan Holmquist ---------- Forwarded message ---------- From: Henning Thielemann <lemming(a)henning-thielemann.de> Date: 2016-04-13 13:28 GMT+02:00 Subject: Re: Proposal: Add functions to get consecutive elements to Data.List To: Johan Holmquist <holmisen(a)gmail.com> Cc: Haskell Libraries <libraries(a)haskell.org> On Wed, 13 Apr 2016, Johan Holmquist wrote: It is not strictly more general because it cannot handle empty sequences. > Think of it as if it handles the non-[] case.

7 12

Proposal: Left-Associative Semigroup Operator Alias in "Data.Semigroup"
by Herbert Valerio Riedel 08 Jun '16

08 Jun '16

Hello! In short, the right-associative fixity of (Data.{Monoid,Semigroup}.<>) subtly conflicts with definitions of (<>) in pretty printing APIs, for which the left-associative variant is sometimes desirable. This subtle overloading of (<>) is error-prone, as one has to remember which version of (<>) is currently in scope in order to be able to reason about non-trivial expressions involving this operator. This proposal is an attempt to resolve this unfortunate and confusing situation by completing the `Semigroup`/`Monoid` vocabulary with a standard left-associative alias. Please see https://ghc.haskell.org/trac/ghc/wiki/Proposal/LeftAssocSemigroupOp for more details. Discussion period: 4 weeks

6 5