Still more NonEmpty variants of inits & tails

[rhendric]

Previously: #67

We currently have:

List.inits, List.tails :: [a] -> [[a]]
NonEmpty.inits, NonEmpty.tails :: Foldable f => f a -> NonEmpty [a]
NonEmpty.inits1, NonEmpty.tails1 :: NonEmpty a -> NonEmpty (NonEmpty a)

These three result types ([[a]], NonEmpty [a], NonEmpty (NonEmpty a)) form an incomplete square; the missing type is [NonEmpty a], and there is a perfectly reasonable variant of these functions that would return that type (it resembles inits1/tails1 but doesn't require its input to be non-empty).

The names are up for debate since I'm unable to find an existing convention for functions matching these types. But I propose adding to Data.List.NonEmpty the following (with these names or better ones):

nonEmptyInits, nonEmptyTails :: Foldable f => f a -> [NonEmpty a]
nonEmptyInits = Prelude.map fromList . List.drop 1 . List.inits . Foldable.toList
nonEmptyTails = Prelude.map fromList . List.init . List.tails . Foldable.toList

These are subexpressions of the current implementations of inits1 and tails1, which should be refactored to reference them. If these implementations are later optimized to, e.g., make fewer unnecessary run-time checks for emptiness, exposing them as functions makes those improvements available to users who would otherwise be defining these variants themselves.

[tomjaguarpaw]

It seems these identities hold (could someone double check?)

List.inits == Foldable.toList . NonEmpty.inits
nonEmptyInits == Foldable.toList . NonEmpty.inits1

If that's so, then perhaps this new combinator should be called List.inits1?

[rhendric]

Putting the new functions in Data.List would introduce a circular dependency with Data.List.NonEmpty.

[mixphix]

-1. Just use toList if you're comfortable using NonEmpty.

[rhendric]

@mixphix, if my input is a possibly-empty list, toList . NonEmpty.inits1 doesn't suffice. Is that what you're recommending or have I misunderstood?

[mixphix]

Excuse me?

ghci> :m +Data.Foldable Data.List Data.List.NonEmpty
-- 1
ghci> Data.List.tails [1, 2, 3, 4]
[[1,2,3,4],[2,3,4],[3,4],[4],[]]
-- 2
ghci> Data.List.NonEmpty.tails (1 :| [2, 3, 4])
[1,2,3,4] :| [[2,3,4],[3,4],[4],[]]
-- 3
ghci> Data.List.NonEmpty.tails1 (1 :| [2, 3, 4])
(1 :| [2,3,4]) :| [2 :| [3,4],3 :| [4],4 :| []]
-- 4
ghci> Data.List.NonEmpty.toList $ Data.List.NonEmpty.tails1 (1 :| [2, 3, 4])
[1 :| [2,3,4],2 :| [3,4],3 :| [4],4 :| []]
-- 5
ghci> Data.List.NonEmpty.toList <$> Data.List.NonEmpty.tails1 (1 :| [2, 3, 4])
[1,2,3,4] :| [[2,3,4],[3,4],[4]]

ghci> let nonEmptyTails = fmap Data.List.NonEmpty.fromList . Data.List.init . Data.List.tails . Data.Foldable.toList
ghci> nonEmptyTails (1 :| [2, 3, 4])
[1 :| [2,3,4],2 :| [3,4],3 :| [4],4 :| []] -- same as 4
ghci> nonEmptyTails [1, 2, 3, 4]
[1 :| [2,3,4],2 :| [3,4],3 :| [4],4 :| []] -- same as 4

[tomjaguarpaw]

But nonEmptyTails also works on [a]; toList . tails1 doesn't.

[mixphix]

mapMaybe nonEmpty . Data.List.tails

This is not primitive, not useful, and not hard to get by without.

[rhendric]

Again, these functions appear as subexpressions of the existing inits1 and tails1 implementations, which seems like evidence of usefulness to me, as well as evidence that these are, if not ‘primitive’, at least more so than the approved inits1 and tails1.

I agree we can get by without it. It's not hard to implement, but neither is it hard to implement inits1 or tails1. There are, I think, interesting performance questions for these functions—namely, do they interfere with list fusion, and do they waste cycles checking at run time emptiness properties that can be known at compile time. I don't think answering these questions is trivial. So the actual thing I would hope to save users from doing by including nonEmptyInits and nonEmptyTails in base is not the cost of implementing them, but the cost of determining which of their possible implementations works best with the rest of base for optimization purposes. (I don't claim that my proposed implementation is at all optimal in this sense, but once the CLC approves some implementation I can iterate with GHC on getting the best implementation.)

Regardless, base already contains an implementation of both functions. They're just contained within the definitions of inits1 and tails1. I would think that the barrier to exposing an existing implementation should be lower than the barrier to taking on an additional function.

Sorry if this is too trivial a thing to suggest.

[Bodigrim]

Prior art is Data.ByteString.initsNE and Data.ByteString.tailsNE and work-in-progress PR, adding the same functions to text: haskell/text#558.

I personally think that this is a useful addition. It's fairly common to encounter things like tail . inits, which would be nice to rewrite without partial functions as NE.tail . initsNE.

[rhendric]

Sadly for me, those functions are analogous to the existing NonEmpty.inits, not my proposed variants. The ByteString analog of nonEmptyInits would return [NonEmptyByteString], if such a type were to exist.

[Bodigrim]

Ah, my bad, sorry.

I'm not really sure about it then. If we can come up with good, self-explaining names then improving consistency and symmetry would be nice. But otherwise - as one can guess from my mistake above - there is a cost of offering users too many confusingly similar alternatives.