search

kowainik / slist

♾️ Sized list
https://kowainik.github.io/projects/slist
Mozilla Public License 2.0
46 stars 6 forks source link

len's maxBound? #37

Closed k0001 closed 3 years ago

k0001 commented 4 years ago

Thanks for the cool library @vrom911! I really like the docs!

One thing I think should be changed, because it could otherwise have catastrophic consequences, is the fact that len, length and genericLength return maxBound on infinite lists. There are at least a couple of problems with this.

First, that there's no way to tell apart, just by looking at this length value, a list of length maxBound from an infinite list. If this length value was to be used to decide, say, how many resources to allocate for some work, then maxBound will surely deplete all resources. This could be addressed by returning, say, -1 rather than maxBound. But…

Second, a program checking the length of a Slist would erroneously succeed where one using [] would diverge. This is not good. As unfortunate as diverging code is, a diverging program that prevents us from accomplishing the wrong thing is better than one that doesn't. This can be addressed by having the length of an infinite list result in error "Tried to obtain the length on an infinite Slist", which is still diverging code, but rather than hanging forever it aborts right away, which is definitely an improvement over length for plain lists.

Obviously, people are encouraged to use size rather than len, length or genericLength, but many times, particularly when code is implemented in terms of Foldable, referring to length will be unavoidable.

My recommendation is to change len and friends so that they loudly fail with error, rather than silently succeed with the wrong result.

Keep up the good work! I look forward to using this library!

vrom911 commented 4 years ago

Thank you for your kind words, @k0001!

This decision is made on purpose. I think that having partial methods in classes is even eviler. If one needs to run length, it is better to check is the list is infinite first. Luckily, with slist you can figure this out beforehand, unlike the list from base. Also, with having maxbound instead of -1 or other value, that would make no sense and can lead to even more problems, maxbound gives another guarantee, that the size is always increasing.

So my vision is instead of runtime errors or negative lengths anywhere in your code, it is better to add an additional check on the infinite lists. Eventually, if you need to allocate resources from an infinite list, you can use the advantage of slist and figure out that something is broken in your programme flow.

k0001 commented 4 years ago

Of course, one should have additional checks before working with infinite lists. However, my point is that if you don't perform those checks for whatever reason (perhaps you simply forgot), the consequences of maxBound could be catastrophic.

A partial function is never desirable, but it is still almost always better than a function that silently results in a significantly wrong value, as this one here.

Notice that people already have the better 'size' function. So making 'len' partial is less of an issue.

On Sun, Jun 21, 2020, 17:20 Veronika Romashkina notifications@github.com wrote:

Thank you for your kind words, @k0001 https://github.com/k0001!

This decision is made on purpose. I think that having partial methods in classes is even eviler. If one needs to run length, it is better to check is the list is infinite first. Luckily, with slist you can figure this out beforehand, unlike the list from base. Also, with having maxbound instead of -1 or other value, that would make no sense and can lead to even more problems, maxbound gives another guarantee, that the size is always increasing.

So my vision is instead of runtime errors or negative lengths anywhere in your code, it is better to add an additional check on the infinite lists. Eventually, if you need to allocate resources from an infinite list, you can use the advantage of slist and figure out that something is broken in your programme flow.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/kowainik/slist/issues/37#issuecomment-647134563, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAAAZZVDZTY6MGFO34C65JDRXYJKPANCNFSM4N4HYOGQ .

chshersh commented 4 years ago

@k0001 As @vrom911 already mentioned, if you want to handle cases with infinite lists, slist provides safe API for that — the size function. It's not a problem of a slist that the length function from the Foldable typeclass doesn't handle infinite data structures. If you write some polymorphic code in terms of Foldable and you expect it to work correctly on infinite data structure, you can consider using different abstractions.

In my experience, I had more troubles with partial functions, especially because it's extremely difficult to catch imprecise exceptions in pure code. The behaviour of len and length function is intentional. Moreover, it is documented. We don't hide any implementation details. If you want to have partial length, you can define a custom function. However, the library encourages safe interface.

Also, as @vrom911 correctly noticed, returning error or -1 on infinite lists breaks the property the length of an infinite list is greater or equal than the length of any other Slist. I find breaking this property more surprising and unexpected than returning -1 or silently failing.