Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Coming from a C# and Java background, I'm used to my lists being homogeneous, and that makes sense to me. When I started picking up Lisp, I noticed that the lists can be heterogeneous. When I started screwing around with the dynamic keyword in C#, I noticed that, as of C# 4.0, there can be heterogeneous lists as well:

List<dynamic> heterogeneousList

My question is what is the point? It seems like a heterogeneous list will have much more overhead when doing processing and that if you need to store different types in one place you may need a different data structure. Is my naivety rearing its ugly face or are there truly times when it is useful to have a heterogeneous list?

share|improve this question
1  
Did you mean ...I noticed that the lists can be heterogeneous...? –  World Engineer Feb 1 '12 at 14:08
    
How is List<dynamic> different (for your question) from simply doing List<object> ? –  Peter K. Feb 1 '12 at 14:13
    
@WorldEngineer yes, I do. I have updated my post. Thanks! –  Jetti Feb 1 '12 at 14:18
    
@PeterK. I guess for everyday use, there isn't any difference. However, not every type in C# derives from System.Object so there would be edge cases where there are differences. –  Jetti Feb 1 '12 at 14:26

5 Answers 5

up vote 9 down vote accepted

The paper Strongly Typed Heterogenous Collections by Oleg Kiselyov, Ralf Lämmel, and Keean Schupke contains not only an implementation of heterogenous lists in Haskell, but also a motivating example of when, why and how you would use HLists. In particular, they are using it for type-safe compile-time checked database access. (Think LINQ, in fact, the paper they are referencing is the Haskell paper by Erik Meijer et al that led to LINQ.)

Quoting from the introductory paragraph of the HLists paper:

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.

Note that the examples you gave in your question are really not heterogenous lists in the sense that the word is commonly used. They are weakly typed or untyped lists. In fact, they are actually homogenous lists, since all elements are of the same type: object or dynamic. You are then forced to perform casts or unchecked instanceof tests or something like that, in order to actually be able to meaningfully work with the elements, which makes them weakly typed.

share|improve this answer
    
Thanks for the link and your response. You make a good point that the lists are truly not heterogeneous but weakly typed. I'm looking forward to reading that paper (probably tomorrow, got me a midterm tonight :) ) –  Jetti Feb 1 '12 at 16:27

Long story short, heterogeneous containers trade runtime performance for flexibility. If you want to have a “list of stuff” without regard to the particular type of stuff, heterogeneity is the way to go. Lisps are characteristically dynamically typed, and most everything is a cons-list of boxed values anyway, so the smallish performance hit is expected. In the Lisp world, programmer productivity is considered more important than runtime performance.

In a dynamically typed language, homogeneous containers would actually have a slight overhead compared to heterogeneous ones, because all elements added would need to be type-checked.

Your intuition about choosing a better data structure is on point. Generally speaking, the more contracts you can put in place on your code, the more you know about how it works, and the more reliable, maintainable, &c. it becomes. However, sometimes you really do want a heterogeneous container, and you ought to be allowed to have one if you need it.

share|improve this answer
1  
"However, sometimes you really do want a heterogeneous container, and you ought to be allowed to have one if you need it." - Why though? That is my question. Why would you ever need to just hodgepodge a bunch of data into a random list? –  Jetti Feb 1 '12 at 14:47
    
@Jetti: Say you have a list of user-entered settings of various types. You could make an interface IUserSetting and implement it several times over, or make a generic UserSetting<T>, but one of the problems with static typing is that you’re defining an interface before you know precisely how it’s going to be used. The things you do with integer settings are probably very different from the things you do with string settings, so what operations make sense to put in a common interface? Until you know for certain, it’s better to judiciously use dynamic typing, and make it concrete later. –  Jon Purdy Feb 1 '12 at 14:55
    
See that is where I run into problems. To me, that just seems like bad design, making something before you know what it'll do/be used. Also, in that case you could make the Interface with an object return value. Does the same thing as the heterogeneous list but is more clear and easier to fix once you know for certain what the types used in the interface are. –  Jetti Feb 1 '12 at 15:02
    
