¿Tiene un iterador un contrato implícito no destructivo?

11

Digamos que estoy diseñando una estructura de datos personalizada como una pila o una cola (por ejemplo, podría ser alguna otra colección ordenada arbitraria que tenga el equivalente lógico pushy los popmétodos, es decir, métodos de acceso destructivos).

Si estuviera implementando un iterador (en .NET, específicamente IEnumerable<T>) sobre esta colección que apareció en cada iteración, ¿eso estaría rompiendo IEnumerable<T>el contrato implícito?

¿ IEnumerable<T>Tiene este contrato implícito?

p.ej:

public IEnumerator<T> GetEnumerator()
{
    if (this.list.Count > 0)
        yield return this.Pop();
    else
        yield break;
}
Steven Evers
fuente

Respuestas:

12

Creo que un Enumerador destructivo viola el Principio de Menos Asombro . Como ejemplo artificial, imagine una biblioteca de objetos de negocios que ofrece funciones genéricas de conveniencia. Inocentemente escribo una función que actualiza una colección de objetos comerciales:

static void UpdateStatus<T>(IEnumerable<T> collection) where T : IBusinessObject
{
    foreach (var item in collection)
    {
        item.Status = BusinessObjectStatus.Foo;
    }
}

Otro desarrollador que no sabe nada sobre mi implementación o su implementación inocentemente decide usar ambas. Es probable que se sorprendan con el resultado:

//developer uses your type without thinking about the details
var collection = GetYourEnumerableType<SomeBusinessObject>();

//developer uses my function without thinking about the details
UpdateStatus<SomeBusinessObject>(collection);

Incluso si el desarrollador es consciente de la enumeración destructiva, es posible que no piense en las repercusiones al entregar la colección a una función de recuadro negro. Como autor de UpdateStatus, probablemente no voy a considerar la enumeración destructiva en mi diseño.

Sin embargo, es solo un contrato implícito. Las colecciones .NET, incluido Stack<T>, hacen cumplir un contrato explícito con sus InvalidOperationException- "La colección se modificó después de que se instanciara el enumerador". Se podría argumentar que un verdadero profesional tiene una actitud de advertencia ante cualquier código que no sea el suyo. La sorpresa de un enumerador destructivo se descubriría con pruebas mínimas.

Corbin March
fuente
1
+1 - para 'Principio de menos asombro' voy a citar eso en las personas.
+1 Esto es básicamente lo que estaba pensando también, también, ser destructivo podría romper el comportamiento esperado de las extensiones LINQ IEnumerable. Simplemente se siente extraño iterar sobre este tipo de colección ordenada sin realizar las operaciones normales / destructivas.
Steven Evers
1

Uno de los desafíos de codificación más interesantes que me dieron para una entrevista fue crear una cola funcional. El requisito era que cada llamada a la cola creara una nueva cola que contuviera la cola anterior y el nuevo elemento en la cola. Dequeue también devolvería una nueva cola y el elemento retirado como un parámetro fuera.

Crear un IEnumerator a partir de esta implementación no sería destructivo. Y déjenme decirles que implementar una cola funcional que funciona bien es mucho más difícil que implementar una pila funcional eficiente (la pila Push / Pop funciona en la cola, porque una cola en cola funciona en la cola, la cola funciona en la cabeza).

Mi punto es ... es trivial crear un enumerador de pila no destructivo mediante la implementación de su propio mecanismo de puntero (StackNode <T>) y el uso de la semántica funcional en el enumerador.

public class Stack<T> implements IEnumerator<T>
{
  private class StackNode<T>
  {
    private readonly T _data;
    private readonly StackNode<T> _next;
    public StackNode(T data, StackNode<T> next)
    {
       _data=data;
       _next=next;
    }
    public <T> Data{get {return _data;}}
    public StackNode<T> Next{get {return _Next;}}
  }

  private StackNode<T> _head;

  public void Push(T item)
  {
    _head =new StackNode<T>(item,_head);
  }

  public T Pop()
  {
    //Add in handling for a null head (i.e. fresh stack)
    var temp=_head.Data;
    _head=_head.Next;
    return temp;
  }

  ///Here's the fun part
  public IEnumerator<T> GetEnumerator()
  {
    //make a copy.
    var current=_head;
    while(current!=null)
    {
       yield return current.Data;
       current=_head.Next;
    }
  }    
}

Algunas cosas a tener en cuenta. Una llamada para empujar o hacer estallar antes de la instrucción current = _head; completar le daría una pila diferente para la enumeración que si no hubiera subprocesamiento múltiple (es posible que desee utilizar un ReaderWriterLock para protegerse contra esto). Hice que los campos en StackNode fueran de solo lectura pero, por supuesto, si T es un objeto mutable, puede cambiar sus valores. Si fuera a crear un constructor de pila que tomara un StackNode como parámetro (y estableciera la cabeza en el nodo pasado). Dos pilas construidas de esta manera no se impactarán entre sí (con la excepción de una T mutable como mencioné). Puedes empujar y hacer estallar todo lo que quieras en una pila, la otra no cambiará.

Y que mi amigo es cómo haces una enumeración no destructiva de una Pila.

Michael Brown
fuente
+1: Mis enumeradores de pila y cola no destructivos se implementan de manera similar. Estaba pensando más en la línea de PQ / montones con comparadores personalizados.
Steven Evers
1
Yo diría que use el mismo enfoque ... no puedo decir que haya implementado una PQ funcional antes ... aunque parece que este artículo sugiere usar secuencias ordenadas como una aproximación no lineal
Michael Brown
0

En un intento por mantener las cosas "simples", .NET solo tiene un par de interfaces genéricas / no genéricas para las cosas que se enumeran llamando GetEnumerator()y luego usando MoveNexty Currenten el objeto recibido de allí, aunque haya al menos cuatro tipos de objetos que debería admitir solo esos métodos:

  1. Cosas que se pueden enumerar al menos una vez, pero no necesariamente más que eso.
  2. Cosas que se pueden enumerar un número arbitrario de veces en contextos de subprocesos libres, pero que pueden generar de manera arbitraria contenido diferente cada vez
  3. Cosas que se pueden enumerar un número arbitrario de veces en contextos de subprocesos libres, pero pueden garantizar que si el código que las enumera repetidamente no llama a ningún método de mutación, todas las enumeraciones devolverán el mismo contenido.
  4. Cosas que se pueden enumerar un número arbitrario de veces, y se garantiza que devolverán el mismo contenido siempre que existan.

Cualquier instancia que satisfaga una de las definiciones numeradas más altas también satisfará todas las más bajas, pero el código que requiere un objeto que satisfaga una de las definiciones más altas puede romperse si se le da una de las más bajas.

Parece que Microsoft ha decidido que las clases que implementan IEnumerable<T>deben satisfacer la segunda definición, pero no tienen la obligación de satisfacer nada más elevado. Podría decirse que no hay muchas razones por las que algo que solo podría cumplir con la primera definición debería implementarse en IEnumerable<T>lugar de IEnumerator<T>; si los foreachbucles pudieran aceptar IEnumerator<T>, tendría sentido que las cosas que solo se pueden enumerar una vez simplemente implementen la última interfaz. Desafortunadamente, los tipos que solo se implementan IEnumerator<T>son menos convenientes de usar en C # y VB.NET que los tipos que tienen un GetEnumeratormétodo.

En cualquier caso, aunque sería útil si hubiera diferentes tipos enumerables para cosas que podrían hacer diferentes garantías, y / o una forma estándar de pedir una instancia que implemente IEnumerable<T>qué garantías puede ofrecer, todavía no existen tales tipos.

Super gato
fuente
0

Creo que esto sería una violación del principio de sustitución de Liskov que establece:

los objetos en un programa deben ser reemplazables con instancias de sus subtipos sin alterar la corrección de ese programa.

Si tuviera un método como el siguiente que se llama más de una vez en mi programa,

PrintCollection<T>(IEnumerable<T> collection)
{
    foreach (T item in collection)
    {
        Console.WriteLine(item);
    }
}

Debería poder cambiar cualquier IEnumerable sin alterar la corrección del programa, pero el uso de la cola destructiva alteraría ampliamente el comportamiento del programa.

Despertar
fuente