Skip to content

More NonEmpty variants of inits & tails #67

@hdgarrood

Description

@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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    approvedApproved by CLC votebase-4.18Implemented in base-4.18 (GHC 9.6)

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions