[Haskell-cafe] Re: Implementing "unionAll"

[Leon Smith]

On Wed, Feb 17, 2010 at 6:58 AM, Heinrich Apfelmus
<apfelmus at quantentunnel.de> 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

In the original case,  we have this strictness property

   union' (VIP x xs) ⊥ == ⊥

The revised verison is a bit lazier:

   union' (VIP x xs) ⊥ == VIP x ⊥

And so the simplified unionAll now works again on an infinite number
of lists.   I've uploaded data-ordlist-0.4.2 to fix the bug introduced
with data-ordlist-0.4.1,   and added a regression test to the suite.

Best,
Leon