- Libraries - Haskell.org

Add `take`/`drop`/`splitAt` to `Data.Map`/`Data.Set`
by Gabriel Gonzalez 08 Mar '16

08 Mar '16

I would like to propose adding `take`/`drop`/`splitAt` to both `Data.Map` and `Data.Set` as originally requested in: https://github.com/haskell/containers/issues/135 <https://github.com/haskell/containers/issues/135> The motivation behind this proposal is three-fold: * for convenience - these functions are commonly used to implement pagination or previews of maps/sets * for type accuracy - the public API impose an unnecessary `Ord` constraint * for efficiency - these can be implemented more efficiently using the internal API Currently the only way you can implement this functionality via the public API is to use `lookupIndex`/`elemAt` + `split`. For example, one way to implement `Data.Set.take` is: take :: Ord a => Int -> Set a -> Set a take n m | n < 0 = empty | size m <= n = m | otherwise = lt where (lt, _) = split k m k = elemAt n m {-# INLINE take #-} This implementation incurs an unnecessary `Ord` constraint due to a roundabout way of computing `take`: this extracts the element at the given index and then works backwards from the element’s value to partition the set using O(log N) comparisons. We could eliminate all of the comparisons by using the internal API. Intuitively, we expect that the performance of `Data.Set.take` would benefit from avoiding those unnecessary comparisons and also avoiding traversing the `Set`’s spine twice. So I tested that hypothesis by implementing `take` via the internal API like this: take :: Int -> Set a -> Set a take n0 s0 = go s0 n0 where go s@(Bin sz x l r) n = if sz <= n then s else let sl = size l in if n <= sl then go l n else link x l (go r $! n - sl) go Tip _ = Tip {-# INLINE take #-} I then added the following benchmark to `benchmarks/Set.hs`: diff --git a/benchmarks/Set.hs b/benchmarks/Set.hs index 3a6e8aa..03c99fb 100644 --- a/benchmarks/Set.hs +++ b/benchmarks/Set.hs @@ -31,6 +31,7 @@ main = do , bench "union" $ whnf (S.union s_even) s_odd , bench "difference" $ whnf (S.difference s) s_even , bench "intersection" $ whnf (S.intersection s) s_even + , bench "take" $ whnf (S.take (2^11)) s , bench "fromList" $ whnf S.fromList elems , bench "fromList-desc" $ whnf S.fromList (reverse elems) , bench "fromAscList" $ whnf S.fromAscList elems Here is the performance on my machine when implementing `take` via the public API: benchmarking take time 272.8 ns (266.7 ns .. 278.1 ns) 0.997 R² (0.996 R² .. 0.998 R²) mean 266.3 ns (261.8 ns .. 270.8 ns) std dev 15.44 ns (13.26 ns .. 18.95 ns) variance introduced by outliers: 75% (severely inflated) … and the performance improved by 61% from using the internal API: benchmarking take time 169.2 ns (166.1 ns .. 172.6 ns) 0.997 R² (0.996 R² .. 0.998 R²) mean 172.1 ns (169.4 ns .. 175.4 ns) std dev 10.68 ns (8.420 ns .. 15.34 ns) variance introduced by outliers: 78% (severely inflated) … and I’m guessing (but haven’t tested) that the performance gap would only increase the more expensive the comparison function gets. I haven’t performed comparative performance testing for `drop`/`splitAt` nor have I tested `Map` (because the benchmarks take a while for me to build and run) but I can perform those additional comparisons upon requests if people feel they are necessary. I haven’t yet written up a full patch since the maintainer asked me to first run this proposal by the libraries mailing list to assess whether it would be wise to expand the `containers` API to include these utilities. The deadline for discussion is two weeks.

8 12

Test email
by Gershom B 03 Mar '16

03 Mar '16

Please disregard -- sorry for the noise. Gershom

1 0

Re: Libraries Digest, Vol 150, Issue 32
by Michał J Gajda 27 Feb '16

27 Feb '16

