Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make Relude.List.permutations return a NonEmpty. #385

Open
kindaro opened this issue Sep 11, 2021 · 5 comments · May be fixed by #397
Open

Make Relude.List.permutations return a NonEmpty. #385

kindaro opened this issue Sep 11, 2021 · 5 comments · May be fixed by #397
Labels
new Bring something new into library (add function or type or interface) question Further information is requested

Comments

@kindaro
Copy link

kindaro commented Sep 11, 2021

You may observe that any list has at least one permutation. The empty list's only permutation is the empty list itself, so:

λ Relude.List.permutations [ ]
[[]]

This behaviour is also theoretically sound since permutations of a list are a model of a symmetric group and a group always has at least one element.

It is nicer to have to drop from a NonEmpty to a list than to lift from a list to NonEmpty, since the latter requires the handling of the spurious case of the list being empty.

@chshersh chshersh added new Bring something new into library (add function or type or interface) question Further information is requested labels Nov 5, 2021
@chshersh
Copy link
Contributor

chshersh commented Nov 5, 2021

Do people actually use the standard permutations function for lists?

@kindaro
Copy link
Author

kindaro commented Nov 19, 2021

I do. Why not? Maybe I am not aware of alternatives.

@chshersh
Copy link
Contributor

Okay, I see that this function is used quite often in different packages. In that case, making its return type consistent with actual behaviour.

I'm surprised the Data.List.NonEmpty doesn't have this function implemented for NonEmpty. Seeing the implementation for lists, it should be pretty easy to implement it for base.

I encourage you (or anyone else) to open a proposal to base to implement it there, so we can just reexport it later:

But for now, we can implement a safer version in relude.

@chshersh
Copy link
Contributor

I was thinking about this issue for a while and I think that the best way to resolve this problem is to provide a separate function that works for NonEmpty lists exclusively with the following type:

permutations :: NonEmpty a -> NonEmpty (NonEmpty a)

Implementation of this function is probably slightly more complicated that the existing permutations. But it's really easy to implement "ordinary" permutations by using this new permutations.

However, I'd love to have this function implemented in base first and eventually just reexport it from there. So anyone motivated enough to bring this interface to relude should open a corresponding proposal to CLC:

One of the relude goals is Type-safety. However, I don't consider the existing type of permutations as critically wrong. Hence, I'd like to stick with the Minimalism goal of relude and implement less custom stuff.

Once the CLC proposal is accepted and the new type-safe permutatiions is implemented, I propose the following migration plan:

  1. Implement permutations and permutationsList functions as aliases to Data.List.permutations.
  2. Deprecate permutations with the message to suggest using permutationsList instead.
  3. Once permtuations for NonEmpty is implemented in base, remove permutations for lists from relude and reexport it from Data.List.NonEmpty instead.

@kindaro
Copy link
Author

kindaro commented May 25, 2022

I do not see why this function should not accept an empty list as an input. As I see it, we should require as few assumptions as we can. We do not need the assumption that the input is non-empty, so we should not require it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
new Bring something new into library (add function or type or interface) question Further information is requested
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants