[Haskell-cafe] Re: inversion lists

[Daniel Fischer]

Am Dienstag 01 Dezember 2009 23:31:10 schrieb Ted Zlatanov:
> On Fri, 20 Nov 2009 15:30:49 -0600 Ted Zlatanov <tzz at lifelogs.com> wrote:
>
> TZ> A nice property of inversion lists is that inverting them simply
> TZ> requires removing or adding the minimum possible value at the beginning
> TZ> of the list.  A membership test requires traversal but since the list
> is TZ> sorted we know when to stop if it doesn't exist.  Set union and TZ>
> difference are pretty tricky but at least can stop early if one of two TZ>
> sets is finite.  As I learn more Haskell I'll try implementing these TZ>
> step by step.  Is there any interest in making this an actual module or TZ>
> is it not very useful in the context of Haskell?
>
> OK, here's my current state.  The first two functions are not mine, of
> course (the original invlist' was called h, that's all).
>
> invlist_negate just appends 0 or removes it.  I think the first
> condition (on an empty list) is not necessary.  Should I keep it for
> clarity?

I don't think it's necessary.
As Sjoerd mentioned, the use of 0 is problematic.

>
> For invlist_member I basically pass the current state down into the
> recursion chain on invlist_member'.  The function will end early if it
> can, or it will scan all the way down the list in the worst case (when
> the goal value is greater than the last interval marker).  I think I
> could do it with a foldl but I wasn't able to figure it out.
>
> Any suggestions are welcome.  I can definitely reimplement the invlist
> function similarly to invlist_member, by passing an exclusion state
> boolean down, which will make the code longer.  I'm not sure if it will
> be bad for performance.  I think it will be better because I'll be able
> to do it lazily as opposed to the foldr below which needs a finite list.

No, quite the opposite. foldr is wonderful for lazy list processing.
I just need to make my function a wee bit lazier:

Prelude> let h x zs = x:case zs of { (y:ys) | x+1 == y -> ys; _ -> (x+1):zs; }
Prelude> let invlist xs = foldr h [] xs
Prelude> invlist [1,2,3,7,8,12,13,14,20]
[1,4,7,9,12,15,20,21]
Prelude> take 10 $ invlist [2,5 .. ]
[2,3,5,6,8,9,11,12,14,15]
Prelude> take 10 $ invlist [2,4 .. ]
[2,3,4,5,6,7,8,9,10,11]
Prelude> take 10 $ invlist [2 .. ]
[2^CInterrupted.
Prelude> take 10 $ invlist [2 :: Data.Int.Int16 .. ]
[2,-32768]
-- That's a problem here

Hadn't thought about infinite (or even long) lists when I wrote it.

> Can I do it with a direct foldl instead?

No, foldl cannot produce anything before the whole list has been traversed, so it can't 
deal with infinite lists at all.

> I need to look at it
> carefully but maybe someone has a suggestion.
>
> I plan to do set operations after I get the basics right :)
>
> This should really have been in comp.lang.haskell.beginner.  Sorry for
> the elementary stuff, I'm keeping the thread in c.l.h.cafe only to avoid
> double postings at this point.
>
> Thanks
> Ted
>
> invlist' :: Num a => a -> [a] -> [a]
> invlist' x (y:ys)
>
>          | x+1 == y = x:ys
>
> invlist' x zs = x:(x+1):zs

invlist' :: Integral a => a -> [a] -> [a]
invlist' x zs = x:ws
    where
      ws = case zs of
              (y:ys) | x+1 == y -> ys
              _ -> (x+1):zs

-- we could use Num here, but for an implementation of sets via inversion lists,
-- Integral is the appropriate setting. Perhaps even better use Integral and Bounded

invlist' :: (Integral a, Bounded a) => a -> [a] -> [a]
invlist' x _
    | x == maxBound = [x]
invlist' x zs = x:ws
    where
      ws = case zs of
              (y:ys) | x+1 == y -> ys
              _ -> (x+1):zs


Now:
Prelude> invlist [2 :: Data.Int.Int8 .. ]
[2]

:D
>
Don't forget a type signature here. Otherwise you'll get bitten by the monomorphism 
restriction.
invlist :: (Integral a, Bounded a) => [a] -> [a]
> invlist = foldr invlist' []
>

Problem. That is only sensible if we only consider sets of nonnegative numbers.
For Integral and Bounded,

invlist_negate (x:xs)
    | x == minBound = xs
invlist_negate xs = minBound:xs

> invlist_negate [] = [0]
> invlist_negate (0:xs) = xs
> invlist_negate xs = 0:xs
>
> invlist_member _ [] = False
>
> -- bootstrap membership test with a False exclusion state (an inversion
> list begins with the first included value) invlist_member goal (x:xs) =
> invlist_member' goal False (x:xs)
>
> invlist_member' goal exclude (x:xs) =
>     if goal < x then
>        exclude
>     else
>         invlist_member' goal (not exclude) xs -- flip the exclusion state
> of the list
>
> invlist_member' _ exclude _ = exclude       -- if we can't match one more
> element, return the current exclusion state

invlist_member :: (Integral a, Bounded a) => a -> [a] -> Bool
invlist_member goal = foldr (\n b -> if goal < n then False else not b) False

*maybe* I'll think about unions, intersections and other set operations as foldr's.