- Libraries - Haskell.org

Proposal: Use (.) and id from Control.Category in Prelude
by Carter Charbonneau 21 Jul '14

21 Jul '14

(.) and id are generalized in the Category class in Control.Category. In the past, many libraries have instructed users to use (.) and id from Control.Category for composition of their types. Importing these types into Prelude shouldn't break existing code, and makes libraries that use Category easier to use. Discussion period: 4 weeks

12 15

Planning a Haskell Platfrom Release Candidate this weekend
by Mark Lentczner 21 Jul '14

21 Jul '14

Here's my remaining list before putting out a realse candidate. I'm aiming for this weekend: *-- General --* [ ] haddock linkage from HP packages to GHC core packages is broken [ ] decision on QuickCheck? *-- Source Tarball --* [ ] missing platform.sh scripts [ ] missing os-extras in hptool/src *-- Mac --* [ ] start.html needs a once over updating [ ] uninstall-hs should clean out /usr/local/bin symlinks (as it does with /usr/bin) *-- Windows --* [ ] GLUT issue in ghci *-- Website --* [ ] templatize info on pages [ ] add build mode to bptool Main - needs to take file of downloads & hashes Anyone have anything else? Otherwise... we're almost good to go!!!! - Mark

1 1

Proposal: add uncons (and unsnoc) to Data.List
by David Feuer 21 Jul '14

21 Jul '14

Alexander Berntsen indicates that he has a branch all ready to go. Henning Thienemann seems to prefer the term viewL. Alexander says that Edward Kmett says that uncons/unsnoc is the more common term. Personally, I find uncons and unsnoc to be more intuitive names. Details: uncons :: [a] -> Maybe (a, [a]) uncons [] = Nothing uncons (a:as) = Just (a,as) -- Henning's implementation of "viewR", renamed, looks like unsnoc :: [a] -> Maybe ([a], a) unsnoc = foldr (\x -> Just . forcePair . maybe ([],x) (mapFst (x:))) Nothing I wonder if it would be possible to tease that apart a bit to get the maybe out of the loop, which I think might be prettier. The really tricky part of unsnoc is making it lazy enough—messing around with it a bit suggested that it's very easy to mess up the pair lifting. The tough rule seems to be this mouthful, if I'm not mistaken: unsnoc (xs ++ (y : _|_)) = Just (xs ++ _|_, _|_) David

9 11

Proposal: add 'equating' function to Data.List
by Frerich Raabe 21 Jul '14

21 Jul '14

Hi, A common use case for 'on' (from Data.Function) is to use it with 'compare', e.g. 'compare `on` snd'. In fact, this pattern is so common that there's a convenient 'comparing' function which provides a shortcut for this use case such that one can write sortBy (comparing snd) instead of sortBy (compare `on` snd) I think another common use case is to use 'on' together with (==) as in groupBy ((==) `on` snd) In a similiar vein as with 'comparing', I think it would be nice if there was a function which encapsulates this use case, like equating :: Eq b => (a -> b) -> a -> a -> Bool equating = on (==) such that one can write groupBy (equating snd) In fact, groupBy is just one of many *By functions taking an a -> a -> Bool -- many of which are Data.List, e.g. groupBy, nubBy, deleteBy, intersectBy, unionBy. Hence, it seems plausible to define 'equating' in Data.List. This is the same reasoning as why 'comparing' is in Data.Ord: because the module exposes a lot of *By functions taking an a -> a -> Ordering. - Frerich

11 28

Re: Add instances for Functor, Monad, Applicative to Data.Monoid.First, Last
by Ben Gamari 20 Jul '14

20 Jul '14

Edward Kmett wrote, > I'd say we should just act upon it. At this point what it needs is a patch. > You mean like this one against GHC master? Cheers, - Ben

2 3

Network.CGI maintenance - character encodings
by Jon Fairbairn 20 Jul '14

20 Jul '14

There is a problem with character handling for form inputs in Network.CGI. Back in December 2013 I emailed the listed maintainer — Anders Kaseorg <andersk(a)mit.edu> — and got no response. I mentioned the issue on here shortly after that. I’ve now tracked the problem down to web browsers using Windows-1252 as the de-facto standard for form data, patched the code to take account of this and sent another message a to andersk fortnight ago, again with no response. Is there someone out there with commit rights to whom I can send the patch? -- Jón Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk

1 0

Re: Speeding up Data.List.inits
by David Feuer 19 Jul '14

19 Jul '14

