[Haskell-cafe] Re: Implementing "unionAll"

Heinrich Apfelmus apfelmus at quantentunnel.de
Thu Feb 18 05:05:46 EST 2010

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

Heinrich Apfelmus


More information about the Haskell-Cafe mailing list