- Libraries - Haskell.org

primitive library
by Simon Peyton Jones 23 Apr '18

23 Apr '18

Andrew, David I've seen a lot of traffic about the primitive library, in which you two are playing a leading role. Clearly something interesting is going on, but I have not been paying enough attention to work out what. Maybe lots of unrelated things? Maybe a handful of closely related things? Would you consider putting out a summary (to libraries and ghc-devs) to give an overview of the main threads, and any driving motivations. Why has all this blown up now? Meanwhile, thank you for being so active. Simon

3 3

Proposal: Export (#.) and (.#) from Data.Coerce
by Daniel Cartwright 22 Apr '18

22 Apr '18

(#.) :: Coercible b c => (b -> c) -> (a -> b) -> (a -> c) (#.) _ = coerce {-# INLINE (#.) #-} (.#) :: Coercible a b => (b -> c) -> (a -> b) -> (a -> c) (.#) f _ = coerce f {-# INLINE (.#) #-} The first of these is exported from Data.Functor.Util, and used in many places inside of base for efficiency over '.' (compose), However no module in base actually exports these. I have recently been using Data.Coerce more frequently and think it would be useful to go ahead and export these from somewhere in base. For convenience, I will paste the note about (#.) from Data.Functor.Util: "Note [Function coercion] ~~~~~~~~~~~~~~~~~~~~~~~ Several functions here use (#.) instead of (.) to avoid potential efficiency problems relating to #7542. The problem, in a nutshell: If N is a newtype constructor, then N x will always have the same representation as x (something similar applies for a newtype deconstructor). However, if f is a function, N . f = \x -> N (f x) This looks almost the same as f, but the eta expansion lifts it--the lhs could be _|_, but the rhs never is. This can lead to very inefficient code. Thus we steal a technique from Shachaf and Edward Kmett and adapt it to the current (rather clean) setting. Instead of using N . f, we use N #. f, which is just coerce f `asTypeOf` (N . f) That is, we just *pretend* that f has the right type, and thanks to the safety of coerce, the type checker guarantees that nothing really goes wrong. We still have to be a bit careful, though: remember that #. completely ignores the *value* of its left operand. "

6 6

Re: Proposal: Add a wrapped applicative type to Data.Monoid
by Ryan Scott 11 Apr '18

11 Apr '18

One thing that is not clear to me: is this Ap type intended to be a catch-all for defining instances that are "lifted" through an Applicative? Or are you deliberately restricting that to the Semigroup and Monoid instances? For instance, I noticed that you currently derive Ap's Eq, Ord, Read, and Show instances, which would give: instance Eq (f a) => Eq (Ap f a) instance Ord (f a) => Ord (Ap f a) instance Read (f a) => Read (Ap f a) instance Show (f a) => Show (Ap f a) Would you not want this instead, to be in line with the Semigroup and Monoid instances? instance (Applicative f, Eq a) => Eq (Ap f a) instance (Applicative f, Ord a) => Ord (Ap f a) instance (Applicative f, Read a) => Read (Ap f a) instance (Applicative f, Show a) => Show (Ap f a) I would be fine with either option, but if we should be clear about Ap's intentions when we end up documenting it. Ryan S.

3 3

Remove mtimesDefault or move it to Data.Monoid
by Simon Jakobi 06 Apr '18

06 Apr '18

Hi! I was surprised to find two functions that appear to do the same thing in Data.Semigroup: stimesMonoid :: (Integral b, Monoid a) => b -> a -> a [1] mtimesDefault :: (Integral b, Monoid a) => b -> a -> a [2] Both are essentially versions of the default stimes implementation that allow 0 as a multiplier. I think it's confusing to have two functions with nearly the same semantics but different implementations exported from the same module. As stimesMonoid seems to fit well into the group of different stimes implementations exported from Data.Semigroup, I propose that either 1. mtimesDefault be deleted (after a suitable deprecation period) or (particularly, if there still are plans to make mtimes a member of Monoid) 2. mtimesDefault be moved to Data.Monoid (possibly with a deprecated re-export from Data.Semigroup) In case 2, I also think mtimesDefault should be made an alias of stimesMonoid. Cheers, Simon [1] http://hackage.haskell.org/package/base-4.11.0.0/docs/Data-Semigroup.html#v… [2] http://hackage.haskell.org/package/base-4.11.0.0/docs/Data-Semigroup.html#v…

1 1

Proposal: Add inductively-defined Nat to base
by Daniel Cartwright 06 Apr '18

06 Apr '18

The proposed addition is simple, add the following to base: data Nat = Zero | Succ Nat, i.e. Peano Nats - commonly used along with -XDataKinds. I will list the pros/cons I see below: Pros: - This datatype is commonly defined throughout many packages throughout Hackage. It would be good for it to have a central location - The inductive definition of 'Nat' is useful for correctness (e.g. safeHead :: Vec a (Succ n) -> a; safeHead (Cons a as) = a;) - -XDependentHaskell is likely to bring this into base anyway - I believe that it might be possible to eliminate a Peano Nat at some stage during/after typechecking. I'm not well-versed in GHC implementation, but something along the lines of possibly converting an inductive Nat to a GMP Integer using some sort of specialisation (Succ -> +1)? Another interesting, related approach (and this is a very top-level view, and perhaps not totally sensical) would be something like a function 'f', that given a data structure and a number system, outputs the representation of that data structure in that number system (Nat is isomorphic to List (), so f : List () -> Binary -> BinaryListRep) Cons: - -XDependentHaskell will most likely obviate any benefit brought about by type families defined in base that directly involve Nat - Looking at base, I'm not sure where this would go. Having it in its own module seems a tad strange. I am open to criticism concerning the usefulness of the idea, or if anyone sees a Pro(s)/Con(s) that I am missing.

9 13

Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys
by Ivan Lazar Miljenovic 03 Apr '18

03 Apr '18

(Sending this back to the libraries@ list as well.) On 2 April 2018 at 23:59, Olivier S. <olivier.sohn(a)gmail.com> wrote: > > 2018-04-02 14:34 GMT+02:00 Ivan Lazar Miljenovic > <ivan.miljenovic(a)gmail.com>: >> >> On 2 April 2018 at 21:30, Olivier S. <olivier.sohn(a)gmail.com> wrote: >> > >> > Hello, >> > >> > I'm resending this proposal, which is simplified w.r.t the first one, >> > and >> > where I removed a wrong analysis of a benchmark. >> > >> > - Proposal I : Optimize the time complexity of (key -> Maybe Vertex) >> > lookups >> > and graph creation when keys are Integral and consecutive. >> > >> > (The related PR for proposal I is [1], including benchmarks showing the >> > performance improvements.) >> > >> > Currently, (key -> Maybe Vertex) lookups returned by graphFromEdges >> > consist >> > of a binary search on an array, with a time complexity of O(log V) (I >> > will >> > use V for "Count of vertices", E for "Count of edges"). >> >> At the risk of bikeshedding, can you please use |V| and |E| to refer >> to the order and size of the graph respectively? > > > Do you mean in the haddock documentation for complexities or here? I don't > know which is mor readable, O( (V+E) * log V ) or O( (|V|+|E|) * log |V| ). > Anyway it would be a quick change in the PR, I'm not particularly attached > to the notation. Both. |V| and |E| are more standard for this, as V and E represent the vertices and edges themselves. >> > When key is Integral, and keys (of nodes passed to the graph creation >> > function) form a set of /consecutive/ values (for example : [4,5,6,7] or >> > [5,6,4,7]), we can have an O(1) lookup by substracting the value of the >> > smallest key, and checking for bounds. >> >> I'm not sure I follow this part; are you ignoring order in these lists >> (you're referring to sets but using list notation)? >> > > I'm not ignoring the order, let me try to give a more precise definition: > > keys is a list of consecutive keys iff it verifies: > > -- (1) keys contains no duplicates > Set.size (Set.fromList keys) == length keys > > -- (2) there is no "gap" between values, when sorted: > sort keys == [minimum keys .. maximum keys] > > > The O(1) lookup is at line 516 of Data/Graph.hs in > https://github.com/haskell/containers/pull/549/files (key_vertex) > >> > >> > Hence, graph creation complexity is improved, and user algorithms using >> > (key >> > -> Maybe Vertex) lookups will see their complexity reduced by a factor >> > of >> > up-to O(log V). >> > >> > The PR introduces this lookup and uses it for functions >> > graphFromEdgesWithConsecutiveKeys and >> > graphFromEdgesWithConsecutiveAscKeys. >> > >> > Here is a summary of complexities for (graph creation, lookup function) >> > as >> > they stand in the current state of the PR: >> > >> > - graphFromEdges (the currently existing function): >> > O( (V+E) * log V ), O(log V) >> > - graphFromEdgesWithConsecutiveKeys (new function): >> > O( E + (V*log V) ), O(1) >> > - graphFromEdgesWithConsecutiveAscKeys (new function) : >> > O( V+E ), O(1) >> > >> > - Proposal II : Deprecate `graphFromEdges` taking [(node, key, [key])] >> > in >> > favor of `graphFromMap` taking (Map key (node,[key])) >> > >> > If we pass the same key twice in the list we pass to 'graphFromEdges' it >> > is >> > undefined which node for that key will actually be used. >> > Introducing 'graphFromMap', taking a (Map key (node,[key]) would >> > alleviate >> > this issue, through the type used. >> >> Off the top of my head, I'm not a big fan of this. If we're going to >> improve this, then I'd prefer to do so in such a way that allowed for >> usage with IntMap > > > Yes, IntMap seems to be better wrt performances than Map. Quoting the doc of > IntMap: > > This data structure performs especially well on binary operations like union > and intersection. However, my benchmarks show that it is also (much) faster > on insertions and deletions when compared to a generic size-balanced map > implementation (see Data.Map). > > >> >> (is there an existing type-class that covers >> association list-style data structures?). > > > > There is the Map type-class (which I just discovered) in : > > https://hackage.haskell.org/package/collections-api-1.0.0.0/docs/Data-Colle… Except that it's in another library ;-) > With instances defined here, but only for Lazy versions Data.Map and > Data.IntMap: Note that the data structures for the Lazy and Strict variants of [Int]Map are the same, it's just the strictness of the functions that operate on them that differ. > > https://hackage.haskell.org/package/collections-base-instances-1.0.0.0/docs… > > Also, the type-class class doesn't have toAscList (or toList) functions > (which is what we would use in the implementation). > > So if we want to rely on this we would need to implement toAscList, and > probably add instances for Strict maps (Data.IntMap.Strict, Data.Map.Strict) > >> >> Ideally you could also use >> HashMap from unordered-containers as well, but since we ultimately >> want `type Vertex = Int` I'm not sure if that's worth it; IntMap, >> however, is. >> > > I see another problem with HashMap : it doesn't provide a toAscList function > where the keys are sorted, so we would have to sort them, incurring a fixed > O(V log V) cost, whereas with Map and IntMap the user has the possibility to > create the map from an ascending list (fromAscList), in O(V) time and we can > get the list back also (toAscList) in O(V) time. > >> > >> > Also, using a Map makes the implementation a bit more "natural" : there >> > is >> > no need for sorting by key, as Map.toAscList gives exactly the sorted >> > list >> > we want. >> > >> > We could also deprecate graphFromEdgesWithConsecutiveKeys and >> > graphFromEdgesWithConsecutiveAscKeys (introduced in proposal I) in favor >> > of >> > graphFromConsecutiveMap. >> > >> > About the naming, I propose two different schemes: >> > >> > Either: >> > - graphFromEdges (takes a List, deprecated, existing >> > function) >> > - graphFromEdgesInMap (takes a Map) >> > - graphFromEdgesInConsecutiveMap (takes a Map with consecutive keys) >> > Or: >> > - graphFromEdges (takes a List, deprecated, existing >> > function) >> > - graphFromMap >> > - graphFromConsecutiveMap >> > with these, to reflect the Map / List duality in the naming scheme: >> > - graphFromList (takes a List, deprecated, redirects >> > to >> > graphFromEdges) >> > - graphFromConsecutiveList (takes a List, deprecated, redirects >> > to >> > graphFromEdgesWithConsecutiveKeys) >> > - graphFromConsecutiveAscList (takes a List, deprecated, redirects >> > to >> > graphFromEdgesWithConsecutiveAscKeys) >> > >> > Cheers, >> > Olivier Sohn >> > >> > [1] https://github.com/haskell/containers/pull/549 >> > >> > >> > _______________________________________________ >> > Libraries mailing list >> > Libraries(a)haskell.org >> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >> > >> >> >> >> -- >> Ivan Lazar Miljenovic >> Ivan.Miljenovic(a)gmail.com >> http://IvanMiljenovic.wordpress.com > > -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com http://IvanMiljenovic.wordpress.com

2 7

Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys
by Olivier S. 03 Apr '18

03 Apr '18

Hello, I'm resending this proposal, which is simplified w.r.t the first one, and where I removed a wrong analysis of a benchmark. - Proposal I : Optimize the time complexity of (key -> Maybe Vertex) lookups and graph creation when keys are Integral and consecutive. (The related PR for proposal I is [1], including benchmarks showing the performance improvements.) Currently, (key -> Maybe Vertex) lookups returned by graphFromEdges consist of a binary search on an array, with a time complexity of O(log V) (I will use V for "Count of vertices", E for "Count of edges"). When key is Integral, and keys (of nodes passed to the graph creation function) form a set of /consecutive/ values (for example : [4,5,6,7] or [5,6,4,7]), we can have an O(1) lookup by substracting the value of the smallest key, and checking for bounds. Hence, graph creation complexity is improved, and user algorithms using (key -> Maybe Vertex) lookups will see their complexity reduced by a factor of up-to O(log V). The PR introduces this lookup and uses it for functions graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys. Here is a summary of complexities for (graph creation, lookup function) as they stand in the current state of the PR: - graphFromEdges (the currently existing function): O( (V+E) * log V ), O(log V) - graphFromEdgesWithConsecutiveKeys (new function): O( E + (V*log V) ), O(1) - graphFromEdgesWithConsecutiveAscKeys (new function) : O( V+E ), O(1) - Proposal II : Deprecate `graphFromEdges` taking [(node, key, [key])] in favor of `graphFromMap` taking (Map key (node,[key])) If we pass the same key twice in the list we pass to 'graphFromEdges' it is undefined which node for that key will actually be used. Introducing 'graphFromMap', taking a (Map key (node,[key]) would alleviate this issue, through the type used. Also, using a Map makes the implementation a bit more "natural" : there is no need for sorting by key, as Map.toAscList gives exactly the sorted list we want. We could also deprecate graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys (introduced in proposal I) in favor of graphFromConsecutiveMap. About the naming, I propose two different schemes: Either: - graphFromEdges (takes a List, deprecated, existing function) - graphFromEdgesInMap (takes a Map) - graphFromEdgesInConsecutiveMap (takes a Map with consecutive keys) Or: - graphFromEdges (takes a List, deprecated, existing function) - graphFromMap - graphFromConsecutiveMap with these, to reflect the Map / List duality in the naming scheme: - graphFromList (takes a List, deprecated, redirects to graphFromEdges) - graphFromConsecutiveList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveKeys) - graphFromConsecutiveAscList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveAscKeys) Cheers, Olivier Sohn [1] https://github.com/haskell/containers/pull/549

2 2

Proposal: function from Maybe to Alternative
by Li-yao Xia 01 Apr '18

01 Apr '18

Hello Libraries, I previously proposed adding a `liftMaybe :: Applicative m => Maybe a -> MaybeT m a` to transformers, on its issue tracker [1]. But its generalization to `Alternative m => Maybe a -> m a` seems like a nice addition to the base library, inside `Control.Applicative` (or `Data.Maybe`). My proposal is the following: 1) In base, add `liftMaybe = maybe empty pure :: Alternative m => Maybe a -> m a` to `Control.Applicative`. 2) In transformers, reexport it from `Control.Monad.Trans.Maybe`. There was another thread [2] on this ML also about the same combinator, and the main question appears to be whether it crosses the Fairbairn threshold. I can give some more arguments. I think it's worth giving it a name, even if there is a three-word definition (`liftMaybe = maybe empty pure`). I've found myself looking for it a few times, and that short definition is the result of a bit of code-golfing that not everyone is familiar with. Some may end up with more verbose reimplementations instead. Its absence stands out even more, as it is also the MaybeT counterpart to the functions `except`, `state`, `reader`, etc. which exist for other monad transformers. A few minor remarks. There is some asymmetry with the solution as I proposed it: this one function `liftMaybe` would correspond to two functions for every other transformer, one in the transformers library (`except`, `state`, etc.), one in mtl (`liftEither`, `state`, etc.). In contrast, the mtl-style class associated with `MaybeT` is `Alternative`. Since it is part of the standard library, it's not as useful to define a specialized version in `Control.Monad.Trans.Maybe` as it is for the other transformers. If we still decide to add a specialized function, a slightly lazier implementation is possible: liftMaybe :: Applicative m => Maybe a -> MaybeT m a liftMaybe = MaybeT . pure Cheers, Li-yao [1] https://hub.darcs.net/ross/transformers/issue/49 [2] https://mail.haskell.org/pipermail/libraries/2012-February/017548.html

1 0

Proposal : Data.Graph performance improvements (graph creation and lookups when nodes keys are consecutive)
by Olivier S. 30 Mar '18

30 Mar '18

Hello, This is a 3-part proposal for improving the time performance of Data.Graph. The related PR for proposal I is https://github.com/haskell/containers/pull/549, including some graph benchmarks. Reading the PR may be a good introduction to this material, if you're not yet familiar with Data.Graph! I'm by advance sorry for the length of this mail, but since these are all related proposals I thought it was best to keep them together. I may be wrong, if you feel the number of issues addressed herein is too big, I can start a thread with just Proposal I for example. Note that I may or may not have time to do more work than done in the current PR, but I hope this discussion will be of use to anyone wanting to follow-up on this. That being said, I'm looking forward to hearing what the community thinks of these proposals! - Proposal I : Optimize the time complexity of (key -> Maybe Vertex) lookups and graph creation. Currently, (key -> Maybe Vertex) lookups returned by graphFromEdges consist of a binary search on an array, with a time complexity of O(log V) (I will use V for "Count of vertices", E for "Count of edges"). When key is Integral, and keys (of nodes passed to the graph creation function) form a set of /consecutive/ values, we can have an O(1) lookup by substracting the value of the smallest key, and checking for bounds. Hence, graph creation complexity is improved, and user algorithms using (key -> Maybe Vertex) lookups will see their complexity reduced by a factor of up-to O(log V). The PR introduces this lookup and uses it for functions graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys. Note that in this PR, graphFromEdges in unchanged, so it doesn't benefit from these improvements (see Proposal II below). Here is a summary of complexities as they stand in the current state of the PR: ------------------------------------------------------------------------------------- | | Time complexities | | Functions |--------------------------------------------- | | graph creation | (key -> Maybe Vertex) | ------------------------------------------------------------------------------------- | graphFromEdges | O( (V+E) * log V ) | O(log V) | | graphFromEdgesWithConsecutiveKeys | O( E + (V*log V) ) | O(1) | | graphFromEdgesWithConsecutiveAscKeys | O( V+E ) | O(1) | ------------------------------------------------------------------------------------- - Proposal II : Make users of graphFromEdges benefit from performance improvements "for free" when they use Integral keys that are consecutive. We could use a rewrite rule to redirect graphFromEdges (when key is Integral) to a function checking if the keys are successive or not, to decide if the optimized lookup can be used. The problem with this is that some potential optimizations would be hidden-away, consider this example: -- 'userAlgorithm' doesn't have the (Integral a) constraint userAlgorithm :: (Ord a) => ... userAlgorithm = (...) -- hence, the rewrite rule here will never fire: graphFromEdges ... userProgram :: (Integral a, Ord a) => a -> ... userProgram input = userAlgorithm input -- Eventhough input /is/ Integral (and its keys may be consecutive), -- a potential optimization is lost because 'userAlgorithm' doesn't have the (Integral a) constraint. To address this, I propose to introduce the following a breaking change : instead of using a rewrite rule, just add an (Integral key) constraint on graphFromEdges, and do the check (wether optimized lookups can be used) in graphFromEdges itself. Then, in the previously described scenario, the user would see a compilation error indicating that (Integral a) could not be deduced from the context. Hence, the user would be more likely to just add the Integral constraint on myAlgorithm (and benefit from optimizations) than to use graphFromEdgesOld, which will have been added to do exactly what graphFromEdges does today, and which is intended to be used when the key is genuinely not Integral. And for completeness, note that we could have the idea of the rewrite rule on graphFromEdgesOld, eventhough I'm not sure it will benefit any real use case (but who knows...). - Proposal III : Deprecate `graphFromEdges` taking [(node, key, [key])] in favor of `graphFromMap` taking (Map key (node,[key])) While working on the PR, I found two arguments in favor of this change: -a) Today in graphFromEdges, if we pass the same key twice, it is undefined which node for that key will actually be used. graphFromMap, taking a (Map key (node,[key]) would alleviate this issue. -b) "sortBy is expensive, even on sorted input": I became aware of this as I looked at these 2 benchmarks: benchmarking Degree_Zero/1000_ascending_graphFromConsecutiveAscKeys time 53.55 μs (52.44 μs .. 54.76 μs) 0.991 R² (0.986 R² .. 0.995 R²) mean 57.41 μs (55.02 μs .. 61.75 μs) std dev 10.64 μs (5.100 μs .. 17.09 μs) variance introduced by outliers: 95% (severely inflated) benchmarking Degree_Zero/1000_ascending_graphFromConsecutiveKeys time 75.34 μs (73.79 μs .. 76.85 μs) 0.992 R² (0.987 R² .. 0.995 R²) mean 74.67 μs (72.29 μs .. 77.47 μs) std dev 8.335 μs (6.692 μs .. 10.70 μs) variance introduced by outliers: 85% (severely inflated) In the second benchmark, we do the same work as in the first benchmark, except for an initial sortBy on an already sorted list, which introduces a 30% overhead! Looking at the implementation of sortBy, I saw that there was no initial check to see if the list was sorted or not. Since we use sortBy in graphFromEdges, we could check wether the input is sorted or not, before using sortBy. But also, if we used a Map (this is the reason I use this example here), there would be no need to sortBy because Map.toAscList gives exactly the sorted list we want. This constitutes another argument for this proposal. Note that graphFromEdgesWithConsecutiveKeys and graphFromEdgesWithConsecutiveAscKeys would also be deprecated in favor of graphFromConsecutiveMap, because they have the same a) and b) issues. Naming proposal N1: - graphFromEdges (takes a List, deprecated, existing function) - graphFromEdgesInMap (takes a Map) - graphFromEdgesInConsecutiveMap (takes a Map with consecutive keys) Naming proposal N2: - graphFromEdges (takes a List, deprecated, existing function) - graphFromMap - graphFromConsecutiveMap with these, to reflect the Map / List duality in the naming scheme: - graphFromList (takes a List, deprecated, redirects to graphFromEdges) - graphFromConsecutiveList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveKeys) - graphFromConsecutiveAscList (takes a List, deprecated, redirects to graphFromEdgesWithConsecutiveAscKeys) -- Olivier Sohn PS : when writing the criterion graph benchmarks, I discovered that Graphs can be evaluated to normal form by criterion only when they are acyclic. Cyclic graphs will make the evaluation loop infinitely. I wonder why that is, if anyone has an explanation on that subject I'd be happy to hear it! Or should I submit a bug report at criterion?

1 0

Proposal: Add a wrapped applicative type to Data.Monoid
by Daniel Cartwright 28 Mar '18

28 Mar '18

I see this as being generally (as in, to the users of Haskell as a whole) useful: newtype Ap f a = Ap { getAp :: f a } deriving (Applicative, Eq, Foldable, Functor, Generic, Generic1 ,Monad, Ord, Read, Show, Traversable) Some hand-written instances: instance (Applicative f, Semigroup a) => Semigroup (Ap f a) where (Ap x) <> (Ap y) = Ap $ liftA2 (<>) x y instance (Applicative f, Monoid a) => Monoid (Ap f a) where mempty = Ap $ pure mempty

5 6