I did a little more benchmarking, and it turns out that the overhead to use Okasaki-style persistently efficient banker's queues is not terribly severe because these queues are simple and therefore fast (it's around 1.5 times as slow at its very worst, but that may have been a fluke--the performance generally seems comparable). It does indeed give far, far better performance when looking at the heads of many of the lists at the end of the result, as Edward Kmett predicted. I don't know if these queues are available in a standard library, but the following is a full implementation of initsQ, including what it needs of the queue implementation: data Queue a = Queue {front :: [a], lenF :: Int, rear :: [a], lenR ::Int} deriving (Show) empty = Queue {front=[],lenF=0,rear=[],lenR=0} queue f lF r lR | lR <= lF = Queue f lF r lR | otherwise = Queue {front = f ++ reverse r, lenF = lF + lR, rear = [], lenR = 0} (Queue f lF r lR) |> x = queue f lF (x:r) (lR+1) toListQ (Queue f _ r _) = f ++ reverse r initsQ xs = map toListQ (scanl (|>) empty xs) On Sat, Jul 19, 2014 at 5:25 AM, Edward Kmett <ekmett(a)gmail.com> wrote: > > The half-baked thought was that reaching the kth list is O(k), and reversing _each list_ is O(k), but with a smarter structure you might share some of the work of construction across multiple lists. e.g. if you had an inits like function that returned a list of queues rather than a list of lists you could actually do less work overall setting up the inits asymptotically, sharing the work. If you only take a constant prefix off each queue then this can change the overhead from O(n^2) to = O(kn). > > A reversal or difference list requires you to pay separately for each list. > > I we are in "violent agreement", however, as I indicated in my comment that the constant factors almost definitely make it a non-starter for something like Data.List. ;) > > -Edward > > > On Sat, Jul 19, 2014 at 4:30 AM, David Feuer <david.feuer(a)gmail.com> wrote: >> >> Edward Kmett, reaching the kth list is O(k). Reversing it is also O(k). I don't know that anything as fancy as something by Okasaki could improve matters—such data structures tend to have large constant factors. Something much worse than that seems to be wrong with the Data.List version at the moment. >> >> >> On Sat, Jul 19, 2014 at 4:25 AM, Edward Kmett <ekmett(a)gmail.com> wrote: >>> >>> Good catch, the common inits and tails version of subsequences makes pretty heavy use of that, as do many of the uses of inits where you use it to get k-element substrings. >>> >>> I'd be curious if an okasaki-style catenable output restricted deque could recover both efficient head access and reasonably efficient appends, but the overhead of that is probably way out of line with the performance at stake! >>> >>> -Edward >>> >>> >>> On Sat, Jul 19, 2014 at 4:14 AM, Henning Thielemann <schlepptop(a)henning-thielemann.de> wrote: >>>> >>>> Am 19.07.2014 09:51, schrieb David Feuer: >>>> >>>> >>>>> Background: I was looking at the code for Data.List.inits in >>>>> base-4.7.0.0 (function renamed for clarity): >>>>> >>>>> initsDL :: [a] -> [[a]] >>>>> initsDL xs = [] : case xs of >>>>> [] -> [] >>>>> x : xs' -> map (x :) (initsDL xs') >>>>> >>>>> The recursive maps made me suspicious. I decided to try writing a >>>>> different version: >>>>> >>>>> initsHO xs = map ($ []) (scanl q id xs) >>>>> where >>>>> q f x = f . (x:) >>>>> >>>>> I mentioned this on #haskell and noted that it would be a nice exercise >>>>> to write it with less fancy function footwork using map reverse. rasfar >>>>> responded (modulo naming) with >>>>> >>>>> initsR xs = map reverse (scanl q [] xs) >>>>> where >>>>> q acc x = x : acc >>>> >>>> >>>> >>>> The 'map' gives efficient access to the first elements of the sub-lists, thus it seems that initsDL is faster than initsR when you access only prefixes of the sub-lists. E.g. >>>> >>>> Prelude> head $ last $ inits [0..10000000::Int] >>>> >>>> _______________________________________________ >>>> Libraries mailing list >>>> Libraries(a)haskell.org >>>> http://www.haskell.org/mailman/listinfo/libraries >>> >>> >> >

1 1

Speeding up Data.List.inits
by David Feuer 19 Jul '14

19 Jul '14

Summary: yes, we can, by a LOT. Yes, I know how. Yes, I've done some benchmarking to demonstrate. Yes, it is even very simple. And yes, the results are correct, including laziness requirements. Background: I was looking at the code for Data.List.inits in base-4.7.0.0 (function renamed for clarity): initsDL :: [a] -> [[a]] initsDL xs = [] : case xs of [] -> [] x : xs' -> map (x :) (initsDL xs') The recursive maps made me suspicious. I decided to try writing a different version: initsHO xs = map ($ []) (scanl q id xs) where q f x = f . (x:) I mentioned this on #haskell and noted that it would be a nice exercise to write it with less fancy function footwork using map reverse. rasfar responded (modulo naming) with initsR xs = map reverse (scanl q [] xs) where q acc x = x : acc rasfar ran a few informal benchmarks suggesting that initsR is faster than initsHO, which in turn is significantly faster than the current implementation in Data.List. I have now run Criterion benchmarks testing performance in three ways: reduction of inits [1..n] to normal form, reduction of (inits [1..n])!!(n-1) to normal form, and reduction of (length (inits [1..n])) to normal form. In each case the Criterion test case is the list [1..n], so there is no risk of some sort of weird fusion occurring. The results are extremely clear in all three test scenarios, with a variety of values of n: initsR is a little faster than initsHO, and inits HO is much, much faster than initsDL. The differences become apparent even for small values of n (10-50), but when n gets up to 100000, you don't even want to wait for initsDL to finish. This was all using ghc 7.8.3 with -O2. I've attached my benchmarking code, which also includes some basic correctness and laziness tests. Note that the first group of benchmarks tests a variety of vaues of n. For the second group, I was tired so I just twiddled it by hand. For the third group... Criterion estimated that benchmarking length(initsDL(100000)) would take 124582.9 seconds, so I decided to stop there. Conclusion: we should replace Data.List.inits with initsR, unless someone comes up with something that beats initsR.

3 6

Re: speeding up inits
by David Feuer 19 Jul '14

19 Jul '14

The test code was missing a line, because I kept messing that line up. I rewrote it more simply, and that test passed too. Sorry for the extra message.

1 0

add IsList instance to Data.Sequence
by Carter Schonwald 16 Jul '14

16 Jul '14

seems like an oversight in ghc 7.8 release of containers, but worth adding! I'm willing to write the patch etc if everyone ok's this discussion period: 2 weeks

2 1