Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Restore tail :: DList a -> DList a? #98

Closed
andreasabel opened this issue Aug 31, 2021 · 7 comments
Closed

Restore tail :: DList a -> DList a? #98

andreasabel opened this issue Aug 31, 2021 · 7 comments

Comments

@andreasabel
Copy link

andreasabel commented Aug 31, 2021

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 #69 (comment)

@spl
Copy link
Owner

spl commented Aug 31, 2021

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
Copy link
Author

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. agda/agda#5387).

@spl
Copy link
Owner

spl commented Aug 31, 2021

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!

@spl spl closed this as completed Aug 31, 2021
@andreasabel
Copy link
Author

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 referenced this issue in ddssff/listlike Aug 31, 2021
andreasabel added a commit to ddssff/listlike that referenced this issue Sep 1, 2021
PR #5 offered a workaround for the regression in `dlist-1.0` which
changed the type of the `tail` function for difference lists (so it does
not have the type `DList a -> DList a` of a tail function anymore).

The problem with #5 is that it collapses the difference list to
compute its tail.

Here, we offer a solution that does not collapse the difference list,
by precomposing the `Data.List.tail` with the underlying function
`[a] -> [a]` of a difference list.   Data.List.Unsafe gives us access
to this function.

This problem would better be fixed upstream, see
spl/dlist#98
@andreasabel
Copy link
Author

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
Copy link

Bodigrim commented Sep 5, 2021

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
Copy link
Author

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 ddssff/listlike#15.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants