I see no obvious deficiencies. :) Personally, I'd probably structure it like

http://www.haskell.org/haskellwiki/Prime_numbers#Implicit_Heap

This variant, based on the wiki article, is cleaner, slightly simpler, appears to be just as fast, and allocates slightly less memory:

import GHC.Exts(inline) import Data.List.Ordered(unionBy)

union' :: People Int -> People Int -> People Int union' (VIP x xt) ys = VIP x (union' xt ys) union' (Crowd xs) (Crowd ys) = Crowd (inline unionBy compare xs ys) union' xs@(Crowd (x:xt)) ys@(VIP y yt) = case compare x y of LT -> VIP x (union' (Crowd xt) ys) EQ -> VIP x (union' (Crowd xt) yt) GT -> VIP y (union' xs yt)

foldTree :: (a -> a -> a) -> [a] -> a foldTree f xs = case xs of [] -> [] xs -> loop xs where loop [x] = x loop (x:xs) = x `f` loop (pairs xs)

pairs (x:y:ys) = f x y : pairs ys pairs xs = xs

unions xss = serve $ inline foldTree union' [ VIP x (Crowd xs) | (x:xs) <- xss ] where serve (VIP x xs) = x:serve xs serve (Crowd xs) = xs

One of the differences is that I started with a slightly different "foldTree", one that was taken directly from Data.List.sort. The only problem is that it has the same problem as I mentioned: unionAll [[1,2],[1,2]] == [1,1,2] whereas unionAll is intended to be a generalization of "foldr union []" to an infinite number of lists, and should thus return [1,2]. But I should be able to fix this without much difficulty.

Your loop function is a strange melange of many different concerns (building a tree, union', adding and removing the VIP constructors).

Note that it's currently unclear to me whether the lazy pattern match in

pairs ~(x: ~(y:ys)) = f x y : pairs ys

is beneficial or not; you used a strict one

unionPairs (x:y:zs) = union' x y : unionPairs zs

Well, as the library implementation must work on finite cases as well, the lazy pattern seems out of the question.

If you're really concerned about time & space usage, it might even be worth to abandon the lazy tree altogether and use a heap to achieve the same effect, similar to Melissa O'Neils prime number code. It's not as "neat", but much more predictable. :)

Well, it is intended as a high quality, generally useful implementation, so of course I care about time and space usage. :) Dave Bayer's original algorithm does slightly better, but was much larger in terms of both source code and object size. Omar implemented something along these lines, but it didn't perform so well. I did not dig into the reasons why, though; it might not have had anything to do with the fact an explicit heap was used. Incidentally, I tried implementing something like implicit heaps once upon a time; but it had a severe performance problem, taking a few minutes to produce 20-30 elements. I didn't have a pressing reason to figure out why though, and didn't pursue it further. Best, Leon

The easiest solution is simply to define

unionAll = nub . mergeAll where -- specialized definition of nub nub = map head . groupBy (==)

Talking about the easiest solution, I guess this is a quite easy way of defining unionAll as well: http://gist.github.com/306782 I, of course, do not claim that it is more efficient or better. But I don't think it'd be rubbish :) -- Ozgur Akgun

Ooops I thought the inner lists are possibly of infinite size. On 17 February 2010 17:16, Daniel Fischer wrote:

Am Mittwoch 17 Februar 2010 17:46:38 schrieb Ozgur Akgun:

...

...

The easiest solution is simply to define

unionAll = nub . mergeAll where -- specialized definition of nub nub = map head . groupBy (==)

Talking about the easiest solution, I guess this is a quite easy way of defining unionAll as well: http://gist.github.com/306782 I, of course, do not claim that it is more efficient or better. But I don't think it'd be rubbish :)

let next = minimum (map head xs')

doesn't work if you have infinitely many lists :( _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Ozgur Akgun

On Wed, Feb 17, 2010 at 6:58 AM, Heinrich Apfelmus wrote:

Ah, I meant to use the  union'  from your previous message, but I think that doesn't work because it doesn't have the crucial property that the case

   union (VIP x xs) ys = ...

does not pattern match on the second argument.

Ahh yes, the funny thing is that I tested the code in my previous message, and it worked in the infinite case. Then I replaced the union' to pattern match on the second argument as well, and tested it on only finite cases, and then released it. Thus, unionAll in data-ordlist-0.4.1 doesn't work on an infinite number of lists. So my original unionAll in data-ordlist-0.4 appears to work ok, my revised and simplified unionAll doesn't work at all.

The easiest solution is simply to define

   unionAll = nub . mergeAll        where        -- specialized definition of  nub        nub = map head . groupBy (==)

Incidentally, data-ordlist has a (slightly different) version of nub that does exactly what you want in this particular case. Check out the documentation for "nub" and "nubBy"

But you're probably concerned that filtering for duplicates afterwards will be less efficient. After all, the (implicit) tree built by mergeAll  might needlessly compare a lot of equal elements.

Well, yes and no. Efficiency is good, but this implementation does not match my intention. For example: unionAll [[1,1,2,2,2],[1,1,1,2]] == foldr union [] [...] == [1,1,1,2,2,2] The "union" function preserves strictly ascending lists, but it also works on multisets as well, returning an element as many times as the maximum number of times in either list. Thus, on an infinite number of lists, unionAll should return a particular element as many times as the maximum number of times it appears in any single list. On Wed, Feb 17, 2010 at 1:18 PM, Daniel Fischer wrote:

Am Mittwoch 17 Februar 2010 18:59:42 schrieb Ozgur Akgun:

...

Ooops I thought the inner lists are possibly of infinite size.

Both, I think.

Yes, both the inner and outer lists of an input to unionAll might be infinite. It's just that foldr union [] works fine if the inner lists are infinite, but gets stuck in an infinite non-productive list if the outer list is infinite. Best, Leon

By purest coincidence I just wrote the exact same function (the simple mergeAll', not the VIP one). Well, extensionally the same... intensionally mine is 32 complicated lines and equivalent to the 3 line mergeAll'. I even thought of short solution by thinking that pulling the first element destroys the ascending lists property so it's equivalent to a normal sorted merge after that, and have no idea why I didn't just write it that way. Anyway, I'm dropping mine and downloading data-ordlist. Thanks for the library *and* the learning experience :)

On Thu, Feb 18, 2010 at 8:07 AM, Evan Laforge wrote:

And BTW again, here's something I've occasionally found useful:

-- | Handy to merge or sort a descending list. reverse_compare :: (Ord a) => a -> a -> Ordering reverse_compare a b = case compare a b of    LT -> GT    EQ -> EQ    GT -> LT

I wondered why there wasn't one of these in the standard library until someone pointed out to me that reverse_compare = flip compare which actually takes fewer characters to type :P

On Thu, Feb 18, 2010 at 5:22 PM, Leon Smith wrote:

On Thu, Feb 18, 2010 at 3:07 AM, Evan Laforge wrote:

...

BTW, I notice that your merges, like mine, are left-biased.  This is a useful property (my callers require it), and doesn't seem to cost anything to implement, so maybe you could commit to it in the documentation?

Ohh, I see it now, I just wasn't looking at the module doc.

Also, I did briefly consider giving up left bias.  GHC has an optimization strategy that seeks to reduce pattern matching,  and due to interactions with this I could have saved a few kilobytes of -O2 object code size by giving up left-bias.

Interesting... but left bias is so useful I think it's worth a few extra k.

If you are curious why,  I suggest taking a look at GHC's core output for each of these two variants.   The hackage package "ghc-core" makes this a little bit more pleasant,  as it can pretty-print it for you.

I can see there's one extra case in the first one, and I can tell the last case is the 'loop' case including the case on Ordering, but I admit I don't understand what the previous cases are doing. Core is really hard for me to read.

It's amazing to think that this library,  at 55k (Optimized -O2 for x64),  would take up most of the memory of my very first computer,  a Commodore 64.   Of course,  I'm sure there are many others on this list who's first computers had a small fraction of 64k of memory to play with.  :-)

It's not even that much assembly. I intended to write a small quick program... then I did it in haskell, and then I linked in the GHC API (fatal blow). Now the stripped optimized binary is 22MB (optimization doesn't seem to have an effect on size). The non-haskell UI part is 367k...

Leon Smith wrote:

On Wed, Feb 17, 2010 at 6:58 AM, Heinrich Apfelmus wrote:

...

Ah, I meant to use the union' from your previous message, but I think that doesn't work because it doesn't have the crucial property that the case

union (VIP x xs) ys = ...

does not pattern match on the second argument.

Ahh yes, my original union' has a bit that looks like this

union' (VIP x xs) (VIP y ys) = case cmp x y of LT -> VIP x (union' xs (VIP y ys)) EQ -> VIP x (union' xs ys) GT -> error "Data.List.Ordered.unionAll: assumption violated!" union' (VIP x xs) (Crowd ys) = VIP x (union' xs (Crowd ys))

For whatever reason, this works in the case of an infinite number of lists with my original version, but not the simplified version. By applying a standard transformation to make this lazier, we can rewrite these clauses as

union' (VIP x xs) ys = VIP x $ case ys of Crowd _ -> union' xs ys VIP y yt -> case cmp x y of LT -> union' xs ys EQ -> union' xs yt GT -> error msg

Oops, I missed this simple rewrite, mainly because the GT case did not start with the VIP x constructor. :D Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com