¿Un iterador tiene un contrato implícito no destructivo?

10

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 de los métodos push y pop , es decir, métodos destructores de acceso) .

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

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

por ejemplo:

public IEnumerator<T> GetEnumerator()
{
    if (this.list.Count > 0)
        yield return this.Pop();
    else
        yield break;
}
    
pregunta Steven Evers 20.02.2012 - 07:03

4 respuestas

11

Creo que un Enumerador destructivo viola el Principio de menos asombro . Como ejemplo artificial, imagine una biblioteca de objetos de negocios que ofrece funciones de conveniencia genéricas. Escribo inocentemente 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 tu implementación decide inocentemente usar ambos. Es probable que se sorprendan por 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 piensen en las repercusiones al entregar la colección a una función de caja negra. 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> , imponen un contrato explícito con su InvalidOperationException - "La colección se modificó después de que se crea una instancia del enumerador". Podría argumentar que un verdadero profesional tiene una actitud de caveat emptor hacia cualquier código que no sea el suyo. La sorpresa de un enumerador destructivo se descubriría con pruebas mínimas.

    
respondido por el Corbin March 20.02.2012 - 18:07
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 puesta en cola creara una nueva cola que contuviera la cola antigua y el nuevo elemento en la cola. La cola de espera también devolverá una nueva cola y el elemento eliminado de la cola como un parámetro de salida.

La creación de un IEnumerator desde esta implementación no sería destructiva. Y déjeme decirle que implementar una cola funcional que funciona bien es mucho más difícil que implementar una pila funcional ejecutante (la pila Push / Pop funciona en la cola, porque una cola de cola funciona en la cola, la cola de cola funciona en la cabeza).

Mi punto es ... es trivial crear un Enumerador de Pila no destructivo implementando su propio mecanismo de Puntero (StackNode < T >) y utilizando 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 a push o pop antes de la sentencia current = _head; completes le daría una pila diferente para la enumeración que si no hubiera multihilo (es posible que desee usar 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, puedes cambiar sus valores. Si tuviera que crear un constructor de pila que tomara un StackNode como parámetro (y establezca el encabezado como pasado en el nodo). 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 abrir 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.

    
respondido por el Michael Brown 20.02.2012 - 20:06
0

En un intento de mantener las cosas "simples", .NET solo tiene un par de interfaces genéricas / no genéricas para las cosas que se enumeran llamando a GetEnumerator() y luego usando MoveNext y Current en el objeto recibido de allí, aunque hay al menos cuatro tipos de objetos que deberían 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 subproceso libre, pero pueden producir contenido diferente cada vez arbitrariamente
  3. Cosas que pueden enumerarse 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 devuelvan el mismo contenido siempre que existan.

Cualquier instancia que satisfaga una de las definiciones con números más altos también satisfará todas las más bajas, pero el código que requiere que 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. Podría decirse que no hay muchas razones para que algo que solo pudiera cumplir con la primera definición debería implementar IEnumerable<T> en lugar de IEnumerator<T> ; Si foreach loops pudiera aceptar IEnumerator<T> , tendría sentido para las cosas que solo se pueden enumerar una vez simplemente para implementar la última interfaz. Desafortunadamente, los tipos que solo implementan IEnumerator<T> son menos convenientes de usar en C # y VB.NET que los tipos que tienen un método GetEnumerator .

En cualquier caso, aunque sería útil si hubiera diferentes tipos enumerables para cosas que pudieran ofrecer diferentes garantías y / o una manera estándar de preguntar a una instancia que implemente IEnumerable<T> qué garantías puede ofrecer, no existe. Los tipos aún existen.

    
respondido por el supercat 16.02.2014 - 19:34
0

Creo que esto sería una violación del Principio de sustitución de Liskov que dice,

  

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 intercambiar cualquier IEnumerable sin alterar la corrección del programa, pero el uso de la cola destructiva alteraría ampliamente el comportamiento de los programas.

    
respondido por el Despertar 17.02.2014 - 00:01

Lea otras preguntas en las etiquetas