-1(*inf) Downsides: 1. New way to make a Haskell expression that makes no semantic sense `length (1, 2)`, and it still evaluates. 2. New trick interview question that makes interviewers hated for being impractical. (Just like `join (*)`.) 3. Confuse hell out of beginners and practitioners alike. Upside: 1. One Canonical(tm) Functor instance for tuple, and pope's own claim that the other instance does not fit in our library. 2. More standard types that are Functor instances. 3. Easier to demonstrate that one can DO EVIL in Haskell too. -- Cheers Michal

1 0

GHC documentation of modules exposed by the base package
by Andrés Sicard-Ramírez 26 Feb '16

26 Feb '16

Dear all, By running in GHC 7.10.3 $ ghc-pkg field base-4.8.2.0 exposed-modules I can see various modules exposed by base-4.8.2.0 which are not documented (e.g. GHC.NUm) in http://downloads.haskell.org/~ghc/7.10.3/docs/html/libraries/index.html Which is the criterion for adding GHC documentation to the modules exposed by base? All the best, -- Andrés

2 1

SAFE: a Foldable proposal
by Thomas Tuegel 26 Feb '16

26 Feb '16

Friends, I address you this evening in the desperate hope that, though we have become divided by harsh words, we may come together again as one family in Haskell. Before, we saw as through a glass, darkly. To drive back the night, we stoked the fires of our passion. Now the heat burns us! The smoke stings our eyes! I intend to magnify what was hidden so we may see clearly by only a small flame. We came to Haskell along many paths, but the same values drew us all. One of the values dearest to us is the ability to reason statically about our programs. To enhance this ability which Haskell naturally affords us, we have devised laws to govern our type classes. Type class laws are rightly judged by their strength: the ways in which they constrain the instances we may write. When these laws bind us most tightly, we may reason most freely. With this in mind, let us turn to the Foldable class. Foldable has several laws, but I will focus on two. First, for foldr and foldMap, > foldr f z t = appEndo (foldMap (Endo . f) t) z Second, optionally, for Functors, > foldMap f = fold . fmap f There are other laws, but for my purposes, they essentially follow from the above. It is generally acknowledged that these laws are relatively weak: it is difficult to conceive an instance which violates them that is not an egregious violation. With that, I offer the following simple proposal. I doubt it will achieve consensus, but I believe it will illuminate our positions more clearly. I hope it allows us to see each other with more empathy. SAFE - Stronger Alternative Foldable Enhancement / Elucidation Foldable will gain a superclass, Alternative: > class Alternative t => Foldable t where { ... } The members of the class will not change. The class will gain the following laws to supercede the existing laws: > foldMap f empty = mempty > foldMap f (xs <|> ys) = foldMap f xs <> foldMap f ys > foldr f z empty = z > foldr f z (xs <|> ys) = foldr f (foldr f z ys) xs The laws for the other members follow in the obvious way. Some instances from base are ruled out: Identity, Either a, (,) a, Proxy, and Const m. Implementing this change would necessitate attaching warnings to those instances for the customary length of time. It is my understanding that GHC is not currently able to attach warnings to instances, but I think that would be a useful feature to add, even absent the current proposal. I think this Foldable class is better than the one we have now. These constraints are stronger because they show the connection between Alternative and Monoid. I will pause here a moment because I think this is crucial to the contention between us. Foldable could be a bridge between Alternative and Monoid. We do not agree about how much may be expected of the Foldable class. I think this is what we should expect. I think this guarantee, that there is a monoidal or Alternative structure underlying Foldable, was always the unarticulated vision behind the objections to these contentious instances. I hope that the utility and elegance of my proposal will convince you, but failing that I hope it illuminates what should be our topic of discussion: not "What is to be done about Foldable?" but rather, "What is to be expected of Foldable?" Sincerely, Thomas

5 8

Re: Haskell Foldable Wats
by Kris Nuttycombe 24 Feb '16

24 Feb '16

