March 2017 - Libraries

Functor, Applicative, Monad, Foldable, Traversable instances for (, , ) a b
by Fumiaki Kinoshita 26 Apr '17

26 Apr '17

It's surprising that they are missing (forgive me, I'm not here to make people grumpy).

22 66

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

Data.List.sortBy creates unnecessary thunks
by Siddhanathan Shanmugam 26 Mar '17

26 Mar '17

Data.List.sortBy uses a DList-like representation to efficiently chunk a list, but the final conversion from DList to List is not strict. This leaves unnecessary suspensions while sorting. This was first noticed in https://github.com/ghc-proposals/ghc-proposals/pull/50, where sorting a random list with a naive merge sort is faster than the one in base. Proposing the following change, which should improve performance and space usage. ```diff diff --git a/libraries/base/Data/OldList.hs b/libraries/base/Data/OldList.hs index c3618c42a9..a68c4f42af 100644 --- a/libraries/base/Data/OldList.hs +++ b/libraries/base/Data/OldList.hs @@ -851,7 +851,7 @@ sortBy cmp = mergeAll . sequences ascending a as (b:bs) | a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs - ascending a as bs = as [a]: sequences bs + ascending a as bs = *as [a] `seq`* as [a] : sequences bs mergeAll [x] = x mergeAll xs = mergeAll (mergePairs xs) ``` And, as a side note, can we please add more type signatures and comments to the sort/sortBy function? Cheers, Sid

1 0

PROPOSAL: Add Map/IntMap newtypes for different Monoid to containers
by Merijn Verstraaten 25 Mar '17

25 Mar '17

I would like to propose adding a newtype wrapper (with all relevant instances) for Map and IntMap (if I missed any other applicable type in containers, let me know). This newtype should differ in Monoid/Semigroup instance from Map/IntMap by switching: Ord k => Semigroup (Map k v) Ord k => Monoid (Map k v) to: (Ord k, Semigroup v) => Semigroup (Map k v) (Ord k, Monoid v) => Monoid (Map k v) or (Ord k, Semigroup v) => Monoid (Map k v) Any opinions on the overall idea? Opinions on which Monoid instance? Bikeshed for the newtype names? Cheers, Merijn

7 8

Re: Deprecate Foldable for Either
by Anthony Clayden 24 Mar '17

24 Mar '17

> On Thu Mar 23 15:03:36 UTC 2017, Edward Kmett wrote: > > On Thu, Mar 23, 2017 at 6:18 AM, Anthony Clayden wrote: > > > > Why is `[a]` hard-coded in the signature for > > concat? I would expect anything specific to Lists > > to be genericised: > > concat :: (Foldable t1, Foldable t2) => t1 (t2 a) -> > > t2 a > > > > Foldable can't be used to 'construct' in this way. Thanks Edward for the comprehensive reply. Yes I know Foldable isn't powerful enough to construct. I wasn't seriously proposing that as the signature. I was pointing out that there were several value judgments in arriving at the FTP changes. The decision has gone different ways in different places. It's not all as predictable by cold logic as you're trying to make out below. And you've left people surprised. FTP left `concat` hard-coded to Lists. It left `map` hard-coded to Lists. Why didn't it leave `length` hard-coded to Lists? The promise with FTP was to not break code, and for code that already compiled to continue to work with the same behaviour. Mostly that's been delivered. The counterpart hasn't been delivered: inappropriate uses of some methods (which therefore didn't previously compile -- good) do now compile, and whatever they calculate is a surprise/non-intuitive for a significant number. To my intuition, "length" -- as an English word -- is about structures that have length. I can see the benefit you point out below for having a generic method for size of a Foldable. Most of those Foldables I don't see as having "length". > Neither Foldable f nor even Traversable f give you the > power to construct a new 'f' with different shape. > Exactly. So why even bother with concat (Right [...]); or concat (Just [...]) ? > > concat is just a type restricted version of fold = foldMap > id provided basically for legacy compatibility. > OK. It's arbitrary but your justification is it was always arbitrary. FTP `concat` does the same as pre-FTP `concat`. "For legacy compatibility". By that same argument: pre-FTP `length` wasn't even in Foldable. It was arbitrarily restricted to Lists. "For legacy compatibility" it should have stayed restricted to Lists. > > The Foldable/Traversable proposal was to bring the > functions that already existed in base in Data.Foldable > into the Prelude and eliminate the monomorphic versions of > those combinators that made importing these more general > versions painful for users. `length` was never in Data.Foldable. There was never a more general version. You're blowing smoke. > We didn't set out to make new > functions, merely standardize on the ones folks had been > using for a decade. concat was left intact, because there > was already a generalization available, and no particular > reason to break all the existing code that expected it. > > > Why have an instance of Foldable which always returns > > length 1? > > (Or for some instances returns length 0 or 1.) > > > > Say you go to write a function > > toVector :: Foldable f => f a -> Vector a > toVector xs = Vector.fromListN (length xs) (toList xs) > > With length in Foldable, ... No. Length was not in Foldable. You should have stopped to ask why! You give good reasons for having a method in Foldable that consistently gives a size. Those are not good reasons for calling that method `length` or for breaking expectations that `length` applies for Lists, Not for Foldables. > > A number of container types can use 'length' rather than > having to supply their own monomorphic size function. > Would 'length' have been better called 'size'? Yes! Or `cardinality`. > That is another color the bikeshed could have been colored, That's an arrogant comment. You've allowed mopeds, motorbikes and skateboards into the bikeshed. And now there's not enough room for the bikes. Now you blow smoke that it's only about the colour of the shed. > but it would have involved taking a fresh name, possibly in the > Prelude, and the name collisions of a common name with > existing code was considered to be the greater evil. Data.Set has `size`. It used to have `cardinality`, that was removed. OK not the Prelude, but close enough. `size` in Data.Set does exactly what `length` now does. > > > `concat` and `length` should not be in Foldable. > > They should be in a separate class `Consable` (say), > > which would be a sub-class of Foldable. > > > > length being in such a class would mean that every author .. Would use a sensibly-named method (`size`) when they wanted the, er, size of a Foldable. And using `length` would document the code that they were applying to something that might be lengthy. > ... This would have also > meant dumping a brand new abstraction in Prelude without > the preceding decade worth of experimentation on what > works well. As it is, we've got what? A brand new abstraction (called `length`) in Foldable without a preceding decade worth of experimentation on whether length makes sense for Either or Maybe. Furthermore without a preceding decade worth of telling people that length [1, 2] is 2; but length (1, 2) is 1. > In general the FTP didn't seek to go out of > its way to make up new classes, merely to standardize > existing code ... You're blowing smoke again. There was no existing code using `length` of a Foldable, because `length` wasn't a method. > > While working on the Foldable/Traversable Proposal what > happened was we found we needed to add a number of methods > to the Foldable class to avoid silent changes in the > semantics of existing Haskell programs. Some Foldable > combinators folded in different directions than their > monomorphic counterparts. > OK. How well communicated was that? It certainly couldn't have applied for `length`. The semantics of existing Haskell programs was that `length` worked for Lists. Only for Lists. Not Foldables in general. > Along the way as we worked to fix these infelicities and > noticed that as a side-effect that this allowed Foldable > authors some power to execute these operations with better > asymptotics where possible for their containers. This nice > knock-on effect lets folks shed some names that they were > taking from the environment by using what Prelude offers. > During this process some folks noticed that length/null > fit into the scheme, Well those folks were wrong. What they should have noticed was that `size`/null fit. > ... > > With the choices made all of the "mainstream" base modules > now have no name conflicts and can be imported > unqualified. Good. I am not criticising the FTP change in general, nor its objectives. But moving `length` from Prelude to Foldable isn't justified on those grounds. There wasn't previously a `size` (or equivalent) in Foldable. Why introduce it when there was no experience of "using for a decade" -- if that was the criterion? > > Could we have named them flength (or size) and fnull so > that people had to ask for them explicitly and left > length/null alone? Yes. But it would have meant taking new > names from the Prelude or not re-exporting them from > Data.Foldable, and the AMP/FTP tried to very careful about > introducing any new names to the Prelude, and wanted users > to be able to supply instances without having to > explicitly import Data.Foldable. > > We were very dubious about the response we'd get > introducing new, untested, names to Prelude ... So you preferred to introduce new, unattested behaviour. `length` of an Either is unattested. `length` of a Maybe is unattested. That `length` of (1, 2) is 1 is unattested. > as everyone's code is impacted by that choice Again, no: nobody's code could have been using Foldable length. > and folks happen to be using all the "good" names for such things, Yes that's a problem. > and nobody had done so in the preceding 17 years, Because they couldn't. Because `length` applied only for lists. > so any changes along > those lines are surprising. > So do you think it unsurprising asking for the length of a Maybe? Do you think it unsurprising that the length of (1, 2) is 1? Note: "length", not "size". So did it come as a surprise that people are surprised? I'm not surprised newbies are surprised. They're using tutorials saying length applies for Lists. And concat applies for Lists of Lists. It seems to be not just newbies surprised, judging by how often the question comes up. AntC

2 1

Re: Deprecate Foldable for Either
by Anthony Clayden 23 Mar '17

23 Mar '17

