CODEWITHSUNDEEP
c#ienumerableinfinite
Ken Kin
Ken Kin

Reputation: 4713

Just when is a stackoverflow fair and sensible?

Code updated

For fixing the bug of a filtered Interminable, the following code is updated and merged into original: 

public static bool IsInfinity(this IEnumerable x) {
    var it=
        x as Infinity??((Func<object>)(() => {
            var info=x.GetType().GetField("source", bindingAttr);
            return null!=info?info.GetValue(x):x;
        }))();

    return it is Infinity;
}

bindingAttr is declared a constant.

The tricky things are:

If option 1 is applied, that is, enumerate on this enumerable, becomes an invalid operation. Isn't it weird to say that this lamp isn't used to illuminate(though it's true in my case).

If option 2 or option 3 is applied, that is, we planned the stack overflowing. Is it really as the title, just when stackoverflow is fair and sensible? Perfectly logical and reasonable?

The last choice is option 4. However, the stack in fact does not really overflow, since we prevented it by throwing a fake StackOverflowException. This reminds me that when Tom Cruise plays John Anderton said that: "But it didn't fall. You caught it. The fact that you prevented it from happening doesnt change the fact that it was going to happen."

Some good ways to avoid the illogical problems?

The code is compile-able and testable, note that one of OPTION_1 to OPTION_4 shoule be defined before compile.

Upvotes: 16

Views: 775

Answers (4)

Ark-kun
Ark-kun

Reputation: 6820

Infinite sequences may be perfectly iterable/enumerable. Natural numbers are enumerable and so are rational numbers or PI digits. Infinite is the opposite of finite, not enumerable.

The variants that you've provided don't represent the infinite sequences. There are infinitely many different infinite sequences and you can see that they're different by iterating through them. Your idea, on the other hand, is to have a singleton, which goes against that diversity.

If you have something that cannot be enumerated (like the set of real numbers), then you just shouldn't define it as IEnumerable as it's breaking the contract. If you want to discern between finite and infinite enumerable sequences, just crate a new interface IInfiniteEnumerable : IEnumerable and mark infinite sequences with it.

Interface that marks infinite sequences

public interface IInfiniteEnumerable<T> : IEnumerable<T> {
}

A wrapper to convert an existing IEnumerable<T> to IInfiniteEnumerable<T> (IEnumerables are easily created with C#'s yield syntax, but we need to convert them to IInfiniteEnumerable )

public class InfiniteEnumerableWrapper<T> : IInfiniteEnumerable<T> {
    IEnumerable<T> _enumerable;

    public InfiniteEnumerableWrapper(IEnumerable<T> enumerable) {
        _enumerable = enumerable;
    }

    public IEnumerator<T> GetEnumerator() {
        return _enumerable.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return _enumerable.GetEnumerator();
    }
}

Some infinity-aware routines (like calculating the sequence length)

//TryGetCount() returns null if the sequence is infinite
public static class EnumerableExtensions {
    public static int? TryGetCount<T>(this IEnumerable<T> sequence) {
        if (sequence is IInfiniteEnumerable<T>) {
            return null;
        } else {
            return sequence.Count();
        }
    }
}

Two examples of sequences - a finite range sequence and the infinite Fibonacci sequence.

public class Sequences {
    public static IEnumerable<int> GetIntegerRange(int start, int count) {
        return Enumerable.Range(start, count);
    }

    public static IInfiniteEnumerable<int> GetFibonacciSequence() {
        return new InfiniteEnumerableWrapper<int>(GetFibonacciSequenceInternal());
    }

    static IEnumerable<int> GetFibonacciSequenceInternal() {
        var p = 0;
        var q = 1;
        while (true) {
            yield return p;
            var newQ = p + q;
            p = q;
            q = newQ;
        }
    }
}

A test app that generates random sequences and tries to calculate their lengths.

public class TestApp {
    public static void Main() {
        for (int i = 0; i < 20; i++) {
            IEnumerable<int> sequence = GetRandomSequence();
            Console.WriteLine(sequence.TryGetCount() ?? double.PositiveInfinity);
        }
        Console.ReadLine();
    }

    static Random _rng = new Random();
    //Randomly generates an finite or infinite sequence
    public static IEnumerable<int> GetRandomSequence() {
        int random = _rng.Next(5) * 10;
        if (random == 0) {
            return Sequences.GetFibonacciSequence();
        } else {
            return Sequences.GetIntegerRange(0, random);
        }
    }
}

The program output something like this:

20
40
20
10
20
10
20
Infinity
40
30
40
Infinity
Infinity
40
40
30
20
30
40
30

Upvotes: 2

Imi
Imi

Reputation: 1579

As mentioned in the other post you linked, an infinite enumeration makes perfectly sense for C# to enumerate and there are an huge amount of real-world examples where people write enumerators that just do never end(first thing that springs off my mind is a random number generator).

So you have a particular case in your mathematical problem, where you need to define a special value (infinite number of points of intersection). Usually, that is where I use simple static constants for. Just define some static constant IEnumerable and test against it to find out whether your algorithm had the "infinite number of intersection" as result.

To more specific answer your current question: DO NOT EVER EVER cause a real stack overflow. This is about the nastiest thing you can do to users of your code. It can not be caught and will immediately terminate your process(probably the only exception is when you are running inside an attached instrumenting debugger).

If at all, I would use NotSupportedException which is used in other places to signal that some class do not support a feature(E.g. ICollections may throw this in Remove() if they are read-only).

Upvotes: 4

Sergey Zyuzin
Sergey Zyuzin

Reputation: 3834

If I understand correctly -- infinite is a confusing word here. I think you need a monad which is either enumerable or not. But let's stick with infinite for now.

I cannot think of a nice way of implementing this in C#. All ways this could be implemented don't integrate with C# generators.

With C# generator, you can only emit valid values; so there's no way to indicate that this is an infinite enumerable. I don't like idea of throwing exceptions from generator to indicate that it is infinite; because to check that it is infinite, you will have to to try-catch every time.

If you don't need to support generators, then I see following options :

  1. Implement sentinel enumerable: 

    public class InfiniteEnumerable<T>: IEnumerable<T> {
    private static InfiniteEnumerable<T> val;

    public static InfiniteEnumerable<T> Value {
        get {
            return val;
        }
    }

    public IEnumerator<T> GetEnumerator() {
        throw new InvalidOperationException(
            "This enumerable cannot be enumerated");
    }

    IEnumerator IEnumerable.GetEnumerator() {
        throw new InvalidOperationException(
             "This enumerable cannot be enumerated");
    }
}

    Sample usage: 

    IEnumerable<int> enumerable=GetEnumerable();

if(enumerable==InfiniteEnumerable<int>.Value) {
    // This is 'infinite' enumerable.
}
else {
    // enumerate it here.
}

  2. Implement Infinitable<T> wrapper: 

    public class Infinitable<T>: IEnumerable<T> {
    private IEnumerable<T> enumerable;
    private bool isInfinite;

    public Infinitable(IEnumerable<T> enumerable) {
        this.enumerable=enumerable;
        this.isInfinite=false;
    }

    public Infinitable() {
        this.isInfinite=true;
    }

    public bool IsInfinite {
        get {
            return isInfinite;
        }
    }

    public IEnumerator<T> GetEnumerator() {
        if(isInfinite) {
            throw new InvalidOperationException(
                "The enumerable cannot be enumerated");
        }

        return this.enumerable.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        if(isInfinite) {
            throw new InvalidOperationException(
                 "The enumerable cannot be enumerated");
        }

        return this.enumerable.GetEnumerator();
    }
}

    Sample usage: 

    Infinitable<int> enumerable=GetEnumerable();

if(enumerable.IsInfinite) {
    // This is 'infinite' enumerable.
}
else {
    // enumerate it here.
    foreach(var i in enumerable) {
    }
}

Upvotes: 3

Knaģis
Knaģis

Reputation: 21515

public IEnumerator<T> GetEnumerator()
{
    while (true)
        yield return default(T);
}

This will create an infinite enumerator - a foreach on it will never end and will just continue to give out the default value.

Note that you will not be able to determine IsInfinity() the way you wrote in your code. That is because new Infinity().Where(o => o == /*do any kind of comparison*/) will still be infinite but will have a different type.

Upvotes: 8

Related Questions