- Libraries - Haskell.org

Re: Constraints on definition of `length` should be strengthened
by dominic＠steinitz.org 10 Apr '17

10 Apr '17

I am not sure what to make of the “documentation” to which you refer. For example, a type Tensor seems to be defined. Now you can tensor lots of things with some algebraic structure but most commonly vector fields and modules (modules in the mathematical sense that is). The type Tensor seems to have no relation to these and there is no prose giving an indication of the author’s intent. Perhaps we should be cautious about adducing other parts of the package as evidence? > Already done mate. > > https://hackage.haskell.org/package/hask-0/docs/Hask-Category.html#t:Either > https://hackage.haskell.org/package/hask-0/docs/Hask-Category.html#t:Functor > > Note the multiple Functor instances for Either and Coproduct. e.g. > > - Functor * (* -> *) Either > - Functor * * (Either a) > etc etc > > On 09/04/17 10:29, Henrik Nilsson wrote: >> And of course, if, in a hypothetical future version of Haskell >> where we could make all possible functor instances for tuples, >> the question becomes: which one do we pick? The answer might well >> be "none" (in the prelude, at least). Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com

2 1

Re: Constraints on definition of `length` should be strengthened
by Anthony Clayden 07 Apr '17

07 Apr '17

> On Wed Apr 5 16:15:48 UTC 2017, Paolo Giarrusso wrote: > Thanks for all the mails, but I'm still missing an answer, > so I must have done something wrong. :-) Thanks Paolo, you've done nothing wrong IMHO. You've done the community a service by pointing out an omission in the docos. It's the same failure to communicate clearly that's given rise to the whole FTP kerfuffle. > I guess I didn't explain my question well. > Or nobody thinks it's worth answering (in which case, sorry, but I'd > prefer to be told I'm misguided, over having the question ignored). I think your original question was clear. I think it is very well worth answering. That is: answering what are the 'Laws' for Foldable? I've been waiting patiently for Libraries HQ to: * explain the applicable Laws * acknowledge they're not doco'd * volunteer to fix that > ... I'm really asking a different question: do length docs actually > give a complete specificationit still seems to me they don't. I agree they don't. > ... > But that's very confusing: can really debate on `length (a, b) = 1` > have continued for so long, without noticing that `length = getSum . > foldMap (Sum . const 1)` is a fundamental assumption and is not > mandated by anything written down? I assume I must be missing > something, which is why I asked. The only reply I've seen [from David F, you copied below, apologies if I've missed others] doesn't give any "fundamental assumption". It only says "should be quite well-behaved" and "pretty much everybody agrees on". I'm not 'getting at' David, at least he answered. I agree with your intuition that Foldable length = length . toList But that just pushes the question back to what are the Laws for `toList`? Note that `toList` has been in Foldable 'for ever'. And instance Foldable Maybe 'for ever'. That returns a 0-or-1 length list. Contrast that `instance Foldable ((,) b)` appeared in GHC 7.8 ~2014, along with `instance Foldable Either`. > Of all incomplete docs, this matters more > since `length (a, b)` is so surprising. I'd say the surprising bit is `toList (a, b)`. `length` is just a consequence. Cue another long thread on `toList`. I'm inclined to agree with Edward K, that there's only one possible definition for `toList` -- that is, if we accept `instance Foldable ((,) b). Cue another long thread on tuple instances, and the Either instance. > The unsuspecting looking at docs lacks the facts needed to > infer this wart. Spelling out implications would IMHO be even better, > for the same reason people state theorems even though they can be > proved, but maybe some disagree. A complete spec would be a starting > point. Yes. In particular, the conspicuous lack of docos is now wildly at variance with all the tutorial/intro texts, which explain `length` as for Lists. I plain think that `length` should be Lists-only; there should be some other name for Foldable's size. >>> On 3 April 2017 at 17:59, David Feuer wrote: >>> length should be quite well-behaved relative to foldMap: >>> >>> length = getSum . foldMap (Sum . const 1) >> Thanks, that looks useful to add to docs. I was thinking of `length = >> length . toList`. >>> Another law pretty much everyone agrees on is that *if* f is an instance of >>> Traversable, then >>> >>> foldMap = foldMapDefault AntC

2 1

Package maintainership takeover: quickcheck-instances
by Oleg Grenrus 07 Apr '17

07 Apr '17

