[Haskell-cafe] Re: inversion lists

[Ted Zlatanov]

On Thu, 19 Nov 2009 04:54:13 +0100 Daniel Fischer <daniel.is.fischer at web.de> wrote: 

DF> h :: Num a => a -> [a] -> [a]
DF> h x (y:ys)
DF>     | x+1 == y = x:ys
DF> h x zs = x:(x+1):zs

DF> invlist = foldr h []

ghci> invlist [2,3,4,5,8,9,10]
DF> [2,6,8,11]
ghci> invlist [4]
DF> [4,5]
ghci> invlist [1,2,3,4,7,8,9,13,14,15,20,22]
DF> [1,5,7,10,13,16,20,21,22,23]

That's nice, thanks for the elegant code.  I was hoping to make it work
lazily with foldl, if you have the interest in implementing it that
way.  I tried but failed (no, you can't see my attempt :)

A nice property of inversion lists is that inverting them simply
requires removing or adding the minimum possible value at the beginning
of the list.  A membership test requires traversal but since the list is
sorted we know when to stop if it doesn't exist.  Set union and
difference are pretty tricky but at least can stop early if one of two
sets is finite.  As I learn more Haskell I'll try implementing these
step by step.  Is there any interest in making this an actual module or
is it not very useful in the context of Haskell?

Thanks
Ted