Since I am currently working on proposition *product/2* functions for
Enum/Stream I thought I may pipe in here.
When talking about Enumerables and Stream, there are a couple
mathematics terms worth using. Specifically the terms for the number of
elements of the set; a set's *cardinality. *
*Finite* cardinality*: *These are your normal sequences. For example, *Lists,
Trees, Maps, and Functions that halt.* Anything with *finite* cardinality
has an Integer Length.
*Aleph-0* cardinality: These are your basic *Countable* infinite sequences.
For example, *Natural numbers, Stream.**with_index, and so on. *Anything
with *Aleph-0* cardinality doesn't have an Integer Length.
*Aleph-1* or more: These are your *Uncountable* infinite sequences. For
example, *All R**eal Numbers. *Anything with *Aleph-1* cardinality is very
hard to reason with in a programming context.
The proposed Enumerable.exhaustible?/1 is checking if the sequence is *Finite
*or *Aleph-0. *Writing a function that returns *true* or *false* would be
very hard. We would have to solve the halting problem to do so.
But from what I understand, the goal is to improve the **correctness** of
Streams. The only thing I can think of that would be close to this is
checking if something is a Stream or not.
Data enumerables will always halt. Stream enumerables may or may not halt.
Something we can do is check if a Stream is *Aleph-0 *or *Aleph-1. *For
example, concatenating two *Aleph-0 *Streams is not a valid operation
because it makes the resulting Stream uncountable. *Unforchenetly,* as
already established, you can't determine a Stream *is* or *isn't* countable
without solving the halting problem.
So we are stuck with only being able to determine if an operation is *valid*,
or is *maybe valid*.
On Monday, July 24, 2017 at 2:28:00 AM UTC-7, José Valim wrote:
>
> Currently, both Enumerable.count/1 and Enumerable.member?/2 can return
>> {:error, __MODULE__} to fall back on a naive linear implementation that
>> takes neither countability nor exhaustibility into account––factors that
>> Enumerable.reduce/3 doesn't entirely rely on. If we want to group these
>> changes into the Enumerable module, this seem to me to be the place of
>> leverage for breaking API changes.
>>
>
> The reason count/1 and member?/2 exist is to provide better than linear
> time implementations. So I don't believe we need to change them and we
> definitely can't remove them - since replacing them by any other construct
> would remove the constant time benefits. For those functions, if they
> return {:error, __MODULE__}, then they could fallback to an implementation
> that guarantees terminability.
>
> - Enumerable.exhaustible?/1
>>
>> Pure opt-in to denote non-negative access: raises if implemented as
>> {:ok, false} in relevant functions, proceeds if {:ok, true} is returned,
>> defaults to {:error, __MODULE__} for existing infinite loop behaviour. Uses
>> the default for existing core types.
>>
>
> The access functions (fetch, at, etc) are not the only one that suffer
> from this issue, any aggregation function, such as sum, max, min, etc will
> have termination issues. As well as drop/take with negative values.
>
> We should also avoid double dispatching to functions: for example calling
> Enumerable.exhaustible? and then Enumerable.reduce because of the double
> dispatch cost. Protocol consolidation is available on production apps but
> still not available during scripts, compilation time, etc. This is not an
> Enumerable specific limitation. I would have added this exact same kind of
> concerns if the Sequence implementation moved forward.
>
> The other limitation here is that some functions are actually quite hard
> to guarantee they terminate. For example, Enum.flat_map/flat_map feels like
> they terminate but they can return an infinite collection to be flattened,
> which then means they won't terminate. What should be the default
> implementation for those? We will either have false positives or false
> negatives.
>
>
>> - Enumerable.seek/2
>>
>> Falls back to reduce/3 if not implemented, via a counter, re-implements
>> Enum.at/{2, 3} and dependents, return {:error, __MODULE__} to fall back
>> on reduce/3.
>>
>
> That sounds great to me. What if we call it Enumerable.fetch to mirror
> Enum.fetch? It may return {:ok, found} | :error | {:error, __MODULE__} -
> where the last one means to fallback to a linear-time implementation.
>
> I think at this point we can clearly treat them as two separate proposals.
> We should guarantee termination regardless if we can optimize functions
> such as fetch/2 and at/3 and vice-versa.
>
>
--
You received this message because you are subscribed to the Google Groups
"elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/elixir-lang-core/558c0d71-3276-4aba-a667-4e607b8515d4%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