The quickcheck-instances provides QuickCheck type-classes' instances for Haskell Platform packages. Unfortunately, author and current maintainer Antoine Latter is quite unresponsive. There is handful of PR open [2], and I had to use Hackage Trustee powers to allow new versions of dependencies (to keep e.g. Stackage nightly going on). I have tried to contact him to offer a co-maintainership help (at 14.12.2016). Cheers, Oleg Grenrus - [1]: http://hackage.haskell.org/package/quickcheck-instances - [2]: https://github.com/aslatter/qc-instances/pulls

1 0

Civility notes (was "Traversable instances for (,,) a b")
by Tom Murphy 06 Apr '17

06 Apr '17

Hi Fumiaki! I agree with you that some poorly-chosen words by a few people have soured this conversation, but please don't let that turn you completely off of the productive conversation most of us are attempting to have! I think it's largely been successful, too: even if many of us haven't changed our -1/+1 votes, I for one have had my ideas challenged and have a more nuanced view than before talking with everyone here. Henning and Edward are two examples (one from each side of the +1/-1 chasm) who have been aided by this discussion, in making important progress to finding a middle ground (each in the form of proposed compiler changes). To the rest of us: Fumiaki regretting having posted here is a pretty stark example of why speaking politely matters. People being scared away and feeling unwelcome is a real phenomenon, and we need to do our part to fix it. I'd propose: - If you haven't read it already, SPJ recently wrote a heartfelt letter on the subject [0]. We've gotten better since then, but clearly we're not finished. - Civility is a norm, and norms sometimes need to be enforced. From a distance, we all look bad (and unwelcoming!) if anyone is hostile and we don't make it clear it's not acceptable. Speak up! That said, everyone makes mistakes - try to give people space to apologize and move on. - If someone says something insulting to you, please take that as a sign to become more polite, not less so. The downward spiral is real. If you're called out for saying something regrettable (again, regardless of if you're +1 or -1 on this issue), *please* take our desire for civil conversation seriously. Responses like (I'm paraphrasing, and not trying to cite anyone specifically): "It was a joke (mostly)" and "It's your fault if you didn't get the joke" are worse than not writing anything at all. Ideal would be a quick "Sorry!" Thanks, all! Tom [0] https://mail.haskell.org/pipermail/haskell/2016-September/024995.html On Sun, Apr 2, 2017 at 12:11 PM, Fumiaki Kinoshita <fumiexcel(a)gmail.com> wrote: > The discussion has diverged to flaming due to a few offensive people. I > guess I shouldn't have posted a proposal here, I should have submitted a > patch instead. > > 2017-03-23 19:53 GMT+09:00 Fumiaki Kinoshita <fumiexcel(a)gmail.com>: > >> It's surprising that they are missing (forgive me, I'm not here to make >> people grumpy). >> > > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > >

16 20

Getting containers updated in Stackage
by David Feuer 03 Apr '17

03 Apr '17

It's come to my attention that Stackage doesn't have the latest and greatest versions of containers. Stackage nightly is on 0.5.7.1, and I just released 0.5.10.2. It'd be nice to get that fixed, but the containers maintainers do not have the time to take responsibility for Stackage curation. Could whoever's responsible please take care of it? Thanks, David

5 7

Deriving length better: missing method problem
by David Feuer 02 Apr '17

02 Apr '17

GHC 8.4 DeriveFoldable will derive the definition of `null` rather than falling back on the default. This can produce dramatic performance improvements. I would like to do the same for `length`, but unfortunately, there's a problem. ### Why I want to derive length Consider the declaration data Foo a = Foo (Map "String" a) (Set a) A hand-written definition of `length` would look like this: length (Foo m set) = length m + length set This would produce an O(1) implementation of length, since Map and Set are annotated with their lengths. But the default implementation of length (which is what you get when you use `deriving Foldable`) would instead produce length foo = foldl' (\acc _ -> acc + 1) 0 foo which is O(n). Gross. ### What's the problem? There's no problem deriving length for Foo. The trouble comes when trying to derive length for a recursive type. data List a = Nil | Cons a (List a) The most obvious implementation to derive would be length Nil = 0 length (Cons _ xs) = 1 + length xs but this is not tail recursive! That's absolutely no good. What we *want* here is length = lengthPlus 0 lengthPlus acc Nil = acc lengthPlus !acc (Cons _ xs) = lengthPlus (acc + 1) xs We actually could arrange for that in this case, since we see that a `List` contains itself recursively. But what about *mutual* recursion? data List2 a = Nil | Cons a (List2' a) newtype List2' a = List2' (List2 a) Now the deriving mechanism can't see the recursion, and everything is horrible. ### The simplest solution It seems likely that the simplest solution would be what nobody really wants: add yet another method to Foldable: lengthPlus :: Int -> f a -> Int lengthPlus n xs = n + length xs We could derive efficient implementations of `lengthPlus` without any particular difficulty. ### Alternatives? I haven't thought of any plausible alternatives yet. Maybe someone else will. David

