Restore `tail :: DList a -> DList a`?

[andreasabel]

In 1.0, the function tail changed to DList a -> [a], motivated by the removal of the recursor list.

However, what speaks against the following definition?

tail :: DList a -> DList a
tail (UnsafeDList f) = UnsafeDList (Data.List.tail . f)

This would be a proper efficient tail function for DList. The new tail (dlist-1.0) leaves the realm of DLists, so it seems it is already subsumed by Data.List.tail . toList.

Originally posted by @andreasabel in https://github.com/spl/dlist/pull/69#r699052240

[spl]

When Data.List.tail fails in that case, the error does not help you trace it to the source of the problem. That's why there is the explicit error below:

tail :: DList a -> [a]
tail xs = case toList xs of
  _ : ys -> ys
  [] -> error "Data.DList.tail: empty DList"

Do you have an actual need for tail :: DList a -> DList a? I'm skeptical that it's (a) useful and (b) worth introducing the indirect error.

[andreasabel]

Do you have an actual need for tail :: DList a -> DList a?

No, I just noted the API change and wondered why it was necessary.

Maybe tail :: DList a -> [a] should be deprecated altogether. It is (i) a partial function with (b) a definition below the Fairbairn threshold (tail . toList) that (c) can perfectly live outside of dlist as it does not access the internal definition of DList.

I found that errors like Data.DList.tail: empty DList are hard to track down in a large codebase, and partial functions like tail are a bit of a historical mistake (see e.g. https://github.com/agda/agda/pull/5387).

[spl]

In general, I agree with everything you said. But I think the error here is slightly better than the error you'd get from Data.List.tail, because you know the source was a DList and not a list. 😁

Thanks for the feedback. Always appreciated!

[andreasabel]

Do you have an actual need for tail :: DList a -> DList a?

No, I just noted the API change and wondered why it was necessary.

Actually, I was wrong. Indeed, package listlike repackages DList into a generic interface for list-like structures, and the loss of tail :: DList a -> DList a has to be compensated there: https://github.com/ddssff/listlike/blob/b43111c4764c5f0c4f5e4338f48481a9ff4d3536/src/Data/ListLike/DList.hs#L37-L41 Note that the compensation fromList . DLIst.tail is inefficient and could be helped by my above efficient variant.
Atm, users of the DList instance of ListLike get an inefficient tail when they expect an efficient one.

[andreasabel]

Let me allow another stab at this issue. I would also be grateful if you kept the issue open so that it is more visible to the community, and others can join the discussion.

I am deeply convicted that tail should be a (partial) endo-function on list structures t, so its type would be t a -> t a, and in the present case, DList a -> DList a. There are strong reasons:

• If one deviates from this type, t cannot be an instance of a list structure (see ListLike). Think of algebraic structures (rings, groups) and how their operations (like plus, inverse) have uniform types over all of the instances of the algebraic structure (like integers, reals,...).
• tail is the differentiation operator for streams, see e.g. the insightful work of Jan Rutten, Helle Hvid Hansen, Clemens Kupke and others. A differentiation operator is an endo-function always, not only in calculus (derivatives of functions), but also e.g. in language theory (the Brzozowski derivative on languages, regular expressions etc.). It would be weird if differentiation would depend on how its object is implemented, so e.g. differentiation of a polynomial (list of coefficients) does not give a polynomial, but a Fourier series. (This is an analogy to DList.tail not returning a DList, but an ordinary list.)

I understand that it is inconvenient to row back on the change of tail, but I think for the future of dlist this would be a great decision.

[Bodigrim]

From my perspective, if tail is deemed to be an antipattern because of its inefficiency, it would be better to remove it from API altogether instead of changing return type.

[andreasabel]

From my perspective, if tail is deemed to be an antipattern because of its inefficiency, it would be better to remove it from API altogether instead of changing return type.

@Bodigrim: tail is efficient if implemented properly, see https://github.com/ddssff/listlike/pull/15.