[Haskell-cafe] Re: Implementing "unionAll"

[Heinrich Apfelmus]

Leon Smith wrote:
> 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

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