[GHC] #5162: Add Int index functions to Data.Set

[GHC]

#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