<p dir="ltr">In fact, since the queues are only used in a very restricted way, we can make them even smaller. Something like this (completely untested) code:</p>
<p dir="ltr">data Queue a = Queue {-# UNPACK #-}!Int [a] [a]</p>
<p dir="ltr">empty = Queue 1 [] []</p>
<p dir="ltr">queue sp1 f r<br>
| popCount sp1 /= 1 = Queue sp1 f r<br>
| otherwise. = Queue sp1 (f ++ reverse r) []<br>
(Queue sp1 f r) |> x = queue (sp1 + 1) f (x:r)<br>
toListQ (Queue _ f r) = f ++ reverse r</p>
<div class="gmail_quote">On Jul 19, 2014 1:33 PM, "David Feuer" <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br type="attribution"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I did a little more benchmarking, and it turns out that the overhead<br>
to use Okasaki-style persistently efficient banker's queues is not<br>
terribly severe because these queues are simple and therefore fast<br>
(it's around 1.5 times as slow at its very worst, but that may have<br>
been a fluke--the performance generally seems comparable). It does<br>
indeed give far, far better performance when looking at the heads of<br>
many of the lists at the end of the result, as Edward Kmett predicted.<br>
I don't know if these queues are available in a standard library, but<br>
the following is a full implementation of initsQ, including what it<br>
needs of the queue implementation:<br>
<br>
data Queue a = Queue<br>
{front :: [a],<br>
lenF :: Int,<br>
rear :: [a],<br>
lenR ::Int} deriving (Show)<br>
<br>
empty = Queue {front=[],lenF=0,rear=[],lenR=0}<br>
<br>
queue f lF r lR<br>
| lR <= lF = Queue f lF r lR<br>
| otherwise = Queue {front = f ++ reverse r,<br>
lenF = lF + lR,<br>
rear = [],<br>
lenR = 0}<br>
<br>
(Queue f lF r lR) |> x = queue f lF (x:r) (lR+1)<br>
<br>
toListQ (Queue f _ r _) = f ++ reverse r<br>
<br>
initsQ xs = map toListQ (scanl (|>) empty xs)<br>
<br>
<br>
<br>
On Sat, Jul 19, 2014 at 5:25 AM, Edward Kmett <<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>> wrote:<br>
><br>
> 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).<br>
><br>
> A reversal or difference list requires you to pay separately for each list.<br>
><br>
> 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. ;)<br>
><br>
> -Edward<br>
><br>
><br>
> On Sat, Jul 19, 2014 at 4:30 AM, David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br>
>><br>
>> 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.<br>
>><br>
>><br>
>> On Sat, Jul 19, 2014 at 4:25 AM, Edward Kmett <<a href="mailto:ekmett@gmail.com">ekmett@gmail.com</a>> wrote:<br>
>>><br>
>>> 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.<br>
>>><br>
>>> 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!<br>
>>><br>
>>> -Edward<br>
>>><br>
>>><br>
>>> On Sat, Jul 19, 2014 at 4:14 AM, Henning Thielemann <<a href="mailto:schlepptop@henning-thielemann.de">schlepptop@henning-thielemann.de</a>> wrote:<br>
>>>><br>
>>>> Am 19.07.2014 09:51, schrieb David Feuer:<br>
>>>><br>
>>>><br>
>>>>> Background: I was looking at the code for Data.List.inits in<br>
>>>>> base-4.7.0.0 (function renamed for clarity):<br>
>>>>><br>
>>>>> initsDL :: [a] -> [[a]]<br>
>>>>> initsDL xs = [] : case xs of<br>
>>>>> [] -> []<br>
>>>>> x : xs' -> map (x :) (initsDL xs')<br>
>>>>><br>
>>>>> The recursive maps made me suspicious. I decided to try writing a<br>
>>>>> different version:<br>
>>>>><br>
>>>>> initsHO xs = map ($ []) (scanl q id xs)<br>
>>>>> where<br>
>>>>> q f x = f . (x:)<br>
>>>>><br>
>>>>> I mentioned this on #haskell and noted that it would be a nice exercise<br>
>>>>> to write it with less fancy function footwork using map reverse. rasfar<br>
>>>>> responded (modulo naming) with<br>
>>>>><br>
>>>>> initsR xs = map reverse (scanl q [] xs)<br>
>>>>> where<br>
>>>>> q acc x = x : acc<br>
>>>><br>
>>>><br>
>>>><br>
>>>> 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.<br>
>>>><br>
>>>> Prelude> head $ last $ inits [0..10000000::Int]<br>
>>>><br>
>>>> _______________________________________________<br>
>>>> Libraries mailing list<br>
>>>> <a href="mailto:Libraries@haskell.org">Libraries@haskell.org</a><br>
>>>> <a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
>>><br>
>>><br>
>><br>
><br>
</blockquote></div>