Add Int index functions to Data.Set

[sacundim]

Data.Map has some functions that allow a Map's entries to be accessed through Int indexes:

lookupIndex :: Ord k => k -> Map k a -> Maybe Int
findIndex :: Ord k => k -> Map k a -> Int
elemAt :: Int -> Map k a -> (k, a)
updateAt :: (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
deleteAt :: Int -> Map k a -> Map k a

With the exception of updateAt, these functions are trivially adaptable to Data.Set.

I attach a patch to this ticket that does that. My Data.Set implementations of the functions are modeled on the ones from Data.Map. Functions implemented:

lookupIndex :: Ord a => a -> Set a -> Maybe Int
findIndex :: Ord a => a -> Set a -> Int
elemAt :: Int -> Set a -> a
deleteAt :: Int -> Set a -> Set a

[sacundim]

Patch that implements and documents the additional functions

[igloo]

Thanks for the patch. However, please see  http://www.haskell.org/haskellwiki/Library_submissions for the process for proposing changes to the APIs for the core libraries.

[sacundim]

Yeah, I didn't see that page until right after I filed the ticket. Will do that.

[malcolm.wallace@…]

Note that, conceptually anyway, a Set's elements are unordered. If you expose a specific ordering, then you are breaking the abstraction.

(It is unfortunate that Data.Set does use an ordering for efficient representation, and that this ordering appears in the type signatures. Ideally, even if the ordering were used internally, it would not be visible to the outside world.)

[tibbe]

Some comment regarding the actual patch:

+lookupIndex :: Ord a => a -> Set a -> Maybe Int
+lookupIndex k = k `seq` go 0
+  where
+    go idx Tip  = idx `seq` Nothing
+    go idx (Bin _ kx l r)
+      = idx `seq` case compare k kx of
+          LT -> go idx l
+          GT -> go (idx + size l + 1) r 
+          EQ -> Just (idx + size l)

The last line is too lazy, it will create a thunk containing (idx + size l).

+elemAt :: Int -> Set a -> a
+elemAt _ Tip = error "Set.elemAt: index out of range"
+elemAt i (Bin _ kx l r)
+  = case compare i sizeL of
+      LT -> elemAt i l
+      GT -> elemAt (i-sizeL-1) r
+      EQ -> kx
+  where
+    sizeL = size l

This function would be more efficient if it was strict in i, which it isn't due to the first equation.

+deleteAt :: Int -> Set a -> Set a
+deleteAt i0 t = i0 `seq` go i0 t
+ where
+    go _ Tip = error "Set.deleteAt: index out of range"
+    go i (Bin sx kx l r) = case compare i sizeL of
+      LT -> balance kx (go i l) r
+      GT -> balance kx l (go (i-sizeL-1) r)
+      EQ -> glue l r
+      where 
+        sizeL = size l

Same here, could be stricter in i.

[sacundim]

tibbe, thanks for your feedback.

To tell you the truth, all I did was get the source for Data.Map in containers-0.4.0, copypaste the existing Data.Map functions to Data.Set, and edit them to work—which mostly just involved editing type signatures and removing the "value" element from the pattern matches and constructors. So as far as I can tell, your objections also apply to the 0.4.0 version of Data.Map.

I've just installed darcs and gotten the containers repository, and this has a different version of these Data.Map functions, presumably newer and better. I'm in the process of recreating the patch based on that, and that's what I will submit to the libraries list.

I will add that I have a very limited goal here: duplicate the Data.Map implementations for Data.Set, and make the Set versions no worse than the original Map versions. So to be frank, for my purposes, any suggested improvements that also apply to Data.Map are beyond my scope (and, sadly, most likely also beyond my Haskell skills at this point).