Given a herd of horses, how do I find the average horn length of all unicorns?

Question

The question above is an abstract example of a common problem I encounter in legacy code, or more accurately, problems resulting from previous attempts at solving this problem.

I can think of at least one .NET framework method that is intended to address this problem, like the Enumerable.OfType<T> method. But the fact that you ultimately end up interrogating an object's type at runtime doesn't sit right with me.

Beyond asking each horse "Are you a unicorn?" the following approaches also come to mind:

• Throw an exception when an attempt is made to get the length of a non-unicorn's horn (exposes functionality not appropriate for each horse)
• Return a default or magic value for the length of a non-unicorn's horn (requires default checks peppered throughout any code that wants to crunch horn stats on a group of horses that could all be non-unicorns)
• Do away with inheritance and create a separate object on a horse that tells you if the horse is a unicorn or not (which is potentially pushing the same problem down a layer)

I have a feeling this is going to be best answered with a "non-answer." But how do you approach this problem and if it depends, what's the context around your decision?

I'd also be interested in any insights on whether this problem still exists in functional code (or maybe it only exists in functional languages that support mutability?)

This was flagged as a possible duplicate of the following question: How to avoid downcasting?

The answer to that question assumes that one is in possession of a HornMeasurer by which all horn measurements must be made. But that's quite an imposition on a codebase that was formed under the egalitarian principle that everyone should be free to measure the horn of a horse.

Absent a HornMeasurer, the accepted answer's approach mirrors the exception-based approach listed above.

There's also been some confusion in the comments on whether horses and unicorns are both equines, or if a unicorn is a magical subspecies of horse. Both possibilities should be considered--perhaps one is preferable to the other?

Answer 1

Assuming you want to treat a Unicorn as a special kind of Horse, there are basically two ways you can model it. The more traditional way is the subclass relationship. You can avoid checking the type and downcasting by simply refactoring your code to always keep the lists separate in the contexts where it matters, and only combine them in the contexts where you never care about Unicorn traits. In other words, you arrange it so you never get into the situation where you need to extract unicorns from a herd of horses in the first place. This seems difficult at first, but is possible in 99.99% of cases, and usually actually makes your code a lot cleaner.

The other way you might model a unicorn is just by giving all horses an optional horn length. Then you could test if it's a unicorn by checking if it has a horn length, and find the average horn length of all the unicorns by (in Scala):

case class Horse(val hornLength: Option[Double])

val horse = Horse(None)
val unicorn = Horse(Some(12.0))
val anotherUnicorn = Horse(Some(6.0))

val herd = List(horse, unicorn, anotherUnicorn)
val hornLengths = herd flatMap {_.hornLength}
val averageLength = hornLengths.sum / hornLengths.size

This method has the advantage of being more straightforward, with a single class, but the disadvantage of being much less extensible, and having sort of a roundabout way of checking for "unicornness." The trick if you go with this solution is to recognize when you start to extend it often that you need to move to a more flexible architecture. This kind of solution is much more popular in functional languages where you have simple and powerful functions like flatMap to easily filter out the None items.

Answer 2

You've pretty much covered all the options. If you have behavior that's dependent on a specific subtype, and it's mixed in with other types, your code has to be aware of that subtype; that's simple logical reasoning.

Personally, I'd just go with horses.OfType<Unicorn>().Average(u => u.HornLength). It expresses the intention of the code very clearly, which is often the most important thing since someone's going to end up having to maintain it later on.

Answer 3

There's nothing wrong in .NET with:

var unicorn = animal as Unicorn;
if(unicorn != null)
{
    sum += unicorn.HornLength;
    count++;
}

Using the Linq equivalent is fine too:

var averageUnicornHornLength = animals
    .OfType<Unicorn>()
    .Select(x => x.HornLength)
    .Average();

Based on the question you asked in the title, this is the code I would expect to find. If the question asked something like "what is average of animals with horns" that would be different:

var averageHornedAnimalHornLength = animals
    .OfType<IHornedAnimal>()
    .Select(x => x.HornLength)
    .Average();

Note that when using Linq, Average (and Min and Max) will throw an exception if the enumerable is empty and type T is not nullable. That's because the average really is undefined (0 / 0). So really you need something like this:

var hornedAnimals = animals
    .OfType<IHornedAnimal>()
    .ToList();
if(hornedAnimals.Count > 0)
{
    var averageHornLengthOfHornedAnimals = hornedAnimals
        .Average(x => x.HornLength);
}
else
{
    // deal with it in your own way...
}

Edit

