Add a right-handed `(:|)` to `Data.List.NonEmpty`

[sjshuck]

Something like this:

pattern (:>) :: [a] -> a -> NonEmpty a
pattern xs :> x <- (initLast -> (,) xs x) where
    xs :> x = prependList xs $ singleton x

-- Perhaps unexported
initLast :: NonEmpty a -> ([a], a)
initLast (x :| xs) = case Data.List.unsnoc xs of
    Nothing      -> ([],     x)
    Just (ys, y) -> (x : ys, y)

or if PatternSynonyms are not acceptable in base, then a pair of functions comprising an Iso' (NonEmpty a) ([a], a).

[konsumlamm]

One problem I see with a pattern synonym is that it might give users the illusion that this is a constant time (or at least fast) operation, when it has to traverse the whole list, making it linear.

[sjshuck]

Patsyn or not, we should definitely have a note about O(N) performance.

But I agree. Constructing with (:>) and immediately destructuring with (:>) looks like it would be trivial but it incurs two, albeit interleaved, traversals.

[Bodigrim]

We have Data.List.unsnoc :: [a] -> Maybe ([a], a), so I think it would be useful to have your initLast as Data.List.NonEmpty.unsnoc :: NonEmpty a -> ([a], a).

Prior art for (:>) includes Data.Text, Data.Sequence and many more, so I think it is well attested.

[sjshuck]

Re: unsnoc, I'd have thought so too, but this discussion gives me pause. If the result type were (Maybe (NonEmpty a), a) that'd be a different story. But I don't love initLast either.

[treeowl]

We have Data.List.unsnoc :: [a] -> Maybe ([a], a), so I think it would be useful to have your initLast as Data.List.NonEmpty.unsnoc :: NonEmpty a -> ([a], a).

Prior art for (:>) includes Data.Text, Data.Sequence and many more, so I think it is well attested.

There are two functions that have a claim to that name. The other is

unsnoc2 :: NonEmpty a -> (Maybe (NonEmpty a), a)

I have no opinion about which should get what name.

[sjshuck]

I think the existence of

cons :: a -> NonEmpty a -> NonEmpty a
uncons :: NonEmpty a -> (a, Maybe (NonEmpty a))

would determine

snoc :: NonEmpty a -> a -> NonEmpty a
unsnoc :: NonEmpty a -> (Maybe (NonEmpty a), a)

so functions involving ([a], a) should be named something else.

[mixphix]

Perhaps a pattern synonym is unwise, and it would be better to offer a function (|:) :: [a] -> a -> NonEmpty a for building rather than matching.

[hasufell]

Any other opinions: @parsonsmatt @velveteer @TeofilC @Daniel-Diaz @ChickenProp @noughtmare @mpscholten @doyougnu

[sjshuck]

FWIW I would be happy with the aforementioned

snoc :: NonEmpty a -> a -> NonEmpty a
unsnoc :: NonEmpty a -> (Maybe (NonEmpty a), a)

as a stop-gap. Happy to toss in an MR too with Haddocks mentioning performance.

[doyougnu]

I have no opinions about the name but I am weakly against the pattern synonym having been bitten by traversals-due-to-a-synonym before and I think the haddock doc should state the performance characteristics regardless.

[parsonsmatt]

I don't like the pattern synonym - imo pattern synonyms really work best when it's O(1) to match effectively. Otherwise, it's better to signal with ViewPatterns or pattern guards that you're doing something potentially costly: mxs :> a vs (unsnoc -> (mxs, a))

I agree that uncons and unsnoc should have similar types. If uncons does Maybe (NonEmpty a) then so should unsnoc.