> On Thu Mar 2 16:30:21 UTC 2017 Henning Thielemann wrote: >> On Thu, 2 Mar 2017, Andreas Abel wrote: >> Today a student came to me wondering why a certain function >> produced a regular result, where he had expected an error. >> Turned out he had used `concat`, but not on a lists of lists >> as he had thought, but on a lists of `Either a [b]`. > That is, he did (concat (xs :: [Either a [b]]))? > Does GHC actually accept that? > If at all, it would not have to do with Foldable. Good questions Henning. They've got swamped. I found Andreas' description a bit unclear. We have: concat :: Foldable t => t [a] -> [a] So the `concat` you put above would give an error. To get a result, the student must have put (concat (xs :: Either a [b])) And got result either `[]` from (Left _) or a genuine List from (Right ys). Either way, I'd be grumpy: this hasn't and couldn't concatenate anything. Two thoughts: 1) The FTP hasn't done a very thorough job. Why is `[a]` hard-coded in the signature for concat? I would expect anything specific to Lists to be genericised: concat :: (Foldable t1, Foldable t2) => t1 (t2 a) -> t2 a 2) It's obvious why FTP didn't go that far: (concat (xs :: [Either a [b]])) -- as you speculated -- would be daft. concat only applies for structures that can be concatenated. But that surely includes more than Lists(?) So this is essentially the same complaint as for `length`: Why have an instance of Foldable which always returns length 1? (Or for some instances returns length 0 or 1.) `concat` and `length` should not be in Foldable. They should be in a separate class `Consable` (say), which would be a sub-class of Foldable. Note that `length` used not to be in Foldable. `concat` was, but restricted to Lists, as now. If there's a need for a method in Foldable to return 1 for a tuple, or 0..1 for Maybe/Either, don't call it `length`, call it `cardinality` (say). (This is the same approach as for separate `map`, `fmap`, `foldMap`.) That isn't breaking genericity/polymorphism/library rationalisation, `length` was never previously available for non-List Foldables. So no code could have been using it. `concat` was always in the wrong place, but Foldable (when it was a bit of a rag-bag) used to be good enough. AntC

2 1

Proposal: Make unsafeInterleaveST safer
by David Feuer 22 Mar '17

22 Mar '17

Currently, unsafeInterleaveST is considerably less safe than unsafeInterleaveIO. Specifically, very careful discipline is required to make code using it thread-safe. This means that unsafeInterleaveST actually behaves like unsafeDupableInterleaveIO. See Edward Kmett's blog post from several years ago [*] for details. I propose that we should 1. Make unsafeInterleaveST behave only as unsafely as unsafeInterleaveIO, and 2. Add a new unsafeDupableInterleaveST function implementing the current unsafeInterleaveST behavior. The alternative would be to leave unsafeInterleaveST alone and add a new unsafeNonDupableInterleaveST, but that seems like an absolutely terrible mismatch of names. Since any currently-correct code using unsafeInterleaveST will continue to work (albeit more slowly), I don't think that's justified. Thanks, David [*] https://www.schoolofhaskell.com/school/to-infinity-and-beyond/older-but-sti… f

1 1

Laws for GHC.Generics
by Gershom B 20 Mar '17

20 Mar '17

I had a bit of discussion today on how to handle generic instances for abstract types. It resolved to the following question, in a sense -- what are the laws for the Generic typeclass? Should require that `from` and `to` be an isomorphism of data types (i.e. that `from . to` and `to . from` both be the identity) or should we require only the weaker one-sided retract condition (i.e. that `from . to` be the identity.). If the latter, is it better that `from` be partial (which i prefer) or that it quotient together "equivalent" representations (i.e. representing a map as a `fromList` as syb-generics do). The documentation doesn't seem to provide clear guidance here, and it might be worth discussing if some should be added. Cheers, Gershom

3 4

Re: Deprecate Foldable for Either
by Artyom Kazak 19 Mar '17

19 Mar '17

On 20 Mar 2017 1:31 a.m., "Tony Morris" <tonymorris(a)gmail.com> wrote: "But the inconsistency with my intuition for the function named l-e-n-g-t-h that I learned in C programming school in the 1980s" is the best criteria that I have seen, and which commands outright dismissal. This is exactly my criterion (except that I learned English, not C), and I do not agree with you that it "commands outright dismissal". There is value in functions being as general as possible, etc, but there is also value in conforming to human intuitions – because it prevents people from shooting themselves in their feet. Whether those intuitions come from math, or from C, or from English, or elsewhere, is entirely irrelevant. If behavior of `length` fully conforms to your intuitions, that's splendid and you're lucky; however, for me and my usecases it's *only* a source of pain, and I want a way to free myself of that pain (without having to learn another language or spend time trying to change my intuitions). Wanting to make one's life easier is not an unreasonable desire.

3 4