I just think this needs adding... one of the reasons a question like this doesn't sit well with object-oriented programmers is that it assumes we're using classes and objects to model a data structure. The original Smalltalk-esque object oriented idea was to structure your program out of modules that were instantiated as objects and performed services for you when you sent them a message. The fact that we can also use classes and objects to model a data structure is a (useful) side effect, but they're two different things. I don't even think the latter should be considered object-oriented programming, since you could do the same thing with a struct, but it just wouldn't be as pretty.

If you're using object-oriented programming to create services that do things for you, then querying whether that service is actually some other service or concrete implementation is generally frowned upon for good reasons. You were given an interface (typically through dependency injection) and you should code to that interface/contract.

On the other hand, if you're (mis-)using the class/object/interface ideas to create a data structure or data model, then I personally don't see a problem with using the is-a idea to its fullest. If you've defined that unicorns are a sub-type of horses and it totally makes sense within your domain, then absolutely go ahead and query the horses in your herd to find the unicorns. After all, in a case like this we're typically trying to create a domain specific language to better express the solutions of the problems we have to solve. In that sense there's nothing wrong with .OfType<Unicorn>() etc.

Ultimately, taking a collection of items and filtering it on type is really just functional programming, not object-oriented programming. Thankfully languages like C# are comfortable handling both paradigms now.

Answer 4

But the fact that you ultimately end up interrogating an object's type at runtime doesn't sit right with me.

The trouble with this statement is that, no matter what mechanism you use, you will always be interrogating the object to tell what type it is. That can be RTTI or it can be a union or a plain data structure where you ask if horn > 0. The exact specifics change slightly but the intent is the same - you ask the object about itself in some way to see if you should interrogate it further.

Given that, it makes sense to use your language's support to do this. In .NET you'd use typeof for example.

The reason to do this goes beyond just using your language well. If you have an object that looks like another one but for some small change, the chances are you're going to find more differences over time. In your example of unicorns/horses you may say there's just horn length... but tomorrow you'll be checking to see if a potential rider is a virgin, or if the poop is glittery. (a classic real-world example would be GUI widgets that derive from a common base and you have to look for checkboxes and listboxes differently. The number of differences would be too great to simply create a single super object that held all possible permutations of data).

