Add lookupMin and lookupMax for IntSet

[meooow25]

I wanted to use IntSet.lookupMin today and realized it's not defined. lookupMin and lookupMax already exist for Set, Map, and IntMap.

Edit: Also

• Update docs for lookupMin, lookupMax, findMin, findMax to be consistent for all the structures.
• Modify IntMap's lookupMin and lookupMax impls so that Just is returned immediately and mark them INLINE. This allows GHC to inline and possibly eliminate the Maybe. Set and Map's lookupMin and lookupMax are already implemented in this style.

[meooow25]

Hello, could you please review this PR?

[meooow25]

Updated Map's lookupMin and lookupMax as discussed. Sharing the core below.

Core

Rec {
-- RHS size: {terms: 19, types: 26, coercions: 0, joins: 0/0}
Data.Map.Internal.$wlookupMinSure [InlPrag=[2], Occ=LoopBreaker]
  :: forall {k} {a}. k -> a -> Map k a -> (# k, a #)
[GblId[StrictWorker([~, ~, !])],
 Arity=3,
 Str=<ML><L><1L>,
 Unf=OtherCon []]
Data.Map.Internal.$wlookupMinSure
  = \ (@k_sIhw)
      (@a_sIhx)
      (k1_sIhy :: k_sIhw)
      (a1_sIhz :: a_sIhx)
      (ds_sIhA :: Map k_sIhw a_sIhx) ->
      case ds_sIhA of {
        Bin bx_dH9Z k2_asZd a2_asZe l_asZf ds1_dzm5 ->
          Data.Map.Internal.$wlookupMinSure
            @k_sIhw @a_sIhx k2_asZd a2_asZe l_asZf;
        Tip ->
          case k1_sIhy of conrep_atnO { __DEFAULT ->
          (# conrep_atnO, a1_sIhz #)
          }
      }
end Rec }

-- RHS size: {terms: 14, types: 18, coercions: 0, joins: 0/0}
lookupMinSure [InlPrag=[2]]
  :: forall k a. k -> a -> Map k a -> KeyValue k a
[GblId,
 Arity=3,
 Str=<ML><L><1L>,
 Cpr=1,
 Unf=Unf{Src=StableSystem, TopLvl=True,
         Value=True, ConLike=True, WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(arity=3,unsat_ok=True,boring_ok=False)
         Tmpl= \ (@k_sIhw)
                 (@a_sIhx)
                 (k1_sIhy [Occ=Once1] :: k_sIhw)
                 (a1_sIhz [Occ=Once1] :: a_sIhx)
                 (ds_sIhA [Occ=Once1] :: Map k_sIhw a_sIhx) ->
                 case Data.Map.Internal.$wlookupMinSure
                        @k_sIhw @a_sIhx k1_sIhy a1_sIhz ds_sIhA
                 of
                 { (# ww_sINB [Occ=Once1], ww1_sINC [Occ=Once1] #) ->
                 Data.Map.Internal.KeyValue @k_sIhw @a_sIhx ww_sINB ww1_sINC
                 }}]
lookupMinSure
  = \ (@k_sIhw)
      (@a_sIhx)
      (k1_sIhy :: k_sIhw)
      (a1_sIhz :: a_sIhx)
      (ds_sIhA :: Map k_sIhw a_sIhx) ->
      case Data.Map.Internal.$wlookupMinSure
             @k_sIhw @a_sIhx k1_sIhy a1_sIhz ds_sIhA
      of
      { (# ww_sINB, ww1_sINC #) ->
      Data.Map.Internal.KeyValue @k_sIhw @a_sIhx ww_sINB ww1_sINC
      }

-- RHS size: {terms: 18, types: 34, coercions: 0, joins: 0/0}
lookupMin [InlPrag=INLINE (sat-args=1)]
  :: forall k a. Map k a -> Maybe (k, a)
[GblId,
 Arity=1,
 Str=<1L>,
 Unf=Unf{Src=StableUser, TopLvl=True,
         Value=True, ConLike=True, WorkFree=True, Expandable=True,
         Guidance=ALWAYS_IF(arity=1,unsat_ok=False,boring_ok=False)
         Tmpl= \ (@k_avaJ)
                 (@a_avaK)
                 (ds_dzmb [Occ=Once1!] :: Map k_avaJ a_avaK) ->
                 case ds_dzmb of {
                   Bin _ [Occ=Dead] k1_asZg [Occ=Once1] x_asZh [Occ=Once1]
                       l_asZi [Occ=Once1] _ [Occ=Dead] ->
                     case lookupMinSure @k_avaJ @a_avaK k1_asZg x_asZh l_asZi of
                     { KeyValue k2_asZ9 [Occ=Once1] a1_asZa [Occ=Once1] ->
                     GHC.Maybe.Just @(k_avaJ, a_avaK) (k2_asZ9, a1_asZa)
                     };
                   Tip -> GHC.Maybe.Nothing @(k_avaJ, a_avaK)
                 }}]
lookupMin
  = \ (@k_avaJ) (@a_avaK) (ds_dzmb :: Map k_avaJ a_avaK) ->
      case ds_dzmb of {
        Bin bx_dHa0 k1_asZg x_asZh l_asZi ds1_dzoB ->
          case Data.Map.Internal.$wlookupMinSure
                 @k_avaJ @a_avaK k1_asZg x_asZh l_asZi
          of
          { (# ww_sINB, ww1_sINC #) ->
          GHC.Maybe.Just @(k_avaJ, a_avaK) (ww_sINB, ww1_sINC)
          };
        Tip -> GHC.Maybe.Nothing @(k_avaJ, a_avaK)
      }

[meooow25]

Updated again to put a bang on k, as recommended in GHC#24340.
Though it looks like k is evaluated every time in core (case k1_somV of k2_X0 { __DEFAULT ->... in https://github.com/haskell/containers/pull/976#discussion_r1451918255), the core does not tell the full story. This is out of my depth but, as explained in the GHC issue above, code generation down the line gets rid of this eval.

[meooow25]

@treeowl does this look good?

[treeowl]

I'd like to take one more look at it after I finish waking up and mixing dough.

[meooow25]

@treeowl?

[meooow25]

@treeowl, reminder to review.

[meooow25]

Rebased.

[meooow25]

@treeowl I am inclined to merge this soon if that's alright.
Your suggestion of using a half-strict pair for Map is implemented, and we are strict in the key in the functions as recommended in the GHC issue.

[meooow25]

Thanks for reviewing!