1 0

GHCI says we all drink left-handed
by Andreas Abel 01 Apr '17

01 Apr '17

GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help Prelude> data Handed = Handed Prelude> let drink beer = beer Prelude> all drink (Left Handed) True -- Andreas Abel <>< Du bist der geliebte Mensch. Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden andreas.abel(a)gu.se http://www.cse.chalmers.se/~abela/

2 3

Re: Functor, Applicative, Monad, Foldable, Traversable instances for (, , ) a b
by dominic＠steinitz.org 01 Apr '17

01 Apr '17

Since "God made the integers…” perhaps the question of whether 0 is an integer is best left to theologians. On the other hand, in set theory a tuple is defined as a set containing two elements and in category theory, a product is a limit of a discrete category with two objects. Of course you can treat a tuple as a decorated container containing one element but I doubt many mathematicians think of them this way. Before anyone points out that I shouldn’t think of types as sets, the same applies to \omega-complete partial orders. Perhaps I had better be explicit and say please no aka -1. > The length of ((,) a) is exactly one. Anything else is ridiculous. Try > arguing against that, instead of a position that does not exist ("length > of tuples"). I wrote this instance some number of years ago (about 11), > and have used it on teams all over the place. Not once was there an > issue that was not quickly corrected, and thereby achieving the > practical benefits that come with, by providing a better understanding. > That understanding is above. The length of ((,) a) is exactly one. Say > it with me. > > > On 01/04/17 10:08, Francesco Ariis wrote: >> On Sat, Apr 01, 2017 at 07:59:00AM +1000, Tony Morris wrote: >>> A contrary, consistent position would mean there is a belief in all of >>> the following: >>> >>> * the length of any value of the type ((,) a) is not 1 >>> * 0 is not an integer Dominic Steinitz dominic(a)steinitz.org http://idontgetoutmuch.wordpress.com

1 0

RE: fix for Data.List.sortBy
by Gregory Popovitch 28 Mar '17

28 Mar '17