Oops, yes, "can't" is what I meant to type there. On Wed, Feb 24, 2016 at 2:54 PM, Manuel Gómez <targen(a)gmail.com> wrote: > On Wed, Feb 24, 2016 at 5:12 PM, Kris Nuttycombe > <kris.nuttycombe(a)gmail.com> wrote: > > make Haskell *less* internally > > consistent, just so that they can call `length (foo, bar)`. > > Can or can’t? >

1 0

Proposal: Add conspicuously missing Functor instances for tuples
by David Feuer 23 Feb '16

23 Feb '16

For some reason I really can't imagine, it seems the only tuple type with a Functor instance is (,) a. I was astonished to find that fmap (+1) (1,2,3) doesn't work. Since this is *useful*, and there is *only one way to do it*, I propose we add the following: instance Functor ((,,) a b) where fmap f (a,b,c) = (a,b,f c) instance Functor ((,,,) a b c) where fmap f (a,b,c,d) = (a,b,c,f d) etc. I would really love to see these make 8.0.0, but if that's impossible then so be it.

18 29

"Excuse me, I think this i my stop..." - Resigning from the Platform
by Mark Lentczner 22 Feb '16

22 Feb '16

I think this is the right time for me to exit: The truth is, I still can't bring myself to use a version of Haskell post the Foldable-Traversable-aPocalypse, let alone some future Haskell after the changes now in the works. My personal machines are all still 7.8. My personal projects are all pre-FTP. The Haskell I love to code in, the Haskell I'm passionate about, the Haskell I've advocated for real world use, and the Haskell I like to teach, is 7.8, pre-FTP. It's not that I'm dead set against change and evolution in a language, or even breaking changes. But FTP and beyond are changes that have lost the balance that Haskell had between abstraction and clarity, between elaborate and practical engineering. I don't see any restraint going forward, so I'm getting off the train. This puts me in an odd position with respect to Haskell Platform: I find myself building the Platform for a version of Haskell that I don't use. This isn't healthy for either the Platform or me. Hence, I'm resigning as release manager. I am sad because I believed that Haskell's path to much wider adoption was within reach. Now, especially with the ramping up of the Haskell Prime committee, which seems preordained to codify FTP and beyond into standard, we are approaching our Algol 68 moment: Building a major language revision with less opportunity than it's predecessor. I'll still see you 'round at meet-ups and conferences. I'll just be coding with an older accent. - Mark "mzero" Lentczner

5 6

Re: Discussion: GHC.Generics vs. transformers Sum/Product
by Ryan Scott 20 Feb '16

20 Feb '16

Indeed, I've been meaning to fix Trac #9043 [1] for a while. Its progress had been blocked by a separate issue [2] that will be fixed in 8.0. Now there's nothing blocking it, and I have a GHC fork [3] that finishes Oliver Charles' work on adding more instances to GHC.Generics datatypes. I'll probably submit it once 8.0 is released (since the window for new additions for 8.0 has already passed). In the meantime, if there's an instance you want to see added, file an issue on https://github.com/RyanGlScott/ghc! Ryan S. ----- [1] https://ghc.haskell.org/trac/ghc/ticket/9043 [2] https://ghc.haskell.org/trac/ghc/ticket/9766 [3] https://github.com/RyanGlScott/ghc/tree/ghc-generics-instances

2 1

Discussion: GHC.Generics vs. transformers Sum/Product
by David Feuer 18 Feb '16

18 Feb '16

GHC.Generics defines the following pleasantly-named types data (f :+: g) a = L1 (f a) | R1 (g a) and data (f :*: g) a = f a :*: g a represent lifted sums and products (analogous to Either and (,), respectively). These types, however, are given very few instances. Most notably, they lack even Functor instances! Entirely equivalent types, with less pleasant names, appear in transformers Data.Functor.Sum and Data.Functor.Product, where they are given plenty of instances. Is there some way to bring these things together, preferably with the names from GHC.Generics and the instances from Data.Functor.Sum and Data.Functor.Product?

3 3