Is there a specific purpose for heterogeneous lists?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.