#5162: Add Int index functions to Data.Set
--------------------------------+-------------------------------------------
Reporter: sacundim | Owner: sacundim
Type: feature request | Status: closed
Priority: normal | Milestone:
Component: libraries (other) | Version: 7.0.3
Resolution: wontfix | Keywords: Data.Set
Testcase: | Blockedby:
Difficulty: | Os: Unknown/Multiple
Blocking: | Architecture: Unknown/Multiple
Failure: None/Unknown |
--------------------------------+-------------------------------------------
Comment(by 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`.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/5162#comment:5>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
Glasgow-haskell-bugs@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
