n^h 1      !"#$%&'()*+,-./0 Safe-Inferred?EOptimized and CPS'd version of 5, where all lefts are known to come before all rights11 Trustworthy!"+13;>?EHJKMT2; equipped with a compatible stable unordered discriminator. For every surjection f, 3 f   "a   )Productive Stable Unordered DiscriminatorValid definition for (4) in terms of .O(n) . Similar to 2, except we do not require groups to be clustered.QThis combinator still operates in linear time, at the expense of storing history.LThe result equivalence classes are _not_ sorted, but the grouping is stable.  =  5 O(n). This is a replacement for   using discrimination.LThe result equivalence classes are _not_ sorted, but the grouping is stable.O(n). This upgrades   from  Data.List from O(n^2) to O(n)/ by using productive unordered discrimination.  =  5  as = 6    as O(n) . Online  with a Schwartzian transform.  f as = 6    f as / 789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVW    +  789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVW Trustworthy +13;>EHJKMTX: equipped with a compatible stable, ordered discriminator.0For every strictly monotone-increasing function f: 3 f  "a  Stable Ordered DiscriminatorValid definition for Y in terms of .~Construct a stable ordered discriminator that sorts a list as multisets of elements from another stable ordered discriminator.The resulting discriminator only cares about the set of keys and their multiplicity, and is sorted as if we'd sorted each key in turn before comparing.yConstruct a stable ordered discriminator that sorts a list as sets of elements from another stable ordered discriminator.The resulting discriminator only cares about the set of keys, and is sorted as if we'd sorted each key in turn before comparing.  O(n)#. Sort a list using discrimination.   = ! 5 !O(n)I. Sort a list with a Schwartzian transformation by using discrimination. !This linear time replacement for   and  uses discrimination."O(n). Construct a Z.,This is an asymptotically faster version of (, which exploits ordered discrimination.toMap [] == emptyTrue)toMap [(5,"a"), (3 :: Int,"b"), (5, "c")]fromList [(5,"c"), (3,"b")])toMap [(5,"c"), (3,"b"), (5 :: Int, "a")]fromList [(5,"a"), (3,"b")]#O(n). Construct a Z, combining values.,This is an asymptotically faster version of (, which exploits ordered discrimination.B(Note: values combine in anti-stable order for compatibility with )CtoMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")] fromList [(3, "ab"), (5, "cba")]toMapWith (++) [] == emptyTrue$O(n). Construct a Z*, combining values with access to the key.,This is an asymptotically faster version of (, which exploits ordered discrimination.F(Note: the values combine in anti-stable order for compatibility with )Plet f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_valueCtoMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5 :: Int,"c")])fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]toMapWithKey f [] == emptyTrue%O(n). Construct an [.toIntMap [] == emptyTrue%toIntMap [(5,"a"), (3,"b"), (5, "c")]fromList [(5,"c"), (3,"b")]%toIntMap [(5,"c"), (3,"b"), (5, "a")]fromList [(5,"a"), (3,"b")]&O(n). Construct an [, combining values.,This is an asymptotically faster version of (, which exploits ordered discrimination.B(Note: values combine in anti-stable order for compatibility with )?toIntMapWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")] fromList [(3, "ab"), (5, "cba")]toIntMapWith (++) [] == emptyTrue'O(n). Construct a Z*, combining values with access to the key.,This is an asymptotically faster version of (, which exploits ordered discrimination.F(Note: the values combine in anti-stable order for compatibility with )Plet f key new_value old_value = show key ++ ":" ++ new_value ++ "|" ++ old_value?toIntMapWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"c")])fromList [(3, "3:a|b"), (5, "5:c|5:b|a")]toIntMapWithKey f [] == emptyTrue(O(n). Construct a \ in linear time.,This is an asymptotically faster version of (, which exploits ordered discrimination.)O(n). Construct an ] in linear time.,This is an asymptotically faster version of (, which exploits ordered discrimination.2^ !"#$%&'()_`abcdefghijklmnopqrstuvwxy !"#$%&'() !"#$%&'().^ !"#$%&'()_`abcdefghijklmnopqrstuvwxy Safe-Inferred,O(n)^. Perform a full outer join while explicit merging of the two result tables a table at a time.-The results are grouped by the discriminator.-O(n)C. Perform an inner join, with operations defined one row at a time.-The results are grouped by the discriminator.CThis takes operation time linear in both the input and result sets..O(n)F. Perform a full outer join with operations defined one row at a time.-The results are grouped by the discriminator.CThis takes operation time linear in both the input and result sets./O(n)F. Perform a left outer join with operations defined one row at a time.-The results are grouped by the discriminator.CThis takes operation time linear in both the input and result sets.0O(n)G. Perform a right outer join with operations defined one row at a time.-The results are grouped by the discriminator.CThis takes operation time linear in both the input and result sets. *+,the discriminator to usehow to join two tablesselector for the left tableselector for the right table left table right table-the discriminator to usehow to join two rowsselector for the left tableselector for the right table left table right table.the discriminator to usehow to join two rows-row present on the left, missing on the right-row present on the right, missing on the leftselector for the left tableselector for the right table left table right table/the discriminator to usehow to join two rows-row present on the left, missing on the rightselector for the left tableselector for the right table left table right table0the discriminator to usehow to join two rows-row present on the right, missing on the leftselector for the left tableselector for the right table left table right tablez{*+,-./0*+,-./0*+,-./0z{ Safe-Inferred)  !"#$%&'()*+,-./0)*+   !"#$%&'(),-./0| !""#$%&  '()*+,,-./0123456789:;<=>?@ABCDEFGHIDEJKLMKNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopDEqDErstusvwsxysz{|}~discrimination-0.1Data.Discrimination.InternalData.Discrimination.GroupingData.Discrimination.SortingData.Discrimination.Class Data.EitherpartitionEithers Data.ListgroupGHC.Exts groupWithnubControl.Applicative<$>sortWithsortOnData.MapfromList fromListWithfromListWithKeyData.IntMap.LazyData.Set Data.IntSetData.DiscriminationbdiscNatrunsgroupNum updateBag updateSet spanEither Grouping1 grouping1GroupinggroupingGroupgetGroup groupingNat groupingEqrunGroupnubWithSorting1sorting1SortingsortingSortrunSortsortingCompare sortingNat sortingBag sortingSetdescsorttoMap toMapWith toMapWithKeytoIntMap toIntMapWithtoIntMapWithKeytoSettoIntSetDiscriminatingdiscjoininginnerouter leftOuter rightOuter fromRightghc-prim GHC.ClassesEqcontravariant-1.3.1.1Data.Functor.Contravariant contramap==baseGHC.BaseidGHC.Listhead$fGrouping1Complex$fGrouping1Compose$fGrouping1(,,,)$fGrouping1(,,)$fGrouping1(,)$fGrouping1Either$fGrouping1Maybe $fGrouping1[]$fGroupingCompose$fGroupingRatio$fGroupingComplex$fGroupingEither$fGroupingMaybe $fGrouping[]$fGrouping(,,,)$fGrouping(,,) $fGrouping(,)$fGroupingBool $fGroupingInt$fGroupingInt64$fGroupingInt32$fGroupingInt16$fGroupingInt8$fGroupingWord$fGroupingWord64$fGroupingWord32$fGroupingWord16$fGroupingWord8$fGroupingVoid $fMonoidGroup$fDecidableGroup$fDivisibleGroup$fContravariantGroupOrdcomparecontainers-0.5.5.1 Data.Map.BaseMapData.IntMap.BaseIntMap Data.Set.BaseSetData.IntSet.BaseIntSet sortingColl$fSorting1Either$fSorting1Maybe $fSorting1[]$fSorting1Compose$fSortingCompose$fSorting(,,,) $fSorting(,,) $fSorting(,)$fSortingEither$fSortingMaybe $fSorting[] $fSortingBool $fSortingVoid $fSortingInt$fSortingInt64$fSortingInt32$fSortingInt16 $fSortingInt8 $fSortingWord$fSortingWord64$fSortingWord32$fSortingWord16$fSortingWord8 $fMonoidSort$fDecidableSort$fDivisibleSort$fContravariantSort$fDiscriminatingGroup$fDiscriminatingSort