On Thu, 19 Nov 2009 04:54:13 +0100 Daniel Fischer <daniel.is.fisc...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe