Where do trivial functions on the usual containers live?

[Ignat Insarov]

Hello.

I am looking for a place where I can find or put some simple functions that I
expect but do not find in the `containers` or elsewhere in the standard
libraries. Some examples I have in mind:

* Group a collection by an equivalence relation:

      classify ∷ Ord π ⇒ (a → π) → [a] → [[a]]

* From a finite map, get a map from its range to its fibers:

      fibers ∷ (Ord k, Ord v) ⇒ Map k v → Map v (NonEmpty k)

* Put a type into the diagonal of its square:

      diagonal = λx → (x, x)

These are all very common and trivial mathematical constructions and I really
want such things to be common place in Haskell, so that they may have a
canonical, polished definition. It is unfeasible to put them into the standard
libraries. _(Attempts were made.)_ So I wonder if there is a package around that
would accept them!
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

[Henning Thielemann]

On Sun, 20 Dec 2020, Ignat Insarov wrote:

> I am looking for a place where I can find or put some simple functions that I
> expect but do not find in the `containers` or elsewhere in the standard
> libraries.

I have my own utility library for such functions. However, it does not and
shall not depend on 'containers'.

> Some examples I have in mind:
>
> * Group a collection by an equivalence relation:
>
>      classify ∷ Ord π ⇒ (a → π) → [a] →a]]

If the grouped elements must be consecutive then I have
Data.List.Key.group. But I guess, that Ord means that you want to group
all elements with the same key in one group. Then I would use Map anyway
for representing the result.

> * From a finite map, get a map from its range to its fibers:
>
>      fibers ∷ (Ord k, Ord v) ⇒ Map k v → Map v (NonEmpty k)
>
> * Put a type into the diagonal of its square:
>
>      diagonal = λx → (x, x)

I have Data.Tuple.HT.double. But recently the name 'dup' was discussed
here.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

[MarLinn]

I am looking for a place where I can find or put some simple functions that I
expect but do not find in the `containers` or elsewhere in the standard
libraries.

For now, I can't see a good place for any of your suggestions. But maybe even discussing potential why-not's may further the discussion.

* Group a collection by an equivalence relation:

      classify ∷ Ord π ⇒ (a → π) → [a] → [[a]]

If the provided function is indeed an "equivalence relation", shouldn't the type be Eq π ⇒ (a → π) → [a] → [[a]], which is basically Data.List.groupBy? On the other hand if the resulting list is supposed to be ordered, most practical applications will probably use a set or a map anyway.

So the difference between this function and existing functionality is so small, that the cost of maintenance and remembering the name might not be worth it.

* From a finite map, get a map from its range to its fibers:

      fibers ∷ (Ord k, Ord v) ⇒ Map k v → Map v (NonEmpty k)

Why NonEmpty, and not Set? Or any Monoid? And more importantly, who are we to decide? Again, the cost difference between maintaining and re-discovering one "standard" vs. re-implementing something more precisely suited to the task at hand via (e.g.) Data.Map.foldMapWithKey doesn't seem worth it.

Additionally if I'm writing a program that would benefit from this function, performance considerations will almost always lead me to not use it. Instead, I will maintain both the map and its inverse from the start.

* Put a type into the diagonal of its square:

      diagonal = λx → (x, x)

Now this might fit into Data.Tuple. Then again, it's faster and more self-documenting to re-implement it at hoc than to remember a name.

Also, this (again) is less useful than it seems. It will almost always require an application of uncurry as well, which makes the program harder to understand. Sometimes it's better to replace both with a single application of the Monad instance of (->) – or with the "real" function.

For example:

uncurry (+) . diagonal ≡ join (+) ≡ \x -> x + x ≡ (2*)

Using diagonal is probably one of the worst ways to implement this and many of its brethren.

It is unfeasible to put them into the standard libraries. _(Attempts were made.)_

This sounds like the maintainers of the standard libraries had their own objections. I suspect some of them might be similar to the ones above. Which leads me to suspect you might not have taken their feedback to heart. Which might in fact be the biggest hurdle on getting your code accepted into a library.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

[Ignat Insarov]

I immediately surrender any claims to having given perfect types to the
functions I would like to have. All I want is to have things that work somewhere
at hand, and not at all to have perfect things nowhere.

Nevertheless, I am going to reply to your objections.

> > * Group a collection by an equivalence relation:
> >
> > classify ∷ Ord π ⇒ (a → π) → [a] → [[a]]
>
> If the provided function is indeed an "equivalence relation", shouldn't the
> type be Eq π ⇒ (a → π) → [a] → [[a]], which is basically Data.List.groupBy? On
> the other hand if the resulting list is supposed to be ordered, most practical
> applications will probably use a set or a map anyway.

`Data.List.groupBy` detects only adjacent equivalent elements. The intention
here is to detect distant equivalent elements as well. You may see a more
detailed explanation and examples here:
<https://stackoverflow.com/questions/8262179>. See also previous discussion
here: <https://mail.haskell.org/pipermail/libraries/2020-August/030736.html>.

You may also see from these sources that it is not trivial to define this
function without the `Ord` constraint. In more detail: there are two versions,
one of which requires only `Eq` and runs in _n × m_ time, and the other requires
`Ord` and runs in _n × log n_ time. Neither is clearly better.

The most precise and informative type for the result seems to be `[NonEmpty
α]`. I do not see how `Set` or `Map` would be more suitable.

> > * From a finite map, get a map from its range to its fibers:
> >
> > fibers ∷ (Ord k, Ord v) ⇒ Map k v → Map v (NonEmpty k)
>
> Why NonEmpty, and not Set? Or any Monoid? And more importantly, who are we to
> decide? Again, the cost difference between maintaining and re-discovering one
> "standard" vs. re-implementing something more precisely suited to the task at
> hand via (e.g.) Data.Map.foldMapWithKey doesn't seem worth it.

Because a fiber is non-empty. Ideally, sure, I would like `(k, Set k)`.

The remainder of the quote would be very hard to substantiate. I evaluate the
cost and the benefit differently, that is all.

> > * Put a type into the diagonal of its square:
> >
> > diagonal = λx → (x, x)
>
> Now this might fit into Data.Tuple. Then again, it's faster and more
> self-documenting to re-implement it at hoc than to remember a name.
>
> Also, this (again) is less useful than it seems. It will almost always require
> an application of uncurry as well, which makes the program harder to
> understand. Sometimes it's better to replace both with a single application of
> the Monad instance of (->) – or with the "real" function.
>
> For example:
>
> uncurry (+) . diagonal ≡ join (+) ≡ \x -> x + x ≡ (2*)

I added this for a joke. It has been discussed previously at hilarious
length. See:

<https://mail.haskell.org/pipermail/libraries/2018-October/029051.html>
<https://mail.haskell.org/pipermail/libraries/2019-July/029744.html>
<https://mail.haskell.org/pipermail/libraries/2020-September/030789.html>

Surprizingly, many high profile Haskell programmers agree that it is useful.

> > It is unfeasible to put them into the standard libraries. _(Attempts were
> > made.)_
>
> This sounds like the maintainers of the standard libraries had their own
> objections. I suspect some of them might be similar to the ones above. Which
> leads me to suspect you might not have taken their feedback to heart. Which
> might in fact be the biggest hurdle on getting your code accepted into a
> library.

Turns out your objections mostly come down to evaluation of usefulness, which
would be very hard to substantiate by evidence, especially since usefulness is
potential as much as it is actual.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

[Ignat Insarov]

> I have my own utility library for such functions. However, it does not and
> shall not depend on 'containers'.

Why not, if I may ask?
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

[Henning Thielemann]

On Sun, 20 Dec 2020, Ignat Insarov wrote:

>> > * From a finite map, get a map from its range to its fibers:
>> >
>> > fibers ∷ (Ord k, Ord v) ⇒ Map k v → Map v (NonEmpty k)
>>
>> Why NonEmpty, and not Set? Or any Monoid? And more importantly, who are we to
>> decide? Again, the cost difference between maintaining and re-discovering one
>> "standard" vs. re-implementing something more precisely suited to the task at
>> hand via (e.g.) Data.Map.foldMapWithKey doesn't seem worth it.
>
> Because a fiber is non-empty. Ideally, sure, I would like `(k, Set k)`.

NonEmptyMap (and NonEmptySet?) were already discussed here.

I also have:
    https://hackage.haskell.org/package/non-empty-0.3.2/docs/Data-NonEmpty-Set.html
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

[Henning Thielemann]

On Sun, 20 Dec 2020, Ignat Insarov wrote:

>> I have my own utility library for such functions. However, it does not and
>> shall not depend on 'containers'.
>
> Why not, if I may ask?

Because I wanted to depend only on 'base' and be very stable. However,
there is certainly room for a containers-utility library.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.