Re: [Haskell-cafe] Re: inversion lists

Am Dienstag 01 Dezember 2009 23:31:10 schrieb Ted Zlatanov:

On Fri, 20 Nov 2009 15:30:49 -0600 Ted Zlatanov 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.