Make `Relude.List.permutations` return a `NonEmpty`.

[kindaro]

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]

Do people actually use the standard permutations function for lists?

[kindaro]

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

[chshersh]

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:

• https://github.com/haskell/core-libraries-committee

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

[chshersh]

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:

• https://github.com/haskell/core-libraries-committee

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]

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.