IntSet's minView and maxView creates unwanted thunks
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
https://github.com/haskell/containers/blob/0c3b9ee93af23f86fb8ad5ffe7729cb82fc4cd3a/containers/src/Data/IntSet/Internal.hs#L1164-L1172
Core:
```
Rec {
-- RHS size: {terms: 47, types: 28, coercions: 0, joins: 0/1}
$wgo1 [InlPrag=[2], Occ=LoopBreaker] :: IntSet -> (# Int, IntSet #)
[GblId[StrictWorker([!])], Arity=1, Str=<1L>, Unf=OtherCon []]
$wgo1
= \ (ds_sdOH :: IntSet) ->
case ds_sdOH of {
Bin bx_dcyn l_a73T r_a73U ->
case $wgo1 r_a73U of { (# ww_se6X, ww1_se6Y #) ->
(# ww_se6X,
case ww1_se6Y of wild2_X4 {
__DEFAULT -> Bin bx_dcyn l_a73T wild2_X4;
Nil -> l_a73T
} #)
};
Tip bx_dcyp bx1_dcyq ->
let {
bi_sd64 :: Int#
[LclId]
bi_sd64 = -# 63# (word2Int# (clz# bx1_dcyq)) } in
(# I# (+# bx_dcyp bi_sd64),
case and# bx1_dcyq (not# (uncheckedShiftL# 1## bi_sd64))
of ds1_X3 {
__DEFAULT -> Tip bx_dcyp ds1_X3;
0## -> Nil
} #);
Nil -> case lvl42_reKj of {}
}
```
Just using a strict pair instead of lazy should fix it. IntMap's definition seems pretty good and how I would define it for IntSet too, splitting the empty map case out and inlining it to potentially get rid of the Maybe.
https://github.com/haskell/containers/blob/0c3b9ee93af23f86fb8ad5ffe7729cb82fc4cd3a/containers/src/Data/IntMap/Internal.hs#L2325-L2345
Contributor guide
Research direction
Start with minView and maxView in containers/src/Data/IntSet/Internal.hs at the linked lines, then compare their definitions with the corresponding IntMap code in containers/src/Data/IntMap/Internal.hs. Generate Core for the affected functions and verify that using the stricter result representation removes the unwanted thunks while preserving the existing IntSet behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- data
- Issue type
- Refactor
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 58/100