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?


5 Answers 5


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.

  • 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, 2012 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.

  • 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, 2012 at 14:47
  • 2
    @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, 2012 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, 2012 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, 2012 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, 2012 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)

  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.

  • 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.
    – user7043
    Feb 1, 2012 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. Feb 1, 2012 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, 2012 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, 2012 at 15:05
  • @Heinzi, you're right...I'm sleepy today :P fixed Feb 1, 2012 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.


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.

  • Lisps have had other data structures since about 1965: O(1) vectors, for example, and first-class procedures (though they weren't closures until 1975). All modern Lisp languages have records/structs as well, which provide for type extensibility.
    – John Cowan
    Oct 29, 2020 at 17:33

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