@Jetti: That’s essentially the same problem, though—a universal base class shouldn’t exist in the first place because, no matter what operations it defines, there will be a type for which those operations don’t make sense. But if C# makes it easier to use an object rather than a dynamic, then sure, use the former. –  Jon Purdy Feb 1 '12 at 15:06
1  
@Jetti: This is what polymorphism is about. The list contains a number of "heterogenous" objects even though they may be subclasses of a single superclass. From a Java point-of-view, you can get the class (or interface) definitions right. For other languages (LISP, Python, etc.) there's no benefit to getting all the declarations right, since there's not practical implementation difference. –  S.Lott Feb 1 '12 at 15:21

In functional languages (like lisp), you use pattern matching to determine what happens to a particular element in a list. The equivalent in C# would be a chain of if...elseif statements that check the type of an element and perform an operation based on that. Needless to say, functional pattern matching is more efficient than runtime type checking.

Using polymorphism would be a closer match to pattern matching. That is, having the objects of a list match a particular interface and calling a function on that interface for each object. Another alternative would be to provide a series of overloaded methods that take a specific object type as a parameter. The default method taking Object as its parameter.

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
  }
}

This approach provides an approximation to Lisp pattern matching. The visitor pattern (as implemented here, is a great example of usage for heterogenous lists). Another example would be for message dispatching where, there are listeners for certain messages in a priority queue and using chain of responsibility, the dispatcher passes the message and the first handler that matches the message handles it.

The flip side is notifying everyone who registers for a message (for example the Event Aggregator pattern commonly used for loose coupling of ViewModels in the MVVM pattern). I use the following construct

IDictionary<Type, List<Object>>

The only way to add to the dictionary is a function

Register<T>(Action<T> handler)

(and the object is actually a WeakReference to the passed in handler). So here I HAVE to use List<Object> because at compile time, I don't know what the closed type will be. At Runtime however I can enforce that it will be that Type that is the key for the dictionary. When I want to fire the event I call

Send<T>(T message)

and again I resolve the list. There is no advantage to using List<dynamic> because I need to cast it anyway. So as you see there are merits to both approaches. If you're going to dynamically dispatch an object using Method overloading, dynamic is the way to do it. If you are FORCED to cast regardless, might as well use Object.

share|improve this answer
    
With pattern matching, the cases are (usually - at least in ML and Haskell) set in stone by the declaration of the data type matched on. Lists containing such types aren't heterogenous either. –  delnan Feb 1 '12 at 14:54
    
I'm not sure about ML and Haskell but Erlang can match against any which means, if you've reached here because no other matches were satisfied, do this. –  Mike Brown Feb 1 '12 at 15:00
    
@MikeBrown - This is nice but doesn't cover WHY one would use heterogeneous lists and would not always work with List<dynamic> –  Jetti Feb 1 '12 at 15:03
4  
In C#, overloads are resolved at compile time. Thus, your example code will always call DoSomething(Object) (at least when using object in the foreach loop; dynamic is a different thing altogether). –  Heinzi Feb 1 '12 at 15:05
    
@Heinzi, you're right...I'm sleepy today :P fixed –  Mike Brown Feb 1 '12 at 15:50

You're correct that heterogeneity carries runtime overhead, but more importantly it weakens the compile-time guarantees provided by the typechecker. Even so, there are some problems where the alternatives are even more costly.

In my experience, dealing with raw bytes through files, network sockets, etc., you often run into such problems.

To give a real example, consider a system for distributed computation using futures. A worker on an individual node can spawn work of any serializable type, yielding a future of that type. Behind the scenes, the system sends the work off to a peer, and then saves a record associating that unit of work with the particular future that must be filled in once the answer to that work returns.

Where can these records be kept? Intuitively, what you want is something like a Dictionary<WorkId, Future<TValue>>, but this limits you to managing only one type of futures in the entire system. The more suitable type is Dictionary<WorkId, Future<dynamic>>, since the worker can cast to the appropriate type when it forces the future.

Note: This example comes from the Haskell world where we don't have subtyping. I would not be surprised if there's a more idiomatic solution for this particular example in C#, but it's hopefully still illustrative.

share|improve this answer

ISTR that Lisp doesn't have any data structures other than a list, so if you need any type of aggregate data object, it's going to have to be a heterogeneous list. As others have pointed out, they're also useful for serializing data for either transmission or storage. One nice feature is that they're also open-ended, so you can use them in a system based on a pipes-and-filters analogy and have successive processing steps augment or correct the data without requiring either a fixed data object or workflow topology.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.