If checking an objects's type at runtime doesn't hold well, then your alternative is to split the different objects right from the start - instead of storing a single herd of unicorn/horses, you hold 2 collections - one for horses, one for unicorns. This can work very well, even if you store them in a specialised container (eg a multimap where the key is the object type... but then even though we store them in 2 groups, we're right back at interrogating the object type!)

Certainly an exception based approach is wrong. Using exceptions as normal program flow is a code smell (if you had a herd of unicorns and a donkey with a seashell taped to its head snuck in, then I'd say exception based approach is OK, but if you have a herd of unicorns and horses then checking each for unicorn-ness is not unexpected. Exceptions are for exceptional circumstances, not a complicated if statement). In any case, using exceptions for this problem is simply interrogating the object type at runtime, only here you're misusing the language feature to check for non-unicorn objects. You might as well code in a if horn > 0 and at least process your collection quickly, clearly, using fewer lines of code and avoiding any issues rising from when other exceptions are thrown (eg an empty collection, or trying to measure that donkey's seashell)

Answer 5

Since the question has a functional-programming tag, we could use a sum type to reflect the two flavors of horses and pattern matching to disambiguate between them. For instance, in F# :

type Equine =
| Horse
| Unicorn of hornLength: float

module equines =

  let averageHornLength (equines : Equine list) =
    equines 
    |> List.choose (fun x -> 
      match x with
      | Unicorn u -> Some(u)
      | _ -> None)
    |> List.average

let herd = [ Horse ; Horse ; Unicorn(35.0) ; Horse ; Unicorn(50.0) ]

printfn "Average horn length in herd : %f" (equines.averageHornLength herd) // prints 42.5

Over OOP, FP has the advantage of data/functions separation, which maybe saves you from the (unjustified ?) "guilty conscience" of violating the level of abstraction when downcasting to specific subtypes from a list of objects of a supertype.

In contrast with the OO solutions proposed in other answers, pattern matching also provides an easier extension point should another Horned species of Equine show up one day.

Answer 6

Short form of same answer at end requires reading book or web article.

Visitor Pattern

The problem has a mixture of horses and unicorns. (Violating the Liskov substitution principle is a common problem in legacy codebases.)

Add a method to horse and all subclasses

Horse.visit(EquineVisitor v)

Equine visitor interface looks something like this in java/c#

interface EquineVisitor {
  void visitHorse(Horse z);
  void visitUnicorn(Unicorn z);
}

Unicorn.visit(EquineVisitor v){
   v.visitUnicorn(this);
}

Horse.visit(EquineVisitor v){
   v.visitHorse(this);
}

To measure horns we now write....

class HornMeasurer implements EquineVistor {
    void visitHorse(Horse h){} // ignore horses
    void visitUnicorn(Unicorn u){
         double len = u.getHornLength();
         totalLength+=len;
         unicornCount++;
    }

    double getAverageLength(){
          return totalLength/unicornCount;
    }

    double totalLength=0;
    int unicornCount=0;
}

The visitor pattern is criticised for making refactoring and growth harder.

Short Answer: Use the design pattern Visitor to get double dispatch.

see also https://en.wikipedia.org/wiki/Visitor_pattern

see also http://c2.com/cgi/wiki?VisitorPattern for discussion of visitors.

see also Design Patterns by Gamma et al.

Answer 7

Assuming that in your architecture unicorns are a subspecies of horse and you encounter places where you get a collection of Horse where some of them may be Unicorns, I would personally go with the first method (.OfType<Unicorn>()...) because it is the most straightforward way of expressing your intention. For anyone who comes along later (including yourself in 3 months), it is immediately obvious what you are trying to accomplish with that code: pick out the unicorns from among the horses.

The other methods you listed feel like just another way of asking the question "Are you a unicorn?". For example, if you use some sort of exception based method of measuring horns, you might have code that would look something like this:

foreach (var horse in horses)
{
    try
    {
        var length = horse.MeasureHorn();
        //...
    }
    catch (NoHornException e)
    {
        continue;
    }
}

So now the exception becomes the indicator that something is not a unicorn. And now this isn't really an exceptional situation any more, but is part of normal program flow. And using an exception instead of an if seems even dirtier than just doing the type check.

Lets say you go the magic value route for checking horns on horses. So now your classes look something like this:

class Horse
{
    public double MeasureHorn() { return -1; }
    //...
}

class Unicorn : Horse
{
    public override double MeasureHorn { return _hornLength; }
    //...
}

Now your Horse class has to know about the Unicorn class and have extra methods to deal with things it doesn't care about. Now imagine you also have Pegasuss and Zebras that inherit from Horse. Now Horse needs a Fly method as well as MeasureWings, CountStripes, etc. And then the Unicorn class gets these methods too. Now your classes all have to know about each other and you have polluted the classes with a bunch of methods that shouldn't be there just to avoid asking the type system "Is this a unicorn?"

So what about adding something to Horses to say if something is a Unicorn and handle all horn measuring? Well, now you have to check for the existence of this object to know if something is a unicorn (which is just substituting one check for another). It also muddies the waters a little bit in that now you may have a List<Horse> unicorns that really holds all unicorns, but the type system and debugger can't easily tell you that. "But I know it is all unicorns" you say, "the name even says so." Well, what if something was poorly named? Or say, you wrote something with the assumption that it really would be all unicorns, but then requirements changed and now it might also have pegasi mixed in? (Because nothing like this ever happens, especially in legacy software /sarcasm.) Now the type system will happily put your pegasi in with your unicorns. If your variable had been declared as List<Unicorn> the compiler (or the runtime environment) would have a fit if you tried to mix in pegasi or horses.

Finally, all these methods are just a replacement for the type system check. Personally, I would rather not reinvent the wheel here and hope that my code works just as well as something that is built in and has been tested by thousands of other coders thousands of times.

Ultimately, the code needs to be understandable to you. The computer will figure it out regardless of how you write it. You are the one who has to debug it and be able to reason about it. Make the choice that makes your job easier. If for some reason, one of these other methods offers an advantage for you that outweighs clearer code in the couple spots it would show up, go for it. But that depends on your code base.

Answer 8

Well, it sounds like your semantic domain has an IS-A relationship, but you're a bit wary of using subtypes/inheritance to model this—particularly because of the runtime type reflection. I think however that you're scared of the wrong thing—subtyping does indeed come with dangers, but the fact that you're querying an object at runtime is not the problem. You'll see what I mean.

Object-oriented programming has leaned quite heavily on the notion of IS-A relationships, it has arguably leaned too heavily on it, leading to two famous critical concepts:

• Circle-ellipse problem
• Composition over inheritance

But I think there's another, more functional-programming-based way to look at IS-A relationships that perhaps doesn't have these difficulties. First, we want to model horses and unicorns in our program, so we are going to have a Horse and an Unicorn type. What are the values of these types? Well, I'd say this:

1. The values of these types are representations or descriptions of horses and unicorns (respectively);
2. They are schematized representations or descriptions—they're not free-form, they're constructed according to very strict rules.

That may sound obvious, but I think one of the ways people get into issues like the circle-ellipse problem is by not minding those points carefully enough. Every circle is an ellipse, but that doesn't mean that every schematized description of a circle is automatically a schematized description of an ellipse according to a different schema. In other words, just because a circle is an ellipse doesn't mean that a Circle is an Ellipse, so to speak. But it does mean that:

1. There is a total function that converts any Circle (schematized circle description) into an Ellipse (different type of description) that describes the same circles;
2. There is a partial function that takes an Ellipse and, if describes a circle, returns the corresponding Circle.

So, in functional programming terms, your Unicorn type doesn't need to be a subtype of Horse at all, you just need operations like these:

-- Convert any unicorn-description of into a horse-description that
-- describes the same unicorns.
toHorse :: Unicorn -> Horse

-- If the horse described by the given horse-description is a unicorn,
-- then return a unicorn-description of that unicorn, otherwise return
-- nothing.
toUnicorn :: Horse -> Maybe Unicorn

And toUnicorn needs to be a right inverse of toHorse:

toUnicorn (toHorse x) = Just x

Haskell's Maybe type is what other languages call an "option" type. For example, the Java 8 Optional<Unicorn> type is either an Unicorn or nothing. Note that two of your alternatives—throwing an exception or returning a "default or magic value"—are very similar to option types.

So basically what I've done here is reconstruct the concept IS-A relationship in terms of types and functions, without using subtypes or inheritance. What I would take away from this is:

1. Your model needs to have a Horse type;
2. The Horse type needs to encode enough information to determine unambiguously whether any value describes a unicorn;
3. Some operations of the Horse type need to expose that information so that clients of the type can observe whether a given Horse is a unicorn;
4. The clients of the Horse type will have to use these latter operations at runtime to discriminate between unicorns and horses.

---

So this is fundamentally an "ask every Horse whether it is an unicorn" model. You are wary of that model, but I think wrongly so. If I give you a list of Horses, all that the type guarantees is that the things that the items in the list describe are horses—so you are, inevitably, going to need to do something at runtime to tell which of them are unicorns. So there's no getting around that, I think—you need to implement operations that will do that for you.

In object-oriented programming, the familiar way of doing this is the following:

• Have a Horse type;
• Have Unicorn as a subtype of Horse;
• Use runtime type reflection as the client-accessible operation that discerns whether a given Horse is an Unicorn.

This does have a big weakness, when you look at it from the "thing vs. description" angle that I presented above:

• What if you have a Horse instance that describes a unicorn but is not an Unicorn instance?

Going back to the beginning, this is what I think is the really scary part about using subtyping and downcasts for modeling this IS-A relationship—not the fact that you have to do a runtime check. Abusing the typography a bit, asking a Horse whether it's an Unicorn instance is not synonymous with asking a Horse whether it is an unicorn (whether it is a Horse-description of a horse that is also an unicorn). Not unless your program has gone to great lengths to encapsulate the code that constructs Horses so that every time a client tries to construct a Horse that describes an unicorn, the Unicorn class is instantiated. In my experience, seldom do programmers do things this carefully.

So I'd go with the approach where there is an explicit, non-downcast operation that converts Horses to Unicorns. This could either be a method of the Horse type:

interface Horse {
    // ...
    Optional<Unicorn> toUnicorn();
}

...or it could be an external object (your "separate object on a horse that tells you if the horse is a unicorn or not"):

class HorseToUnicornCoercion {
    Optional<Unicorn> convert(Horse horse) {
       // ...
    }
}

The choice between these is a matter of how your program is organized—in both cases, you have the equivalent of my Horse -> Maybe Unicorn operation from above, you're just packaging it in different ways (that will admittedly have ripple effects on what operations the Horse type needs to expose to its clients).

Answer 9

OP's comment in another answer clarified the question, I thought

that's part of what the question is asking too. If I have a herd of horses, and some of them are conceptually unicorns, how should they exist so that the problem can be cleanly solved without too many negative impacts?

Phrased that way, I think we need more information. The answer probably depends on a number of things:

• Our language facilities. Eg, I'd probably approach this differently in ruby and javascript and Java.
• The concepts themselves: What is a horse and what is a unicorn? What data is associated with each? Are they exactly the same except for the horn, or do they have other differences?
• How else are we using them, aside from taking horn length averages? And what about herds? Maybe we should model them too? Do we use them elsewhere? herd.averageHornLength() seems to match our conceptual model.
• How are the horse and unicorn objects being created? Is changing that code up within the bounds of our refactoring?

In general, though, I wouldn't even think about inheritance and subtypes here. You have a list of objects. Some of those objects can be identified as unicorns, perhaps because they have a hornLength() method. Filter the list based on this unicorn-unique property. Now the problem has been reduced to averaging the horn length of a list of unicorns.

OP, let me know if I'm still misunderstanding...

Answer 10

A method GetUnicorns() that returns an IEnumerable seems the most elegant, flexible and universal solution to me. This way you could deal with any (combination of) traits that determine whether a horse will pass as a unicorn, not just class type or the value of a particular property.