July 2014 - Libraries

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

Proposal: add -XPolyKinds to Data.Monoid
by Carl Howells 15 Jul '14

15 Jul '14

At the moment, the Monoid instance for Data.Proxy.Proxy is only defined for types with kind *. Prelude Data.Proxy Data.Monoid> (Proxy :: Proxy String) <> Proxy Proxy Prelude Data.Proxy Data.Monoid> :set -XDataKinds Prelude Data.Proxy Data.Monoid> (Proxy :: Proxy 5) <> Proxy <interactive>:8:20: No instance for (Monoid (Proxy 5)) arising from a use of ‘<>’ In the expression: (Proxy :: Proxy 5) <> Proxy In an equation for ‘it’: it = (Proxy :: Proxy 5) <> Proxy Enabling -XPolyKinds while compiling the Data.Monoid module is the only change necessary to make the Monoid instance for Proxy polykinded like Proxy itself is. I don't believe adding a language pragma would have any other effect on that module, and I believe the only effect of changing that instance would be allowing more correct programs to compile. This is my first proposal to this list, so I'm starting with something that I hope isn't controversial. Let me know if I should do anything different procedurally in future proposals. Thanks.

5 7

Bit shifting limitations
by David Feuer 14 Jul '14

14 Jul '14

The current state of affairs is a bit unsatisfactory. 1. The biggest problem, as I see it, is that while we have shiftR and shiftL, which are documented as giving 0 or -1 when shifting too far, and we have unsafeShiftR and unsafeShiftL, which are likely to do whatever the CPU happens to do, we don't have anything guaranteed to shift using just the first five or six bits of the shift count, which is what Java specifies and what unsafeShiftR and unsafeShiftL *actually* do (at least on x86_64). I propose that we add these masked shifts to Data.Bits. The default implementations can look something like: shiftRMasked x count | popCount (finiteBitSize x) != 1 = error "Masked shift only makes sense if the size is a power of 2." | otherwise = x `unsafeShiftR` (count .&. (finiteBitSize x - 1)) 2. It would be nice to specify what shiftR and shiftL are supposed to do when given negative shift counts. Is there a practical reason not to specify that? 3. I would like to add explicit arithmetic and logical shifts to Data.Bits. When fiddling bits, it's often easier to think about that distinction explicitly, rather than in terms of whether the type is signed or unsigned, and more convenient to have an explicit operation rather than casting around. David

6 21

[ANNOUNCE] New Core Libraries Committee Members
by Edward Kmett 11 Jul '14

11 Jul '14

I'm pleased to announce that Eric Mertens and Luite Stegeman have joined the core libraries committee. http://www.haskell.org/haskellwiki/Core_Libraries_Committee Brent Yorgey and Doug Beardsley stepped down to make room. I'd like to thank them for helping us get the committee started. In the short term Eric will probably help out with moving the Applicative Monad Proposal forward and with the knock-on effects of that change, and Luite will join Joachim Breitner in trying to figure out the right path forward for the split base proposal. -Edward Kmett

1 0