Come evitare la ricorsione infinita con un enumeratore personalizzato?

Question

Ho creato un metodo di estensione per trovare il numero di valori consecutivi in ​​una raccolta. Poiché è generico, consento al chiamante di definire "incrementor" che è un Func <> che dovrebbe incrementare il valore per verificare l'esistenza di un valore "successivo".

Tuttavia, se il chiamante passa un incrementore improprio (cioè x => x), causerà un loop ricorsivo infinito. Qualche suggerimento su un modo pulito per prevenire questo?

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor) 
{ 
    if (values == null) 
    { 
     throw new ArgumentNullException("values"); 
    } 
    if (incrementor == null) 
    { 
     throw new ArgumentNullException("incrementor"); 
    } 
    var nextValue = incrementor(startValue); 
    return values.Contains(nextValue) 
     ? values.CountConsecutive(nextValue, incrementor) + 1 
     : 1; 
} 

Answer 1

Nel senso più puro, questo è un tentativo allo Halting Problem ed è indecidibile. Per tutti tranne i casi più semplici, dovrai fidarti di quelli che chiamano il tuo metodo.

Come altri hanno mostrato, è possibile eseguire un semplice controllo di uguaglianza per mostrare che il valore successivo è diverso. Memorizzando ogni visitato lo T funzionerà ma dovrai preoccuparti della memoria eventualmente.

Come parte, ecco uno StackOverflowException facilmente implementato, quindi devi essere cauto su qualsiasi set di dati che avrà molto su valori consecutivi.

var x = Enumerable.Range(1, 100000).CountConsecutive(1, x => x+1); 

Answer 2

È possibile confrontare nextValue a startValue (avrete bisogno T per implementare IComparable).

Questo risolverà questo errore, non risolverà un brutto bug incrementore che restituisce un ciclo - a1, a2, a3, ..., an, a1. Non credo che si desidera gestire questo caso, però

Answer 3

Per affrontare il caso più semplice, si può fare questo:

var nextValue = incrementor(startValue); 
if (nextValue.Equals(startValue)) { 
    throw new ArgumentException("incrementor"); 
} 

Per caso generale, fare questo:

public static int CountConsecutive<T>(this IEnumerable<T> values, T startValue, Func<T, T> incrementor) { 
    if (values == null) { 
     throw new ArgumentNullException("values"); 
    } 
    if (incrementor == null) { 
     throw new ArgumentNullException("incrementor"); 
    } 
    ISet<T> seen = new HashSet<T>(); 
    return CountConsecutive(values, startValue, incrementor, seen); 
} 

private static int CountConsecutive<T>(IEnumerable<T> values, T startValue, Func<T, T> incrementor, ISet<T> seen) { 
    if (!seen.Add(startValue)) { 
     throw new ArgumentException("incrementor"); 
    } 
    var nextValue = incrementor(startValue); 
    return values.Contains(nextValue) 
     ? values.CountConsecutive(nextValue, incrementor) + 1 
     : 1; 
}