Just an idea: "Asc" and "Desc" are relatively common abbreviations for increasing and decreasing. Not sure how I feel about them though. On Sun, Aug 7, 2016 at 1:04 AM, David Feuer wrote:

Sorry about that. filterIncreasing and filterDecreasing filter assuming a predicate that is increasing or decreasing on the key values. So instead of an O(n) pass over the whole set/map, they simply perform an O(log n) split.

On Aug 6, 2016 11:31 PM, "Ivan Lazar Miljenovic" < ivan.miljenovic@gmail.com> wrote:

...

On 7 August 2016 at 13:15, David Feuer wrote:

...

Cale Gibbard and Ryan Trinkle are interested in adding some more operations they say will be useful in their work. Note that unionWithMapping is intended to enable an efficient implementation of alignWith in Data.Align in the `these` package.

Set:

filterIncreasing :: Ord a => (a -> Bool) -> Set a -> Set a filterDecreasing :: Ord a => (a -> Bool) -> Set a -> Set a partitionIncreasing :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)

I'm not sure what the difference between the first two functions are, or even how they differ from a generic filter function.

...

Map:

filterKeysIncreasing :: Ord k => (k -> Bool) -> Map k a -> Map k a filterKeysDecreasing :: Ord k => (k -> Bool) -> Map k a -> Map k a partitionKeysIncreasing :: Ord k => (k -> Bool) -> Map k a -> (Map k a,

Map k a)

...

traverseMaybe :: Applicative f => (a -> f (Maybe b)) -> Map k a -> f

(Map k b)

...

alterMany :: Ord k => (a -> Maybe b -> Maybe b) -> Map k a -> Map k b

-> Map k b

...

alterManyA :: (Applicative f, Ord k) => (a -> Maybe b -> f (Maybe b)) -> Map k a -> Map k b -> f (Map k b)

unionWithMapping :: Ord k => (a -> c) -> (b -> c) -> (a -> b -> c) -> Map k a -> Map k b -> Map k c

unionWithKeyMapping :: Ord k => (k -> a -> c) -> (k -> b -> c) -> (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

When the predicate is monotone then all of those operations have the same semantics as filter. -Edward On Sun, Aug 7, 2016 at 1:34 AM, Ivan Lazar Miljenovic < ivan.miljenovic@gmail.com> wrote:

On 7 August 2016 at 15:04, David Feuer wrote:

...

Sorry about that. filterIncreasing and filterDecreasing filter assuming a predicate that is increasing or decreasing on the key values. So instead of an O(n) pass over the whole set/map, they simply perform an O(log n) split.

So it's more like a takeWhile, (dropWhile . not) and span than filter and predicate for lists?

...

On Aug 6, 2016 11:31 PM, "Ivan Lazar Miljenovic" <

ivan.miljenovic@gmail.com>

...

wrote:

...

On 7 August 2016 at 13:15, David Feuer wrote:

...

Cale Gibbard and Ryan Trinkle are interested in adding some more operations they say will be useful in their work. Note that unionWithMapping is intended to enable an efficient implementation of alignWith in Data.Align in the `these` package.

Set:

filterIncreasing :: Ord a => (a -> Bool) -> Set a -> Set a filterDecreasing :: Ord a => (a -> Bool) -> Set a -> Set a partitionIncreasing :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)

I'm not sure what the difference between the first two functions are, or even how they differ from a generic filter function.

...

Map:

filterKeysIncreasing :: Ord k => (k -> Bool) -> Map k a -> Map k a filterKeysDecreasing :: Ord k => (k -> Bool) -> Map k a -> Map k a partitionKeysIncreasing :: Ord k => (k -> Bool) -> Map k a -> (Map k

a,

...

...

Map k a)

traverseMaybe :: Applicative f => (a -> f (Maybe b)) -> Map k a -> f (Map k b)

alterMany :: Ord k => (a -> Maybe b -> Maybe b) -> Map k a -> Map k b -> Map k b

alterManyA :: (Applicative f, Ord k) => (a -> Maybe b -> f (Maybe b)) -> Map k a -> Map k b -> f (Map k b)

unionWithMapping :: Ord k => (a -> c) -> (b -> c) -> (a -> b -> c) -> Map k a -> Map k b -> Map k c

unionWithKeyMapping :: Ord k => (k -> a -> c) -> (k -> b -> c) -> (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

-- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

So what names would you prefer? On Aug 7, 2016 3:34 PM, "Henning Thielemann" wrote:

On Sun, 7 Aug 2016, Edward Kmett wrote:

When the predicate is monotone then all of those operations have the same

...

semantics as filter.

Which is true for takeWhile, dropWhile and span. I find the 'filter' names also highly misleading. _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

No objection. On Aug 8, 2016 11:48 AM, "Henning Thielemann" wrote:

On Mon, 8 Aug 2016, David Feuer wrote:

So what names would you prefer?

...

Good question. I would prefer something with takeWhile and dropWhile, however that also only matches if the predicates are monotonic. We already have mapMonotonic. Maybe:

takeWhileMonotonic dropWhileMonotonic spanMonotonic

I had another idea for an operation that covers most of the likely use-cases for mergeWithKey, but without its danger and with a substantially more informative type signature. The only downside is that it's not even close to Haskell 98. data MergeTactic k x y where Drop :: MergeTactic k x y Preserve :: MergeTactic k x x MapFilter :: (k -> x -> Maybe y) -> MergeTactic k x y generalMerge :: Ord k => (k -> a -> b -> Maybe c) -> MergeTactic k a c -> MergeTactic k b c -> Map k a -> Map k b -> Map k c How do people feel about exporting this for GHC? On Sun, Aug 7, 2016 at 12:32 AM, Oleg Grenrus wrote:

-1 on unionWithMapping/Key. There is already mergeWithKey (and there’s pull request to `these` to use it, I’d just hadn’t time to look it thru properly and apply).

- Oleg Grenrus (co-maintainer of these)

...

On 07 Aug 2016, at 06:15, David Feuer wrote:

Cale Gibbard and Ryan Trinkle are interested in adding some more operations they say will be useful in their work. Note that unionWithMapping is intended to enable an efficient implementation of alignWith in Data.Align in the `these` package.

Set:

filterIncreasing :: Ord a => (a -> Bool) -> Set a -> Set a filterDecreasing :: Ord a => (a -> Bool) -> Set a -> Set a partitionIncreasing :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)

Map:

filterKeysIncreasing :: Ord k => (k -> Bool) -> Map k a -> Map k a filterKeysDecreasing :: Ord k => (k -> Bool) -> Map k a -> Map k a partitionKeysIncreasing :: Ord k => (k -> Bool) -> Map k a -> (Map k a, Map k a)

traverseMaybe :: Applicative f => (a -> f (Maybe b)) -> Map k a -> f (Map k b)

alterMany :: Ord k => (a -> Maybe b -> Maybe b) -> Map k a -> Map k b -> Map k b

alterManyA :: (Applicative f, Ord k) => (a -> Maybe b -> f (Maybe b)) -> Map k a -> Map k b -> f (Map k b)

unionWithMapping :: Ord k => (a -> c) -> (b -> c) -> (a -> b -> c) -> Map k a -> Map k b -> Map k c

unionWithKeyMapping :: Ord k => (k -> a -> c) -> (k -> b -> c) -> (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On Sun, Aug 7, 2016 at 3:31 PM, Henning Thielemann wrote:

If I import a package (containers) with functions that are only available on GHC then I need to insert conditionals for whether I am running on GHC or not.

This is true. Unfortunately, the safe, relatively pleasant, relatively comprehensible, and relatively general API this function offers simply can't be supported without GADTs. It would be possible to retain safety and generality in a potentially-more-portable fashion using rank 2 types, but the API is unlikely to be pleasant or easy to understand. The alternatives are to use mergeWithKey, which is unpleasant, difficult to understand, and unsafe, or to export four functions instead of one. I don't particularly care for either of those options. If you are more concerned about portability than safety or ease of understanding, you can always use mergeWithKey.

On Aug 7, 2016 3:22 PM, "Jan-Willem Maessen" wrote:

Are there good examples of increasing / decreasing predicates that don't embed a split element? Because split already gives the results you want.

An obvious one is isRight :: Either a b -> Bool. Another is fst :: (Bool, a) -> Bool

There's a pretty large combinatorial space of these functions – I'm not sure Data.Map and Data.Set should fill that entire space with individually-named functions.

The applicative versions suggest there might want to be an applicative-friendly version of mergeWithKey, but again it's not obvious we need the 32767 different combinations of individual functions.

Indeed, that is cause for concern. I wrote another email suggesting a combinator subsuming several of these using a GADT to deal with the type equalities some of them require.