Sid, I'd be delighted to submit the patch, as long as I have permission (which I probably don't), you feel confident about the change and maybe a couple of other people agree. Here is the proposed change. Tests shows significant speed improvement (30%) when sorting lists of random numbers, and same efficiency for sorting already sorted lists (both ascending and descending). Thanks, greg _____ From: siddhanathan(a)gmail.com [mailto:siddhanathan@gmail.com] On Behalf Of Siddhanathan Shanmugam Sent: Monday, March 27, 2017 6:53 PM To: Gregory Popovitch Subject: RE: Proposal: a new implementation for Data.List.sort and Data.List.sortBy, which has better performance characteristics and is more laziness-friendly. Since I don't see any regressions, this doesn't really need CLC approval. The changes are also small enough that a Github PR may be accepted (otherwise, the change goes in via Phabricator). Are you interested in implementing this patch? If yes, a standard Github PR should be fine. Right now gSort is a three line change I think. It will be changed in ghc/libraries/base/Data/OldList.hs on the ghc/ghc repo on Github. I'm hoping for some more comments from other Haskellers, before pushing for this change in base. I feel like we may be missing a potential optimization that someone else might spot. So probably going to wait a few days. On Mar 27, 2017 11:43 AM, "Gregory Popovitch" <greg7mdp(a)gmail.com> wrote: Hi Sid, Thanks, glad you looked into that. My understanding of the Haskell execution model is really poor, so I can't say one way or the other, but I felt that laziness ought to be considered as well, and I'm glad it was :-) So in conclusion it looks like we have a winner with your latest gSortBy version. How do we get this pushed to the GHC library? Thanks, greg _____ From: siddhanathan(a)gmail.com [mailto:siddhanathan@gmail.com] On Behalf Of Siddhanathan Shanmugam Sent: Monday, March 27, 2017 2:12 PM To: Gregory Popovitch Subject: Re: Proposal: a new implementation for Data.List.sort and Data.List.sortBy, which has better performance characteristics and is more laziness-friendly. Hi Greg, On Mon, Mar 27, 2017 at 10:19 AM, Gregory Popovitch <greg7mdp(a)gmail.com> wrote: Unfortunately, this optimization makes the sort less lazy, so doing something like: take 4 $ sort l requires more sorting of the list l with this change. I'm not sure it is a good tradeoff. This can be verified with: https://github.com/greg7mdp/gh <https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs> c-sort/blob/master/src/sort_with_trace.hs I think you're running without optimizations turned on. It is lazy in my case. Also, the difference should be negligible (if any at all). Here's an example of the list being sorted: [11,4,6,8,2,5,1,7,9,55,11,3] ... [[4,11],[6,8],[2,5],[1,7,9,55],[3,11],[]] ... [[1,2,4,5,6,7,8,9,11,55],[3,11]] * 1 3 * 2 3 * 4 3 * 4 11 [1,2,3,4] The number of operations saved is only in the last merge. It's only lazy at this step. So we save at most one traversal of the list, which is not too expensive since our worst case bounds is O(n log n) anyway. This should mean that the asymptotic performance should be identical, regardless of the number of comparisons saved. Of course, you do get better constants, but I would be surprised if those constants translated to significantly better performance for a reasonable size list. I do agree that it would be nice to have a more serious validation test suite. Thanks, greg _____ From: siddhanathan(a)gmail.com [mailto:siddhanathan@gmail.com] On Behalf Of Siddhanathan Shanmugam Sent: Monday, March 27, 2017 12:53 PM To: Gregory Popovitch Cc: Haskell Libraries Subject: Re: Proposal: a new implementation for Data.List.sort and Data.List.sortBy, which has better performance characteristics and is more laziness-friendly. We can improve things a bit further by forcing evaluation (with seq) along the way appropriately. gregSortBy cmp [] = [] gregSortBy cmp xs = head $ until (null.tail) reduce (pair xs) where pair (x:y:t) | x `cmp` y == GT = [y, x] : pair t | otherwise = [x, y] : pair t pair [x] = [[x]] pair [] = [] reduce (v:w:x:y:t) = merge v' x' `seq` merge v' x' : reduce t where v' = merge v w `seq` merge v w x' = merge x y `seq` merge x y reduce (x:y:t) = merge x y `seq` merge x y : reduce t reduce xs = xs merge xs [] = xs merge [] ys = ys merge xs@(x:xs') ys@(y:ys') | x `cmp` y == GT = y : merge xs ys' | otherwise = x : merge xs' ys gSortBy cmp = mergeAll . sequences where sequences (a:b:xs) | a `cmp` b == GT = descending b [a] xs | otherwise = ascending b (a:) xs sequences xs = [xs] descending a as (b:bs) | a `cmp` b == GT = descending b (a:as) bs descending a as bs = (a:as) `seq` (a:as) : sequences bs ascending a as (b:bs) | a `cmp` b /= GT = ascending b (as . (a:)) bs ascending a as bs = as [a] `seq` as [a] : sequences bs mergeAll [x] = x mergeAll xs = mergeAll (mergePairs xs) mergePairs (a:b:xs) = merge a b `seq` merge a b : mergePairs xs mergePairs xs = xs merge as@(a:as') bs@(b:bs') | a `cmp` b == GT = b : merge as bs' | otherwise = a : merge as' bs merge [] bs = bs merge as [] = as Before the change: benchmarking random ints/ghc time 3.687 s (3.541 s .. NaN s) 1.000 R² (1.000 R² .. 1.000 R²) mean 3.691 s (3.669 s .. 3.705 s) std dev 21.45 ms (0.0 s .. 24.76 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking random ints/greg time 2.648 s (2.482 s .. 2.822 s) 0.999 R² (0.998 R² .. 1.000 R²) mean 2.704 s (2.670 s .. 2.736 s) std dev 52.68 ms (0.0 s .. 54.49 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking random ints/gSort time 2.733 s (2.682 s .. 2.758 s) 1.000 R² (1.000 R² .. 1.000 R²) mean 2.707 s (2.689 s .. 2.718 s) std dev 16.84 ms (0.0 s .. 19.20 ms) variance introduced by outliers: 19% (moderately inflated) After the change: benchmarking random ints/greg time 2.576 s (2.548 s .. 2.628 s) 1.000 R² (1.000 R² .. 1.000 R²) mean 2.590 s (2.578 s .. 2.599 s) std dev 12.99 ms (0.0 s .. 14.89 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking random ints/gSort time 2.538 s (2.412 s .. 2.627 s) 1.000 R² (0.999 R² .. 1.000 R²) mean 2.543 s (2.517 s .. 2.560 s) std dev 26.16 ms (0.0 s .. 30.21 ms) variance introduced by outliers: 19% (moderately inflated) On Sun, Mar 26, 2017 at 1:54 PM, Siddhanathan Shanmugam <siddhanathan+eml(a)gmail.com> wrote: Theoretically, we could do better. We currently only exploit monotonic runs in merge sort, but we could also exploit bitonic runs: dlist as = as [] `seq` as [] sequences [] = [[]] sequences [a] = [[a]] sequences (a:xs) = bitonic a a (a:) xs bitonic min max as (b:bs) | b `cmp` max /= LT = bitonic min b (as . (b:)) bs | b `cmp` min /= GT = bitonic b max ((b:) . as) bs | otherwise = dlist as : sequences (b:bs) bitonic _ _ as [] = [dlist as] The constant factors here might be too high to notice the difference though. > However, still my version is more laziness-friendly, i.e. it requires fewer > comparisons to get the > N smallest elements of a list (see > https://github.com/greg7mdp/ <https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs> ghc-sort/blob/master/src/sort_with_trace.hs). > > I wonder if this might not be a more useful trait than being able to sort > already sorted lists super fast. This comes down to a discussion of merge sort vs natural merge sort. Data.List.sort is an implementation of a variant of merge sort called natural merge sort. The algorithm is linearithmic in the worst case, but linear in the best case (already sorted list). On Sun, Mar 26, 2017 at 10:47 AM, Gregory Popovitch <greg7mdp(a)gmail.com> wrote: Thanks again @Siddhanathan! Looks like your gSort fixes the main issue with Data.List.sort(). I have updated the test programs in https://github.com/greg7mdp/gh <https://github.com/greg7mdp/ghc-sort> c-sort to include your new version. Here are the results (your new version looks like a definite improvement vs the current GHC one): input GHC sort My Orig proposal gSort ---------------------------------------------------------------------------- --- sorted ints (ascending) 151 456 148 sorted ints (descending) 152 466 155 random ints 2732 2006 2004 random strings 6564 5549 5528 So replacing the current GHC version with gSort is a no brainer, as it is better in all regards. However, still my version is more laziness-friendly, i.e. it requires fewer comparisons to get the N smallest elements of a list (see https://github.com/greg7mdp/gh <https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs> c-sort/blob/master/src/sort_with_trace.hs). I wonder if this might not be a more useful trait than being able to sort already sorted lists super fast. Thanks, greg ________________________________ From: siddhanathan(a)gmail.com [mailto:siddhanathan@gmail.com] On Behalf Of Siddhanathan Shanmugam Sent: Sunday, March 26, 2017 1:05 PM To: Gregory Popovitch Cc: Haskell Libraries Subject: Re: Proposal: a new implementation for Data.List.sort and Data.List.sortBy, which has better performance characteristics and is more laziness-friendly. Interesting. You are right, performance for sorting random lists has priority over performance for sorting already-sorted lists. Ignore the numbers for my previous version. Can you compare GHC's sort, your proposal, and gSort below? gSort :: Ord a => [a] -> [a] gSort = gSortBy compare gSortBy cmp = mergeAll . sequences where sequences (a:b:xs) | a `cmp` b == GT = descending b [a] xs | otherwise = ascending b (a:) xs sequences xs = [xs] descending a as (b:bs) | a `cmp` b == GT = descending b (a:as) bs descending a as bs = (a:as) : sequences bs ascending a as (b:bs) | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs ascending a as bs = as [a] `seq` as [a] : sequences bs mergeAll [x] = x mergeAll xs = mergeAll (mergePairs xs) mergePairs (a:b:xs) = merge a b : mergePairs xs mergePairs xs = xs merge as@(a:as') bs@(b:bs') | a `cmp` b == GT = b : merge as bs' | otherwise = a : merge as' bs merge [] bs = bs merge as [] = as Thanks, Sid On Sun, Mar 26, 2017 at 9:19 AM, Gregory Popovitch <greg7mdp(a)gmail.com> wrote: Thank you @Siddhanathan! I welcome any improvement you may make, as I said I am very far from a Haskell expert. I just tested your change with my test project (https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort> hc-sort <https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort> hc-sort> ) and here are my results (mean times in ms): input GHC sort Orig proposal your change ---------------------------------------------------------------------------- --- sorted ints (ascending) 153 467 139 sorted ints (descending) 152 472 599 random ints 2824 2077 2126 random strings 6564 5613 5983 Your change is a definite improvement for sorted integers in ascending order, but is worse for other cases. Is there a real need to optimize the sort for already sorted list? Of course it should not be a degenerate case and take longer than sorting random numbers, but this is not the case here. Sorting already sorted lists is, even with my version, over 4 times faster than sorting random lists. This sounds perfectly acceptable to me, and I feel that trying to optimize this specific case further, if it comes at the detriment of the general case, is not desirable. Thanks, greg ________________________________ From: siddhanathan(a)gmail.com [mailto:siddhanathan@gmail.com] On Behalf Of Siddhanathan Shanmugam Sent: Sunday, March 26, 2017 11:41 AM To: Gregory Popovitch Cc: Haskell Libraries Subject: Re: Proposal: a new implementation for Data.List.sort and Data.List.sortBy, which has better performance characteristics and is more laziness-friendly. Thank you! This identifies a space leak in base which went unnoticed for 7 years. Your implementation can be improved further. Instead of splitting into pairs, you could instead split into lists of sorted sublists by replacing the pairs function with the following pair = foldr f [] where f x [] = [[x]] f x (y:ys) | x `cmp` head y == LT = (x:y):ys | otherwise = [x]:y:ys This should give you the same performance improvements for sorting random lists, but better performance while sorting ascending lists. The version in base takes it one step further by using a DList to handle the descending case efficiently as well, except there's a space leak right now because of which it is slower. On Sun, Mar 26, 2017 at 7:21 AM, Gregory Popovitch <greg7mdp(a)gmail.com> wrote: Motivation: ---------- Data.List.sort is a very important functionality in Haskell. I believe that the proposed implementation is: - significantly faster than the current implementation on unsorted lists, typically 14% to 27% faster - more laziness-friendly, i.e.: take 3 $ sort l will require significantly less comparisons than the current implementation Proposed Implementation ----------------------- sort :: (Ord a) => [a] -> [a] sort = sortBy compare sortBy cmp [] = [] sortBy cmp xs = head $ until (null.tail) reduce (pair xs) where pair (x:y:t) | x `cmp` y == GT = [y, x] : pair t | otherwise = [x, y] : pair t pair [x] = [[x]] pair [] = [] reduce (v:w:x:y:t) = merge v' x' : reduce t where v' = merge v w x' = merge x y reduce (x:y:t) = merge x y : reduce t reduce xs = xs merge xs [] = xs merge [] ys = ys merge xs@(x:xs') ys@(y:ys') | x `cmp` y == GT = y : merge xs ys' | otherwise = x : merge xs' ys Effect and Interactions ----------------------- I have a stack project with a criterion test for this new implementation, available at https://github.com/greg7mdp/gh <https://github.com/greg7mdp/ghc-sort> c-sort <https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort> hc-sort> <https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort> hc-sort <https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort> hc-sort> > . I ran the tests on an Ubuntu 14.0.2 VM and GHC 8.0.2, and had the following results: - sorting of random lists of integers is 27% faster - sorting of random lists of strings is 14% faster - sorting of already sorted lists is significantly slower, but still much faster than sorting random lists - proposed version is more laziness friendly. For example this version of sortBy requires 11 comparisons to find the smallest element of a 15 element list, while the default Data.List.sortBy requires 15 comparisons. (see https://github.com/greg7mdp/gh <https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs> c-sort/blob/master/src/sort_with_trace.hs <https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs> hc-sort/blob/master/src/sort_with_trace.hs> <https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs> hc-sort/blob/master/src/sort_with_trace.hs <https://github.com/greg7mdp/g <https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs> hc-sort/blob/master/src/sort_with_trace.hs> > ) Test results ------------ Criterion output (descending/ascending results are for already sorted lists). I barely understand what Criterion does, and I am puzzled with the various "T" output - maybe there is a bug in my bench code: vagrant@vagrant-ubuntu-trusty-64:/vagrant$ stack exec ghc-sort benchmarking ascending ints/ghc TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtime 160.6 ms (153.4 ms .. 167.8 ms) 0.997 R² (0.986 R² .. 1.000 R²) mean 161.7 ms (158.3 ms .. 165.9 ms) std dev 5.210 ms (3.193 ms .. 7.006 ms) variance introduced by outliers: 12% (moderately inflated) benchmarking ascending ints/greg TTTTTTTTTTTTTTTTtime 473.8 ms (398.6 ms .. 554.9 ms) 0.996 R² (0.987 R² .. 1.000 R²) mean 466.2 ms (449.0 ms .. 475.0 ms) std dev 14.94 ms (0.0 s .. 15.29 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking descending ints/ghc TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtime 165.1 ms (148.2 ms .. 178.2 ms) 0.991 R² (0.957 R² .. 1.000 R²) mean 158.7 ms (154.0 ms .. 164.3 ms) std dev 7.075 ms (4.152 ms .. 9.903 ms) variance introduced by outliers: 12% (moderately inflated) benchmarking descending ints/greg TTTTTTTTTTTTTTTTtime 471.7 ms (419.8 ms .. 508.3 ms) 0.999 R² (0.995 R² .. 1.000 R²) mean 476.0 ms (467.5 ms .. 480.0 ms) std dev 7.447 ms (67.99 as .. 7.865 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking random ints/ghc TTTTTTTTTTTTTTTTtime 2.852 s (2.564 s .. 3.019 s) 0.999 R² (0.997 R² .. 1.000 R²) mean 2.812 s (2.785 s .. 2.838 s) std dev 44.06 ms (543.9 as .. 44.97 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking random ints/greg TTTTTTTTTTTTTTTTtime 2.032 s (1.993 s .. 2.076 s) 1.000 R² (1.000 R² .. 1.000 R²) mean 2.028 s (2.019 s .. 2.033 s) std dev 7.832 ms (0.0 s .. 8.178 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking shakespeare/ghc TTTTTTTTTTTTTTTTtime 6.504 s (6.391 s .. 6.694 s) 1.000 R² (1.000 R² .. 1.000 R²) mean 6.499 s (6.468 s .. 6.518 s) std dev 28.85 ms (0.0 s .. 32.62 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking shakespeare/greg TTTTTTTTTTTTTTTTtime 5.560 s (5.307 s .. 5.763 s) 1.000 R² (0.999 R² .. 1.000 R²) mean 5.582 s (5.537 s .. 5.607 s) std dev 39.30 ms (0.0 s .. 43.49 ms) variance introduced by outliers: 19% (moderately inflated) Costs and Drawbacks ------------------- The only cost I see is the reduced performance when sorting already sorted lists. However, since this remains quite efficient, indeed over 4 times faster than sorting unsorted lists, I think it is an acceptable tradeoff. Final note ---------- My Haskell is very rusty. I worked on this a couple years ago when I was learning Haskell, and meant to propose it to the Haskell community, but never got to it at the time. _______________________________________________ Libraries mailing list Libraries(a)haskell.org http://mail.haskell.org/cgi-bi <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries> n/mailman/listinfo/libraries <http://mail.haskell.org/cgi-b <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries> in/mailman/listinfo/libraries> <http://mail.haskell.org/cgi-b <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries> in/mailman/listinfo/libraries <http://mail.haskell.org/cgi-b <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries> in/mailman/listinfo/libraries> >

