More NonEmpty variants of inits & tails

[hdgarrood]

At the moment Data.List.NonEmpty has the following variants of inits and tails:

inits :: Foldable f => f a -> NonEmpty [a]
tails :: Foldable f => f a -> NonEmpty [a]

where the input list may be empty, but the output list is guaranteed to contain at least one element (namely, the input list). Note that inits and tails will always both include the empty list at the start and end of their return values, respectively:

-- Pretending that I can use regular list syntax for nonempty lists here
inits [1,2,3] = [[], [1], [1,2], [1,2,3]]
tails [1,2,3] = [[1,2,3], [2,3], [3], []]

While it seems reasonable to consider the empty list to be a prefix and a suffix of every list and therefore to include it in the return value, I'd argue it's not always an interesting or useful element. Sometimes, I want to use inits or tails on a list which I already know to be nonempty, and I only care about the nonempty prefixes/suffixes. To that end, I think it might be useful to have variants like this:

inits1 :: NonEmpty a -> NonEmpty (NonEmpty a)
tails1 :: NonEmpty a -> NonEmpty (NonEmpty a)

such that (modulo types), we'd have:

inits1 [1,2,3] = [[1], [1,2], [1,2,3]]
tails1 [1,2,3] = [[1,2,3], [2,3], [3]]

A concrete example where this would be useful is in the PureScript compiler: https://github.com/purescript/purescript/blob/8181c4fee34fdfa576ad7029ec2303f71020e1b6/src/Language/PureScript/TypeChecker/Entailment.hs#L261-L273
At the moment, we have code that uses regular lists, and does

for (init $ tails chain) $ \(tcd:tl) -> ...

where chain is a regular list which is known to be nonempty, and where we have an unsafe incomplete pattern match which doesn't blow up at runtime because of the init (which removes the empty list at the end of tails). With tails1, we could change chain to be a NonEmpty, and change the above line to

for (tails1 chain) $ \(tcd :| tl) -> ...

and have all of the non-emptiness facts that we are relying on tracked safely in the types.

[andreasabel]

+1. This proposal is consistent with the already existing group1: https://hackage.haskell.org/package/base-4.16.1.0/docs/Data-List-NonEmpty.html#v:group1

[emilypi]

+1

[chessai]

+1

[hdgarrood]

I am aware that as the issue creator I am responsible for making this happen, and I do intend to make a PR at some point, although I’m not sure exactly when I’ll get around to it.

[Bodigrim]

@hdgarrood yes, please raise an MR, so that we can vote on a specific implementation.

[Bodigrim]

@hdgarrood just a gentle reminder to raise an MR, so that we can proceed forward.

[hdgarrood]

https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8880

[hdgarrood]

This just landed: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8880 so I guess this issue can be closed?

[Bodigrim]

No, Ben mistakenly went ahead with a merge without CLC approval. If the proposal happens to be declined, we'll revert.

Dear CLC members, let's vote on https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8880, adding inits1, tails1 :: NonEmpty a -> NonEmpty (NonEmpty a). @tomjaguarpaw @cgibbard @emilypi @mixphix

---

+1 from me, seems pretty uncontroversial.

[tomjaguarpaw]

+1

[mixphix]

+1, thank you @hdgarrood !

[emilypi]

+1 less work for ben, more things for us

[Bodigrim]

Awesome, 4 votes are enough to approve, thanks all.

[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	@hdgarrood
Status	merged
base version	4.18.0.0
Merge Request (MR)	https://gitlab.haskell.org/ghc/ghc/-/merge_requests/8880
Blocked by	nothing
CHANGELOG entry	present
Migration guide	not needed

Please, let me know if you find any mistakes 🙂