Add permutations for non-empty lists

[kindaro]

Currently we have:

permutations :: [a] -> [[a]]

However, you may observe that any list has at least one permutation. For example, the empty list's only permutation is the empty list itself, so:

λ Data.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 former is safe while the latter requires the unsafe handling of the spurious case of the list of permutations being empty. Therefore I propose to add a function that does the same as permutations but returns a NonEmpty of lists.

See also kowainik/relude#385.

[andreasabel]

Therefore I propose to add a function that does the same as permutations but returns a NonEmpty of lists.

I suggest to name it permutations1.

[JakobBruenker]

Doesn't the 1 suffix usually indicate that the input has to be non-empty, rather than the output?

E.g. Data.List.NonEmpty has group (rather than group1), which also has a possibly empty input but NonEmpty output - but it also has group1, which has a NonEmpty input as well.

[andreasabel]

@JakobBruenker wrote:

Doesn't the 1 suffix usually indicate that the input has to be non-empty, rather than the output?

Dunno. I see no pretext for this in Data.List.
What do you suggest?

[JakobBruenker]

If we go with the precedent set by Data.List.NonEmpty.group and Data.List.NonEmpty.repeat and such, it would just be Data.List.NonEmpty.permutations.

[emilypi]

I'm in favor of deprecating Data.List.permutations to be replaced with

Data.List.NonEmpty.permutations :: [a] -> NonEmpty [a]

I think we can get away with this because people really don't use permutations in production code, and the people who would be affected probably care more about refined APIs such as the one above as opposed to dealing with nonsensical edge cases.

[Bodigrim]

@kindaro could you please clarify what exactly is being proposed here?

[kindaro]

I propose to add a function that does the same as permutations but returns a NonEmpty of lists. I care not what its name would be, what module it would be exported from, whether the current permutations would be deprecated — these decisions I am not qualified to make anyway.

[Bodigrim]

@kindaro in this case I mark this idea as awaiting a proper proposal. Participants are encouraged to come up with one.

[kindaro]

proposal № 68

Add Data.List.NonEmpty.permutations :: [a] -> NonEmpty [a] to base.

motivation

There is a function Data.List.permutations :: [a] -> [[a]]. Its meaning is to return all permutations of a given list. There is always at least one permutation, so it always returns a non-empty list.

proposal

Add a function Data.List.NonEmpty.permutations :: [a] -> NonEmpty [a] to base with the same behaviour as Data.List.permutations but a finer type.

Furthermore, add a note to the documentation of Data.List.permutations pointing out the existence of this newly added function, so as to make it easier to discover.

implementation

permutations            :: [a] -> NonEmpty [a]
permutations xs0        =  xs0 :| perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

[recursion-ninja]

I would argue that the permutation of an empty list is a degenerate (trivial) case and can be checked with a pattern match. Incorporating the semantics for a monoidal identity within a function tends to be a mistake. Hence a function with a more useful type signature would be:

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

Expect the library user to pattern match on [] inputs, manually handling the degenerate empty list case, then call permutations as defined above within the non-empty case.

Three important considerations:

1. If a user has a NonEmpty structure to start with, they do not lose the NonEmpty type information after generating the permutations.

2. If a user has a [] they must discern if it is empty or non-empty. In the former case they define handling the identity element. In the latter case, they gain type safety by operation on a collection of NonEmpty permutations.

3. This provides semantic equality between "permutations of a list" and "permutations of elements." In the monoid identity case of [], the permutations of the list is [] :| [], there is only one way to arrange a list of zero elements. However, the permutations of the elements is [], as there are no elements to permute, and hence no permutations. It's best to leave the user distinguish between where they expect [] :| [] or [] when handling the monoid identity element.

[Bodigrim]

Cf. #67, CC @hdgarrood.

[hdgarrood]

I’m personally inclined to agree with @recursion-ninja in that I like the sound of a permutations :: NonEmpty a -> NonEmpty (NonEmpty a) more (although I am unconvinced by point 3, specifically the idea that there is a sensible distinction to be made between the concepts of “permutations of a list” and “permutations of the elements of a list”). However, I also can’t think of the last time I wanted to use this function so I don’t have a strong opinion here.

[JakobBruenker]

Sticking with the naming convention established by

Data.List.NonEmpty.group :: (Foldable f, Eq a) => f a -> [NonEmpty a]
Data.List.NonEmpty.group1 :: Eq a => NonEmpty a -> NonEmpty (NonEmpty a) 

I propose adding

Data.List.NonEmpty.permutations :: [a] -> NonEmpty [a]
Data.List.NonEmpty.permutations1 :: NonEmpty a -> NonEmpty (NonEmpty a)

[kindaro]

Cool, can I go on and do it?

[tomjaguarpaw]

As a point of information (not an argument either way) which I don't think has been mentioned, the "real" type is permutations :: List n a -> List (Factorial n) (List n a) and all other types are just approximations to that.

[JakobBruenker]

@kindaro I'm not sure if your question is directed at me but if so, sure

[JakobBruenker]

@tomjaguarpaw as long as the type has more than one possible implementation you can always add more information, e.g. in this case that the resulting lists must contain not just the same number but exactly the elements provided in the input list.

Though since NonEmpty exists in base whereas a length-indexed list type or list singletons do not, it seems like a good compromise.

[kindaro]

So, what is the next step in the process? I am lost.

[JakobBruenker]

@kindaro the next step would probably be to ask @Bodigrim to trigger a committee vote on a version of the proposal. I imagine (but don't know) that if you want the vote to include both permutations and permutations1, the proposal needs to list concrete implementations for both of them.

[Bodigrim]

@kindaro would you like to stick to your original proposal or add permutations1 as well? Please raise a draft GHC MR, so that there are no doubts about proposed impementation.

[kindaro]

@recursion-ninja @hdgarrood  You can help me by providing an implementation for permutations1. I may get to it one day, but right now I do not have any spare mind space. Once I have it, I shall open a merge request to GHC.

[recursion-ninja]

@kindaro

You can help me by providing an implementation for permutations1.

I can certainly do this.

[JakobBruenker]

I finished a version just before I saw your response, @recursion-ninja:

import qualified Data.List.NonEmpty as NE
import Data.List.NonEmpty (NonEmpty(..))
import Data.Foldable

permutations1            :: NonEmpty a -> NonEmpty (NonEmpty a)
permutations1 xs0        =  xs0 :| perms (toList xs0) []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (NE.cons y)) ys r
                                     in  (y:us, f (t:|y:us) : zs)

Edit: though I suppose it could be nice to make this not depend on permutations and instead implement permutations in terms of permutations1
Making this not depend on permutations is unnecessary. They can be mutually recursive. You can define permutations e.g. as

permutations :: [a] -> NonEmpty [a]
permutations = maybe ([] :| []) (fmap toList . permutations1) . NE.nonEmpty

However, it's possible that this performs slightly worse than keeping the original permutations implementation, since it has to do I believe n calls to NE.nonEmpty for a list of length n.

[JakobBruenker]

After some benchmarking, it looks like it makes more sense to keep permutations as is, rather than having it depend on permutations1. It seems silly to have two functions that are implemented so similarly, but even after spending some time with it, I couldn't come up with mutually recursive pair of functions (or even just recursive permutations1) that's not >2x slower. Maybe someone else can.

