Esiste uno scopo specifico per le liste eterogenee?

13

Venendo da uno sfondo C # e Java, sono abituato alle mie liste omogenee, e questo per me ha senso. Quando ho iniziato a raccogliere Lisp, ho notato che le liste possono essere eterogenee. Quando ho iniziato a rovinare con la parola chiave dynamic in C #, ho notato che, a partire da C # 4.0, possono esserci anche liste eterogenee:

List<dynamic> heterogeneousList

La mia domanda è qual è il punto? Sembra che un elenco eterogeneo abbia un sovraccarico maggiore durante l'elaborazione e che, se è necessario memorizzare diversi tipi in un unico punto, potrebbe essere necessaria una struttura dati diversa. La mia ingenuità sta crescendo sulla sua brutta faccia o ci sono davvero momenti in cui è utile avere una lista eterogenea?

    
posta Jetti 01.02.2012 - 14:59
fonte

5 risposte

14

Il documento Raccolte eterogenee strongmente tipizzate di Oleg Kiselyov, Ralf Lämmel e Keean Schupke contiene non solo un'implementazione di liste eterogenee in Haskell, ma anche un esempio motivante di quando, perché e come useresti HLists. In particolare, lo stanno utilizzando per l'accesso sicuro al database controllato in fase di compilazione. (Pensa a LINQ, in effetti, la carta a cui fanno riferimento è la carta Haskell di Erik Meijer e altri che ha portato a LINQ.)

Citando il paragrafo introduttivo del documento HLists:

Here is an open-ended list of typical examples that call for heterogeneous collections:

  • A symbol table that is supposed to store entries of different types is heterogeneous. It is a finite map, where the result type depends on the argument value.
  • An XML element is heterogeneously typed. In fact, XML elements are nested collections that are constrained by regular expressions and the 1-ambiguity property.
  • Each row returned by an SQL query is a heterogeneous map from column names to cells. The result of a query is a homogeneous stream of heterogeneous rows.
  • Adding an advanced object system to a functional language requires heterogeneous collections of a kind that combine extensible records with subtyping and an enumeration interface.

Nota che gli esempi che hai fornito nella tua domanda non sono in realtà liste eterogenee nel senso che la parola è comunemente usata. Sono elenchi tipizzati debolmente o non tipizzati . Infatti, sono in realtà elenchi , poiché tutti gli elementi sono dello stesso tipo: object o dynamic . Sei quindi costretto a eseguire cast o test instanceof non selezionati o qualcosa del genere, per poter effettivamente lavorare in modo significativo con gli elementi, il che li rende debolmente tipizzati.

    
risposta data 01.02.2012 - 17:18
fonte
5

In breve, i contenitori eterogenei scambiano le prestazioni di runtime per la flessibilità. Se vuoi avere una "lista di cose" senza riguardo al particolare tipo di cose, l'eterogeneità è la strada da percorrere. I Lisps sono caratterizzati tipicamente in modo dinamico, e la maggior parte di essi è comunque una lista di valori in scatola, quindi è prevedibile un risultato minimo. Nel mondo Lisp, la produttività dei programmatori è considerata più importante delle prestazioni di runtime.

In un linguaggio tipizzato dinamicamente, i contenitori omogenei avrebbero in realtà un leggero overhead rispetto a quelli eterogenei, perché tutti gli elementi aggiunti dovrebbero essere controllati dal tipo.

La tua intuizione sulla scelta di una migliore struttura dati è al punto. In generale, più contratti puoi mettere sul tuo codice, più sai come funziona e più affidabile, manutenibile e & c; c. diventa. Tuttavia, a volte vuoi davvero vuoi un contenitore eterogeneo, e dovresti poterne avere uno se ne hai bisogno.

    
risposta data 01.02.2012 - 15:39
fonte
2

Nei linguaggi funzionali (come il lisp), si usa la corrispondenza del modello per determinare cosa succede a un particolare elemento in una lista. L'equivalente in C # sarebbe una catena di if ... elseif che controllano il tipo di un elemento ed eseguono un'operazione basata su questo. Inutile dire che la corrispondenza dei modelli funzionali è più efficiente del controllo del tipo di runtime.

Usare il polimorfismo sarebbe una corrispondenza più stretta con la corrispondenza del modello. Cioè, avere gli oggetti di una lista abbinare una particolare interfaccia e chiamare una funzione su quella interfaccia per ogni oggetto. Un'altra alternativa sarebbe quella di fornire una serie di metodi sovraccaricati che accettano un tipo di oggetto specifico come parametro. Il metodo predefinito che accetta Object come parametro.

public class ListVisitor
{
  public void DoSomething(IEnumerable<dynamic> list)
  {
    foreach(dynamic obj in list)
    {
       DoSomething(obj);
    }
  }

  public void DoSomething(SomeClass obj)
  {
    //do something with SomeClass
  }

  public void DoSomething(AnotherClass obj)
  {
    //do something with AnotherClass
  }

  public void DoSomething(Object obj)
  {
    //do something with everything els
  }
}

Questo approccio fornisce un'approssimazione alla corrispondenza del modello Lisp. Il modello di visitatore (come implementato qui, è un ottimo esempio di utilizzo per elenchi eterogenei). Un altro esempio potrebbe essere l'invio di messaggi dove, ci sono ascoltatori per determinati messaggi in una coda di priorità e utilizzando la catena di responsabilità, il dispatcher passa il messaggio e il primo gestore che corrisponde al messaggio lo gestisce.

Il rovescio della medaglia è la notifica a tutti coloro che registrano un messaggio (ad esempio il pattern Aggregatore eventi comunemente usato per l'accoppiamento lento di ViewModels nel pattern MVVM). Io uso il seguente costrutto

IDictionary<Type, List<Object>>

L'unico modo per aggiungere al dizionario è una funzione

Register<T>(Action<T> handler)

(e l'oggetto è in realtà un WeakReference per il gestore in ingresso passato). Quindi qui DEVO usare List < Object > perché al momento della compilazione, non so quale sarà il tipo chiuso. In fase di esecuzione, tuttavia, posso far sì che sarà quel tipo che è la chiave per il dizionario. Quando voglio attivare l'evento che chiamo

Send<T>(T message)

e di nuovo risolvo la lista. Non c'è alcun vantaggio nell'uso di List < dynamic > perché ho bisogno di lanciarlo comunque. Quindi, come vedi, ci sono meriti per entrambi gli approcci. Se invii in modo dinamico un oggetto utilizzando l'overloading del metodo, dinamico è il modo per farlo. Se sei FORCATO a cast a prescindere, potresti usare Object.

    
risposta data 01.02.2012 - 15:52
fonte
0

Hai ragione che l'eterogeneità comporta un sovraccarico in fase di esecuzione, ma, cosa più importante, indebolisce le garanzie di compilazione fornite dal tipografo. Anche così, ci sono alcuni problemi dove le alternative sono ancora più costose.

Nella mia esperienza, occupandomi di byte non elaborati tramite file, socket di rete, ecc., ti imbatti spesso in tali problemi.

Per dare un esempio reale, considera un sistema per il calcolo distribuito utilizzando futures . Un lavoratore su un singolo nodo può generare un lavoro di qualsiasi tipo serializzabile, producendo un futuro di quel tipo. Dietro le quinte, il sistema invia il lavoro a un peer, quindi salva un record che associa quell'unità di lavoro al particolare futuro che deve essere compilato una volta che viene restituita la risposta a tale lavoro.

Dove possono essere conservati questi documenti? Intuitivamente, quello che vuoi è qualcosa come Dictionary<WorkId, Future<TValue>> , ma questo ti limita a gestire solo un tipo di futuro nell'intero sistema. Il tipo più adatto è Dictionary<WorkId, Future<dynamic>> , poiché l'operatore può eseguire il cast sul tipo appropriato quando forza il futuro.

Nota : questo esempio viene dal mondo Haskell in cui non abbiamo sottotipizzazione. Non sarei sorpreso se ci fosse una soluzione più idiomatica per questo particolare esempio in C #, ma si spera sia ancora illustrativo.

    
risposta data 01.02.2012 - 16:40
fonte
0

ISTR che Lisp non ha strutture di dati diverse da un elenco, quindi se hai bisogno di qualsiasi tipo di oggetto di dati aggregati, avere sarà un elenco eterogeneo. Come altri hanno sottolineato, sono anche utili per serializzare i dati per la trasmissione o l'archiviazione. Una buona caratteristica è che sono anche a tempo indeterminato, quindi è possibile utilizzarli in un sistema basato su un'analogia di pipe e filtri e fare in modo che fasi di elaborazione successive aumentino o correggano i dati senza richiedere un oggetto dati fisso o una topologia del flusso di lavoro .

    
risposta data 01.02.2012 - 20:31
fonte

Leggi altre domande sui tag