On Fri, 20 Nov 2009 15:30:49 -0600 Ted Zlatanov <t...@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? 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. Can I do it with a direct foldl instead? 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 = foldr invlist' [] 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe