[Haskell-cafe] Re: Implementing "unionAll"

18 Feb 2010


      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