4 13

Proposal: a new implementation for Data.List.sort and Data.List.sortBy, which has better performance characteristics and is more laziness-friendly.
by Gregory Popovitch 27 Mar '17

27 Mar '17

Motivation: ---------- Data.List.sort is a very important functionality in Haskell. I believe that the proposed implementation is: - significantly faster than the current implementation on unsorted lists, typically 14% to 27% faster - more laziness-friendly, i.e.: take 3 $ sort l will require significantly less comparisons than the current implementation Proposed Implementation ----------------------- sort :: (Ord a) => [a] -> [a] sort = sortBy compare sortBy cmp [] = [] sortBy cmp xs = head $ until (null.tail) reduce (pair xs) where pair (x:y:t) | x `cmp` y == GT = [y, x] : pair t | otherwise = [x, y] : pair t pair [x] = [[x]] pair [] = [] reduce (v:w:x:y:t) = merge v' x' : reduce t where v' = merge v w x' = merge x y reduce (x:y:t) = merge x y : reduce t reduce xs = xs merge xs [] = xs merge [] ys = ys merge xs@(x:xs') ys@(y:ys') | x `cmp` y == GT = y : merge xs ys' | otherwise = x : merge xs' ys Effect and Interactions ----------------------- I have a stack project with a criterion test for this new implementation, available at https://github.com/greg7mdp/ghc-sort. I ran the tests on an Ubuntu 14.0.2 VM and GHC 8.0.2, and had the following results: - sorting of random lists of integers is 27% faster - sorting of random lists of strings is 14% faster - sorting of already sorted lists is significantly slower, but still much faster than sorting random lists - proposed version is more laziness friendly. For example this version of sortBy requires 11 comparisons to find the smallest element of a 15 element list, while the default Data.List.sortBy requires 15 comparisons. (see https://github.com/greg7mdp/ghc-sort/blob/master/src/sort_with_trace.hs) Test results ------------ Criterion output (descending/ascending results are for already sorted lists). I barely understand what Criterion does, and I am puzzled with the various "T" output - maybe there is a bug in my bench code: vagrant@vagrant-ubuntu-trusty-64:/vagrant$ stack exec ghc-sort benchmarking ascending ints/ghc TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtime 160.6 ms (153.4 ms .. 167.8 ms) 0.997 R² (0.986 R² .. 1.000 R²) mean 161.7 ms (158.3 ms .. 165.9 ms) std dev 5.210 ms (3.193 ms .. 7.006 ms) variance introduced by outliers: 12% (moderately inflated) benchmarking ascending ints/greg TTTTTTTTTTTTTTTTtime 473.8 ms (398.6 ms .. 554.9 ms) 0.996 R² (0.987 R² .. 1.000 R²) mean 466.2 ms (449.0 ms .. 475.0 ms) std dev 14.94 ms (0.0 s .. 15.29 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking descending ints/ghc TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTtime 165.1 ms (148.2 ms .. 178.2 ms) 0.991 R² (0.957 R² .. 1.000 R²) mean 158.7 ms (154.0 ms .. 164.3 ms) std dev 7.075 ms (4.152 ms .. 9.903 ms) variance introduced by outliers: 12% (moderately inflated) benchmarking descending ints/greg TTTTTTTTTTTTTTTTtime 471.7 ms (419.8 ms .. 508.3 ms) 0.999 R² (0.995 R² .. 1.000 R²) mean 476.0 ms (467.5 ms .. 480.0 ms) std dev 7.447 ms (67.99 as .. 7.865 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking random ints/ghc TTTTTTTTTTTTTTTTtime 2.852 s (2.564 s .. 3.019 s) 0.999 R² (0.997 R² .. 1.000 R²) mean 2.812 s (2.785 s .. 2.838 s) std dev 44.06 ms (543.9 as .. 44.97 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking random ints/greg TTTTTTTTTTTTTTTTtime 2.032 s (1.993 s .. 2.076 s) 1.000 R² (1.000 R² .. 1.000 R²) mean 2.028 s (2.019 s .. 2.033 s) std dev 7.832 ms (0.0 s .. 8.178 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking shakespeare/ghc TTTTTTTTTTTTTTTTtime 6.504 s (6.391 s .. 6.694 s) 1.000 R² (1.000 R² .. 1.000 R²) mean 6.499 s (6.468 s .. 6.518 s) std dev 28.85 ms (0.0 s .. 32.62 ms) variance introduced by outliers: 19% (moderately inflated) benchmarking shakespeare/greg TTTTTTTTTTTTTTTTtime 5.560 s (5.307 s .. 5.763 s) 1.000 R² (0.999 R² .. 1.000 R²) mean 5.582 s (5.537 s .. 5.607 s) std dev 39.30 ms (0.0 s .. 43.49 ms) variance introduced by outliers: 19% (moderately inflated) Costs and Drawbacks ------------------- The only cost I see is the reduced performance when sorting already sorted lists. However, since this remains quite efficient, indeed over 4 times faster than sorting unsorted lists, I think it is an acceptable tradeoff. Final note ---------- My Haskell is very rusty. I worked on this a couple years ago when I was learning Haskell, and meant to propose it to the Haskell community, but never got to it at the time.

4 10