[Haskell-cafe] Re: Implementing "unionAll"
leon.p.smith at gmail.com
Wed Feb 17 23:52:38 EST 2010
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.
More information about the Haskell-Cafe