(To be clear though, I stand by the permutations1 definition in the comment above - it's not as fast as the original permutations, but faster than the mutually recursive definition.)

[JakobBruenker]

Ah, there is also this pretty simple solution:

permutations1 :: NonEmpty a -> NonEmpty (NonEmpty a)
permutations1 xs = NE.fromList <$> permutations (toList xs)

It uses a partial function (but isn't partial itself), but the upside is that it's significantly faster than the version I posted above, almost as fast as permutations itself.

(I'm benchmarking these by deepseqing the result, FWIW - or to be more precise, using criterion's nf)

[kindaro]

Here is the draft pull request to GHC. @Bodigrim Dear Andrew, please activate whatever next steps need to be activated.

[Bodigrim]

I'd like to hear from semigroups experts. Does this addition fit nicely into existing API? CC @ekmett @phadej

[phadej]

My immediate reaction would be to add

Data.List.permutations1 :: [a] -> NonEmpty [a]

and maybe

Data.List.NonEmpty.permutations :: NonEmpty a -> NonEmpty (NonEmpty a)

---

But then seeing @JakobBruenker comment above the

Data.List.NonEmpty.permutations :: [a] -> NonEmpty [a]
Data.List.NonEmpty.permutations1 :: NonEmpty a -> NonEmpty (NonEmpty a)

after group functions make sense too, as original group (and permutations) don't have precise enough type.

EDIT: note these are that way because semigroups package was independent of base, so Data.List couldn't used NonEmpty type, that isn't a limitation anymore.

FWIW, #67 is the same, and would fit. At least should be considered.

I think having [a] -> NonEmpty [a] function named permutations is good. (Like we have Data.Foldable1.head!). It's a better type. Data.List monomorphisation makes open imports of Data.List discouraged already, so having an overlapping name is fine.

Yet, I'd like to have Data.List.NonEmpty.permutations :: NonEmpty a -> NonEmpty (NonEmpty a) like in my original proposal, as I'd expect functions in Data.List.NonEmpty to primarily work on NonEmpty.

So without an option to do a breaking change (getting to if we could start over, what and where we would do state), there are two suboptimal options, and I don't know which one is less bad.

[Bodigrim]

Dear CLC members, let's vote on adding Data.List.NonEmpty.permutations{,1} as detailed in https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8696.
@tomjaguarpaw @chessai @emilypi @mixphix @cgibbard

---

+1 from me. Names and types follow existing scheme for Data.List.NonEmpty.group{,1}.

[tomjaguarpaw]

+1

---

Doesn't seem like a critical part of the ecosystem, but I have no objections.

[cgibbard]

+1 for the additions to Data.List.NonEmpty

[emilypi]

+1

[Bodigrim]

Thanks all, 4 votes in favor are enough. Approved.

[phadej]

Doesn't seem like a critical part of the ecosystem, but I have no objections.

It would be weird if only critical changes were accepted. Don't discourage people from making however small improvements.

[tomjaguarpaw]

Firstly, you may be reading something into my message that I didn't intend.

Secondly, perhaps this is not the place to discuss it, but I'm curious to know why it would be weird if only critical changes were accepted. It seems to me that it would be perfectly self-consistent if base were maintained on a critical change basis only. I spend significant amounts of time and mental energy reading through and voting on each CLC proposal (I imagine the experience is similar for other CLC members) and I think it's important for the future of Haskell that volunteer energy is spent in the places where most benefit will be obtained.

Naturally, there are strong argument for other approaches too.

[phadej]

I spend significant amounts of time and mental energy reading through and voting on each CLC proposal (I imagine the experience is similar for other CLC members) and I think it's important for the future of Haskell that volunteer energy is spend in the places where most benefit will be obtained.

IIRC, when CLC members were asked to nominate first point was https://discourse.haskell.org/t/ann-core-libraries-committee-elections/3215

Candidates should have enough bandwidth to review merge requests to base on a semi-frequent basis (2 to 3 per month), and sustain this for their term in a healthy manner.

https://discourse.haskell.org/t/clc-election-january-2022/3839

Candidates should have enough bandwidth to review merge requests to base on a semi-frequent basis (2 to 3 per month), and sustain this for their 3 years term in a healthy manner.

Is there more than 3 proposal per month nowadays?

[tomjaguarpaw]

Could you please elaborate? Interpreted one way it sounds like you might be saying I'm not fit to fulfil my role on the committee. I'm sure you didn't mean to say that, so I would welcome a clarification.

As a point of information, as can be verified from the issue tracker there have been 33 proposals made since I joined the CLC in February. That's a bit over 6 months and therefore roughly 5 proposals per month, double the estimate of 2-3 per month. There have also been numerous non-proposal issues filed.

[phadej]

If there are significantly more issues than the ones reaching the vote, and CLC members feel there are too many proposals to look immediately, you could adapt the GHC steering committee way:

• For each new proposal (issue) a shepherd is assigned
• When proposal matures enough (i.e. the community feedback has settled) shepherd informs the rest of committee to review the proposal
• When the review by committee is done and addressed, committee votes.

Then a single member of committee don't need to look at every proposal immediately as issue is raised. Especially, I think it's a waste of time for whole committee to follow the initial bikishedding phase.

[konsumlamm]

Doesn't seem like a critical part of the ecosystem, but I have no objections.

It would be weird if only critical changes were accepted. Don't discourage people from making however small improvements.

I don't see how saying "I have no objections" and voting in favor of this proposal would discourage people from making similar proposals.

[phadej]

Sorry, but I read "Doesn't seem like a critical part of the ecosystem" as a snarky comment "why you bother me with this".

[tomjaguarpaw]

Thank you for clarifying your interpretation. I can confirm that my comment was not intended to be snarky, but I shall bear your comment in mind and try to communicate less ambiguously in the future. I would also appreciate it if in future, rather than making such assumptions, you asked for clarification.

[chshersh]

I'm trying to summarise the state of this proposal as part of my volunteering effort to track the progress of all approved CLC proposals.

Field	Value
Authors	@kindaro
Status	not merged
base version	Unknown
Merge Request (MR)	https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8696
Blocked by	nothing
CHANGELOG entry	missing (please, raise an MR to base to update changelog)
Migration guide	not needed

Please, let me know if you find any mistakes 🙂

---

@kindaro could you share a status update on the implementation and what are next steps? Also, please do let CLC know if you need any help, so we can coordinate and prioritise approved proposals accordingly!

[kindaro]

@chshersh   The only reason for the delay is an onset of overwhelming sadness. I am trying to get over it. Summer is coming, it will get better.

I remember that there are 2 pull requests to GHC that I opened and need to see through. Nothing technically challenging. I just need to put myself together.

Thank you for stepping up to track the progress of all approved CLC proposals, and your other efforts before that. We are blessed to have you.

[chshersh]

@kindaro Sending you some support 🫂

If you need an extra review or some thoughts on the PRs, feel free to ping me!
Alternatively, if you think that this work is too overwhelming, let us know, and we can find another volunteer to offload this work from you 👌🏻