Luca Bolognese's WebLog

A C# library to write functional code - Part III - Records

Previous posts:

• Part I - Background
• Part II - Tuples

Now that we know what Tuples are, we can start talking about Record, as they use a derivative of Tuples under the cover. But first, what is a record?

Well, in C# parlance a Record is a sort of immutable value object. I talked at length about these fellows in this series of blog posts. In functional parlance, a Record is a Tuple that lets you access its items by name.

You code Records like this:

    public class Order: Record<string, int> {

        public Order(string item, int qty): base(item,qty) {}

        public string Item { get { return state.Item1;}}
        public int Quantity { get { return state.Item2; } }
    }

    public class Customer: Record<string, IEnumerable<Order>> {

        public Customer(string name, IEnumerable<Order> orders) : base(name, orders) { }

        public string Name { get { return state.Item1; } }
        public IEnumerable<Order> Orders { get { return state.Item2; } }
    }

You need to do three things:

1. Inherit from a generic Record class specifying the types of the properties as parameters
2. Add a constructor that calls back to the Record constructor
3. Add getters to retrieve the values of the properties (no setters as it is immutable)

This may seem like plenty of work, but in return you get structural equality. Coding that by hand every time you use a record would be a royal pain. You lose control of the base class, but that is often not a problem as in functional-land you more often use type unions than inheritance.

How is it implemented?

First of all it is an abstract class with as many generic parameters as properties that you need in your Record. Let's use two as an example.

    public abstract class Record<T1, T2> {

This abstract class has a field of type STuple:

        protected readonly STuple<T1, T2> state;

What is a STuple? Well it is exactly the same as the Tuple described in Part II, but coded as a struct instead of a class. The reason to use a struct is to not allocate an additional object on the stack. This allows this solution to be as 'performant' as simply having coded the fields on the class itself. Or at least I think so ...

The Record class also has a constructor that simply initialize the STuple:

        public Record(T1 t1, T2 t2) { state = F.STuple(t1, t2); }

where

        internal static STuple<T1, T2> STuple<T1, T2>(T1 t1, T2 t2) {

            return new STuple<T1, T2>(t1, t2);
        }

The Equals method is very much the same as the Tuple's one, just delegating to the same DSEqual function that checks equality for Tuples.

        public override bool Equals(object right) {

            Utils.CheckNull(right);

            if (object.ReferenceEquals(this, right))
                return true;

            if (this.GetType() != right.GetType())
                return false;

            var rightT = right as Record<T1, T2>;

            return F.DSEquals(this.state, rightT.state);
        }

That's it. Not too difficult as most of the implementation is based on the Tuple's code. Next post will hopefully be more interesting. It is about Type Unions.

A C# library to write functional code - Part II - Tuples

Previous posts:

• Part I - Background

Tuples are a way for you not to name things. In Object Oriented languages you got to name everything. If you need to represent a bunch of data, you create a class for it.

There is a strange asymmetry in mainstream OO languages in that you can pass multiple parameters to a function, but you can return just one value. Granted, there are ways around it: you can use 'ref' in C# or return some sort of collection where things are stored. But by and large the model is: you pass many, you get one; if you need to return more than one, create a class to represent this 'bunch of data'. Tuples are a way for you not to create such a class.

Tuples are also much more than that. Once you have the language concept of 'a bunch of data without a name', you can create arrays of them, you can pass them as parameters, use them as local variables. Wherever you'd use a type, you can use a Tuple instead.

This is particularly appealing to me as I like to use classes almost exclusively to represent things that have a counterpart in the domain I'm modeling (i.e. Customer, Account). I don't like to create classes/structs just for the sake of temporarily put some data together.

You can create your own Tuple class in C#, but the syntax gets ugly. Syntax matter. Syntax helps you to think differently about your program. We have syntax for anonymous types, but given that they cannot escape the scope of a method, they cannot be used as full replacement for Tuples.

In any case, to my implementation. Here is how you create a Tuple:

            var t1 = F.Tuple(34, "bo", 2.3);

not too bad. In F# it is better: (34, "bo", 2.3). And you often don't need the parenthesis. But still, my C# version is ok.

You then need to access its elements:

            var n = t1.Item1;
            var s = t1.Item2;

In F# you usually access them by doing pattern matching, which gives a more intuitive syntax. But again, my C# syntax is not terrible. 

Tuples need to have structural equality, which means that the following has to work:

        ArrayList mad1 = new ArrayList { new List<IEnumerable<string>> { new string[] { "bo" }, new string[] { "bo" } },
                               32, "bo", new int[] { 4, 5, 6 } };
        ArrayList mad2 = new ArrayList { new List<IEnumerable<string>> { new string[] { "bo" }, new string[] { "bo" } },
                               32, "bo", new int[] { 4, 5, 6 } };
        ArrayList mad3 = new ArrayList { new List<IEnumerable<string>> { new string[] { "bo" }, new string[] { "bo" } },
                               32, "bo", new int[] { 4, 5, 5 } };

        Assert.AreEqual(F.Tuple(mad1, mad2, mad1), F.Tuple(mad2, mad1, mad2));
        Assert.AreNotEqual(F.Tuple(mad1, mad2, mad1), F.Tuple(mad1, mad3, mad1));

You can use Tuples as return values, parameters, locals etc. Unfortunately, the syntax is ugly when Tuples are part of the signature of a function:

    public Tuple<string, IEnumerable<Tuple<string, ObservationHistory>>> Execute() {

    }

With the above information, you can be a user of Tuples. From this point on, I'll talk about some details of the implementation (I also attach the full code to this post as a zip file).

    public class Tuple<T1> {

        public Tuple(T1 t1) {

            Item1 = t1;
        }

        public readonly T1 Item1;

        #region Equals, GetHashCode, ==, !=
    }

    public class Tuple<T1, T2> : Tuple<T1> {

        public Tuple(T1 t1, T2 t2) : base(t1) { Item2 = t2; }

        public readonly T2 Item2;

        #region Equals, GetHashCode, ==, !=
    }

 

So, Tuples are classes, not structs. The reason for it is fully described in this series of posts. They also inherit from one another. There are pros and cons to that. The main pros are that I had to write less code and that you can pass a Tuple<int, string> when a function expects a Tuple<int, string, int>. The main drawback is that you can pass a Tuple<int, string> when a function expects a Tuple<int, string, int>.  Also notice the use of public fields. These is a problem with frameworks that insist on properties (i.e. Data Binding). Also, I just got to 5 as arity goes. The day I need 6 items, I'll add another one. It is boilerplate code (that I'd still like not to write).

The Equals method is a bit convoluted:

    internal static class Utils {

        public static void CheckNull<T>(T t) {

            if (t == null)
                throw new ArgumentNullException();
        }
     }

       public override bool Equals(object right) {

            Utils.CheckNull(right);

            if (object.ReferenceEquals(this, right))
                return true;

            if (this.GetType() != right.GetType())
                return false;

            var rightT = right as Tuple<T1, T2, T3>;

            return base.Equals(rightT) && F.DSEquals(this.Item3, rightT.Item3);
        }

I always get complaints when I show Equals methods that throw if null is passed in, but I stand by my logic, that the presence of null for these categories of 'structurally equal' classes is symptom of an error and I want to be notified. Returning false doesn't do that.

        internal static bool DSEquals<T>(T left, T right) {

            if (left == null && right == null)
                return true;

            if (left == null && right != null)
                return false;

            var len = left as IEnumerable;
            var ren = right as IEnumerable;

            if (len == null && ren == null)
                return left.Equals(right);

            if (len == null && ren != null)
                return false;

            if (len != null && ren == null)
                return false;

            return SequenceEqual(len, ren);
        }

DSEquals check the content of the Tuple and forward to SequenceEqual in case one slot of the Tuple contains an IEnumerable.

        internal static bool SequenceEqual(IEnumerable en1, IEnumerable en2) {

            var enumerator = en2.GetEnumerator();
            foreach (var o in en1) {

                if (!enumerator.MoveNext())
                    return false;

                if (!DSEquals(o, enumerator.Current))
                    return false;
            }

SequenceEqual checks that the number of items in the enumerator is the same and recursively calls DSEqual to check structural equality for items at the same index in the two enumerators.

GetHashCode is trivial (and maybe trivially wrong, one of these days I'll learn everything about GetHashCode() ).

        public override int GetHashCode() {

            return base.GetHashCode() | Item3.GetHashCode();
        }

The equality operators are equally simple.

        public static bool operator ==(Tuple<T1, T2, T3> t1, Tuple<T1, T2, T3> t2) {

            Utils.CheckNull(t1);
            Utils.CheckNull(t2);

            return t1.Equals(t2);
        }
        public static bool operator !=(Tuple<T1, T2, T3> t1, Tuple<T1, T2, T3> t2) {

            return !(t1 == t2);
        }

And ToString() prints my favorite Tuple format.

        public override string ToString() {

            return string.Format("{0},{1}", base.ToString(), Item3.ToString());
        }

I'm sure you can find plenty of issues in this code. As always, it is not 'production ready', it is more 'Luca having fun doing it'. In any case, there are some testcases in the solution to check the extent of my testing.

In the next post we'll look at Records.

A C# library to write functional code - Part I - Background

In December (slow time in msft) I decided to understand what functional programming is all about. When I say 'understanding' I don't mean just paying lip service to the main concepts by knowingly mentioning them in casual conversations (i.e. "look at this memoization, man!" or "this lambda function is so hot!". I can already do that. I intellectually know what the thing is.

I wanted to *really* understand it. For me that means writing plenty of code. I had a medium size application in my mind that I've been wanting to write for quite some time (stock price, dividends, splits downloading and various return calculations), so I went ahead and wrote it. I also wanted to use C#. It would have been easier in F#, but I work on the C# team and love using our own product.

My early attempts were unpleasing. I would fall back to my OO background and my functional code slowly reverted to OO code. My way of thinking about it, even if starting with the best intentions, would go back to: what are the objects, what are their responsibilities and such.

I needed to force myself somehow; kind of overcompensate on the other side. I hit on the idea of pragmatically defining functional programming and try to limit myself to the subset of language constructs inside my definition. As a way to define it, I used Chapter 3 of "Expert F#". I know, I know, I could have read 1,000s of academic papers and come up with a meta-analysis of all of them that formally defines what 'functional programming' really is. But life is too short. I trusted Don.

The problem is, several of the language constructs in my small definition of functional programming don't exist in C#. So I went ahead and created them. I built a little library to represent them and forced myself to write code using just this library. It worked.

In this series of posts I will describe what's inside this library. I want to emphasize that I built it for educational purpose only, not for performance or production code. Caveat emptor.

My plan is to cover the following:

1. Tuples
2. Records
3. Type Unions
4. Match

Let's see if I can find the time to actually write these posts :-)

"LINQ to SQL Overview" video

This is my presentation from TechEd Barcelona: http://www.microsoft.com/emea/msdn/spotlight/sessionh.aspx?videoid=716. The European locale brings out my Italian accent ...

 On this page there are a bunch of interesting presentations (i.e. Anders on LINQ): http://www.microsoft.com/emea/msdn/spotlight/default.aspx

Creating an immutable value object in C# - Part V - Using a library

Other posts:

Part I - Using a class

Part II - Making the class better

Part III - Using a struct

Part IV - A class with a special value

In the last post we presented a variation of implementing a value object using a class. Everything works (obviously), but the amount of code to write is unpleasing. In this post we examine a library based solution. I just describe how to use the Record class, not how it is implemented. You can read the attached implementation code (it is in functional.cs). There is much more in there than "Record<...>". I'll talk about the rest in a (hopefully) upcoming series.

To use the record class you need to inherit from it, as in:

public class DateSpan: Record<DateTime, DateTime, bool> {...}

The generic argument types represent the types that comprise the (immutable) state of the object. You then need a friendly way for folks to access this state:

    public DateTime Start { get { return state.Item1; } }
    public DateTime End { get { return state.Item2; } }
    public bool HasValue { get { return state.Item3; } }

This is all you have to do. You don't need to implement "Equals", "==", "!=" and "GetHashCode". Structural equivalence is given to you by the Record class. Such a property is recursive, in the sense that you can embed value objects inside other value objects and the implementation would walk your object graph as necessary.

For example, given the following class hierarchy:

    public class Order: Record<string, int> {

        public Order(string item, int qty): base(item,qty) {}

        public string Item { get { return state.Item1;}}
        public int Quantity { get { return state.Item2; } }
    }

    public class Customer: Record<string, IEnumerable<Order>> {

        public Customer(string name, IEnumerable<Order> orders) : base(name, orders) { }

        public string Name { get { return state.Item1; } }
        public IEnumerable<Order> Orders { get { return state.Item2; } }
    }

The following test case succeed:

        [TestMethod]
        public void Record2Test() {

            var c1 = new Customer("Luca", new Order[] { new Order("car",1), new Order("stereo", 3)});
            var c11 = new Customer("Luca", new Order[] { new Order("car", 1), new Order("stereo", 3) });
            var c2 = new Customer("Bob", new Order[] { new Order("car", 1), new Order("stereo", 3) });
            var c3 = new Customer("Bob", new Order[] { new Order("car", 1), new Order("stereo", 2) });

            Assert.AreEqual(c1, c11);
            Assert.AreNotEqual(c1, c2);
            Assert.AreNotEqual(c1, c3);
            Assert.AreNotEqual(c2, c3);

        }

Please don't take my library as production ready code. The amount of test I put into it is limited. You can probably find obvious bugs with it.

Let's look at other drawbacks. The biggest one is that I'm stealing your base class. If you want your value object to inherit from something else, you cannot. You cannot even have value objects inherit from each other. In that case you are back to implementing your own Equals, == and so on. The only tools at your disposal are interfaces and composition.

Another drawback is that writing classes in this way is slightly unnatural. You have to think about the 'type' of your state in the declaration of the class itself instead of more naturally writing it closer to where you assign names to it (property/field declaration).

Having considered these drawbacks, I'm using this library in all my code wherever I need value objects (which is almost everywhere these days). Writing all the "Equals" explicitly is too error prone for my taste. I will also be creating IDE snippets for myself that make writing these classes easier.

I don't think I have anything else to say on this topic, so this will be my last post on it. If something else comes up, I'll let you know.

Book review: The Halo Effect

When I read "Built to Last", "In search of excellent" and "Good to great" I immediately thought: "What a bunch of BS!!". But again, I think that about most business books.

The content of these books seemed particularly ludicrous to me. I found both logical inconsistencies and methodological flaws in their process. For example, picking successful companies after the fact is analogous to picking the winners of a lottery and claim that they have exceptional skills. Betting the farm on a single concept (i.e. Big Hairy Goal) is clearly the right thing when you are right, but most often than not you are wrong. What about all the companies that did that and failed? Also, Keeping to the Core worked really well for Coca Cola, but really badly for Kodak.

These are just examples. These books are packed full of such reasonably sounding absurdities. I thought that everybody would immediately spot this. I thought that the mediocre subsequent performance of the companies originally selected as excellent would obviously demonstrate the unsoundness of such conclusion. I was very wrong. These tomes are hugely successful. People seemed to disagree with me. They really like this stuff. Given that my work and my life were not overly impacted one way or the other, I left the matter to rest.

And then came "The Halo Effect". It was a pleasure for me to read, as it confirmed my own ideas (confirmation bias anyone?) and added many more.

The title is slightly misleading. A better title would have been: "Why the idea of finding common traits among successful companies is baloney". I know, not as catchy. The catchy halo effect, mentioned in the title, is just the biggest delusion that people have about the topic.

I found an experiment recounted in the book to be very illuminating. They divided a set of people in multiple groups and gave each group a problem to solve. They then told half of the groups that they did a very good job and the other half that they did a very poor job. The thing is, they did so at random. They then asked people to rate the dynamics of their group on several factors. People that were told that they did a good job reported to have had wonderful dynamics: open discussions, inspired leaders, high caliber people and such. The opposite was true for the other groups.

It didn't matter what the actual dynamics had really been: some groups were very confrontational, others were very amicable; some were very vocal, others were very quiet. In the end, people who were told that they did good recalled the experience in positive terms. People who were told that they did poorly, recalled the experience in negative terms. Remember, good and bad outcomes were assigned randomly. Also, the results have been confirmed in several similar studies.

It is not a good strategy that drives performance. It is perceived performance that makes people think that they had a good strategy. This is: "The halo effect". This simple concept has dramatic repercussions.

First of all, it invalidates the main process used in these studies: if you use newspapers articles and managers recollection to draw conclusions, you are just piling halos over halos. People would certainly give all sort of positive attributes to companies that succeeded. They do it exactly because they succeeded. And when these companies fail, they suddenly give all sort of negative attributes to them. The book is full of examples of companies that were rated as excellent when their stock price went up and terrible when their stock price went down. Nothing changed in these companies, they were still doing the same exact thing.

The book contains many other insights of why these 'studies' are deeply flawed. It calls them delusions. You are probably familiar with some of them if you have a scientific background: for example, Delusion of Correlation and Causality, Delusion of Single Explanation (factors are not independent), Delusion of Connecting the Winning Dots (ad hoc after the fact selection). Other delusions are specific to the analyzed domain: Delusion of Lasting Success, Delusion of Absolute Performance, Delusion of Organizational Physics.

In the end what should managers do? Instead of following these books's precepts, they should focus on two things: strategy and execution. Both of these things are probabilistic endeavors where the absolutely wrong measuring stick is the result that you obtain. I always found this to be a very common error people fall into at whatever level in an organization. The error is judging the soundness of a decision by its result. A decision should be judged by the soundness of the process to get to the decision and the information available at the time the decision was taken. This is the only thing that is consistent with the probabilistic nature of the world we live in. The book profiles three leaders who embody this probabilistic view.

In summary, please go and read this book. There are many more things in it than I described in this (albeit long and boring) post.

Creating an immutable value object in C# - Part IV - A class with a special value

Other posts:

Part I - Using a class

Part II - Making the class better

Part III - Using a struct

In the last post we looked at structs as ways to implement immutable value objects and we discovered that they have several issues.

A good thing about the struct implementation was the introduction of an explicit 'special value' instead of 'null'. I personally like doing that because it forces me to think about what are the special values in my domain instead of blindly rely on null and its semantics. Plus, it also works where null breaks down, when there are multiple special values.

Having explicit special values is obviously not related to structs in any way. You can use the same pattern with classes as well, but you have to manage 'null' values that can enter your API. Here is how I did it for the DateSpan class.

First I defined an utility function to manage null values:

    public static void CheckNull<T>(T t) {

        if (t == null)
            throw new ArgumentNullException();
    }

Then I had to check my null precondition for each parameter of my API. I.E.

    public DateSpan Intersect(DateSpan other) {

        Utils.CheckNull(other);
        ...
    }

Most importantly I now have to check for null in 'Equals' and '==':

    public override bool Equals(object obj) {

        // Interesting choice, null is not valid in this domain
        Utils.CheckNull(obj);

        if (this.GetType() != obj.GetType()) return false;

        DateSpan other = obj as DateSpan;

        return other.End == End && other.Start == Start;
    }

    public static Boolean operator ==(DateSpan v1, DateSpan v2) {

        Utils.CheckNull(v1);
        Utils.CheckNull(v2);

        return (v1.Equals(v2));
    }

So now we have an immutable value object, represented as a class, with checks for nulls and a special value (not shown above because it is essentially the same as for structs). So, does this work?

It does, but it is cumbersome to write. And if it is too cumbersome, I already know that I'm not going to use it. I might start doing it, but I would soon give up. Are there ways to ease the pain?

One way would be to use snippets to help in writing the code. Snippets in this case have a couple of problems:

• It is not easy to 'snippify' the logic inside 'Equals', 'GetHashcode' and such
• It makes easy to write the code, but still it is hard to read it and maintain it

In the next post we'll look at a better solution.

Creating an immutable value object in C# - Part III - Using a struct

Other posts:

• Part I - Using a class
• Part II - Making the class better
• Part IV - A class with a special value

In Part II I talked about the asymmetry created by using 'null' as the special value for our little DateSpan domain. We also noticed the boredom of having to implement Equals, GetHashCode, '==' and '!=' for our value objects. Let's see if structs solve our problem.

Well, to the untrained eye they do. Structs cannot be null and they implement Equals and GetHashCode by checking the state of the object, not its pointer in memory.

So, have we found the perfect tool to implement our value object?

Unfortunately, no. Here is why a struct is a less than optimal way to implement a value object:

1. Convenience issues - it is not as convenient as it looks
   1. You still have to implement '==' and '!='.
   2. You still want to implement Equals() and GetHashCode(), if you want to avoid boxing/unboxing.
2. Performance issues - it is not as fast as it looks
   1. Structs are allocated on the stack. Every time you pass them as arguments, the state is copied. If your struct has more than a few fields, performance might suffer
3. Usability issues - it is not as useful as it looks.
   1. Structs always have a public default constructor that 'zeros' all the fields
   2. Structs cannot be abstract
   3. Structs cannot extend another structs

Don't get me wrong, structs are extremely useful as a way to represent small bundles of data. But if you use value objects extensively, their limitations start to show.

A case could be made that you should use struct to implement value objects if the issues exposed above don't apply to your case. When they do apply, you should use classes. I'm a forgetful and lazy programmer, I don't want to remember all these cases. I just want a pattern that I can use whenever I need a value object. It seems to me that structs don't fit the bill.

For the sake of completeness, here is the code for DateSpan using a struct. Note that I explicitly introduced a 'special value' instead of using null (which is not available for structs).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


public struct DateSpan {

    public static DateSpan NoValueDateSpan { get { return noValueDateSpan; } }

    public DateSpan(DateTime pstart, DateTime pend) {

        if (pend < pstart)
            throw new ArgumentException(pstart.ToString() + " doesn't come before " + pend.ToString());
        start = pstart;
        end = pend;
        hasValue = true;
    }

    public DateSpan Union(DateSpan other) {

        if (!HasValue)
            return other;

        if (!other.HasValue)
            return this;

        if (IsOutside(other))
            return DateSpan.NoValueDateSpan;

        DateTime newStart = other.Start < Start ? other.Start : Start;
        DateTime newEnd = other.End > End ? other.End : End;

        return new DateSpan(newStart, newEnd);
    }

    public DateSpan Intersect(DateSpan other) {

        if (!HasValue)
            return DateSpan.NoValueDateSpan;

        if (!other.HasValue)
            return DateSpan.NoValueDateSpan;

        if (IsOutside(other))
            return DateSpan.NoValueDateSpan;

        DateTime newStart = other.Start > Start ? other.Start : Start;
        DateTime newEnd = other.End < End ? other.End : End;

        return new DateSpan(newStart, newEnd);
    }

    public DateTime Start { get { return start; } }
    public DateTime End { get { return end; } }
    public bool HasValue { get { return hasValue; } }

    // Making field explicitely readonly (but cannot use autoproperties)
    // BTW: If you want to use autoproperties, given that it is a struct,
    // you need to add :this() to the constructor
    private readonly DateTime start;
    private readonly DateTime end;
    private readonly bool hasValue;

    private bool IsOutside(DateSpan other) {

        return other.start > end || other.end < start;
    }

    // Changing the internal machinery so that hasValue default is false
    // This way the automatically generated empty constructor returns the right thing
    private static DateSpan noValueDateSpan = new DateSpan();

    #region Boilerplate Equals, ToString Implementation

    public override string ToString() {
        return string.Format("Start:{0} End:{1}", start, end);
    }

    public static Boolean operator ==(DateSpan v1, DateSpan v2) {

        return (v1.Equals(v2));
    }
    public static Boolean operator !=(DateSpan v1, DateSpan v2) {

        return !(v1 == v2);
    }

    //public override bool Equals(object obj) {

    //    if (this.GetType() != obj.GetType()) return false;

    //    DateSpan other = (DateSpan) obj;

    //    return other.end == end && other.start == start;
    //}

    //public override int GetHashCode() {

    //    return start.GetHashCode() | end.GetHashCode();
    //}

    #endregion
}

Bisection-based XIRR implementation in C#

Here is a quick implementation of XIRR (using Excel nomenclature) written in C#.

Disclaimer: this is a super simple Bisection-based implementation. People tend to prefer the Newton method, but this is simpler and works for the app I'm writing. I decided to post it because I couldn't find one on the net when I looked for it. I attached testcases to show the extent of my testing.

It is called CalculateXIRR and it is invoked by passing a list of cash flows, a tolerance and a max number of iterations.

using System;
using System.Linq;
using Money = System.Decimal;
using Rate = System.Double;
using System.Collections.Generic;

public class CashFlow {

    public CashFlow(Money amount, DateTime date) { Amount = amount; Date = date; }

    public readonly Money Amount;
    public readonly DateTime Date;
}

public struct AlgorithmResult<TKindOfResult, TValue> {

    public AlgorithmResult(TKindOfResult kind, TValue value) {

        Kind = kind;
        Value = value;
    }

    public readonly TKindOfResult Kind;
    public readonly TValue Value;
}

public enum ApproximateResultKind {
    ApproximateSolution,
    ExactSolution,
    NoSolutionWithinTolerance
}

public static class Algorithms {

    internal static Money CalculateXNPV(IEnumerable<CashFlow> cfs, Rate r) {

        if (r <= -1)
            r= -0.99999999; // Very funky ... Better check what an IRR <= -100% means

        return (from cf in cfs
                let startDate = cfs.OrderBy(cf1 => cf1.Date).First().Date
                select cf.Amount / (decimal) Math.Pow(1 + r, (cf.Date - startDate).Days / 365.0)).Sum(); 
    }

    internal static Pair<Rate, Rate> FindBrackets(Func<IEnumerable<CashFlow>, Rate, Money> func, IEnumerable<CashFlow> cfs) {

        // Abracadabra magic numbers ...
        const int maxIter = 100;
        const Rate bracketStep = 0.5;
        const Rate guess = 0.1;

        Rate leftBracket = guess - bracketStep;
        Rate rightBracket = guess + bracketStep;
        var iter = 0;

        while (func(cfs, leftBracket) * func(cfs, rightBracket) > 0 && iter++ < maxIter) {

            leftBracket -= bracketStep;
            rightBracket += bracketStep;
        }

        if (iter >= maxIter)
            return new Pair<double, double>(0, 0);

        return new Pair<Rate, Rate>(leftBracket, rightBracket);
    }
   
    // From "Applied Numerical Analyis" by Gerald
    internal static AlgorithmResult<ApproximateResultKind, Rate> Bisection(Func<Rate, Money> func, Pair<Rate, Rate> brackets, Rate tol, int maxIters) {

        int iter = 1;

        Money f3 = 0;
        Rate x3 = 0;
        Rate x1 = brackets.First;
        Rate x2 = brackets.Second;

        do {
            var f1 = func(x1);
            var f2 = func(x2);

            if (f1 == 0 && f2 == 0)
                return new AlgorithmResult<ApproximateResultKind, Rate>(ApproximateResultKind.NoSolutionWithinTolerance, x1);
            
            if (f1 * f2 > 0)
                throw new ArgumentException("x1 x2 values don't bracket a root");

            x3 = (x1 + x2) / 2;
            f3 = func(x3);

            if (f3 * f1 < 0)
                x2 = x3;
            else
                x1 = x3;

            iter++;

        } while (Math.Abs(x1 - x2)/2 > tol && f3 != 0 && iter < maxIters);

        if (f3 == 0)
            return new AlgorithmResult<ApproximateResultKind, Rate>(ApproximateResultKind.ExactSolution, x3);

        if (Math.Abs(x1 - x2) / 2 < tol)
            return new AlgorithmResult<ApproximateResultKind, Rate>(ApproximateResultKind.ApproximateSolution, x3);

        if (iter > maxIters)
            return new AlgorithmResult<ApproximateResultKind, Rate>(ApproximateResultKind.NoSolutionWithinTolerance, x3);

        throw new Exception("It should never get here");
    }

    public static AlgorithmResult<ApproximateResultKind, Rate> CalculateXIRR(IEnumerable<CashFlow> cfs, Rate tolerance, int maxIters) {

        var brackets = FindBrackets(CalculateXNPV, cfs);
        
        if (brackets.First == brackets.Second)
            return new AlgorithmResult<ApproximateResultKind, double>(ApproximateResultKind.NoSolutionWithinTolerance, brackets.First);

        return Bisection(r => CalculateXNPV(cfs,r), brackets, tolerance, maxIters);
    }
}

// TESTS

using Microsoft.VisualStudio.TestTools.UnitTesting;
using System.Collections.Generic;
using System;
using Rate = System.Double;

namespace TimeLineTest
{
    [TestClass()]
    public class AlgorithmsTest {

        IEnumerable<CashFlow> cfs = new CashFlow[] {
                new CashFlow(-10000, new DateTime(2008,1,1)),
                new CashFlow(2750, new DateTime(2008,3,1)),
                new CashFlow(4250, new DateTime(2008,10,30)),
                new CashFlow(3250, new DateTime(2009,2,15)),
                new CashFlow(2750, new DateTime(2009,4,1))
            };

        IEnumerable<CashFlow> bigcfs = new CashFlow[] {
                new CashFlow(-10, new DateTime(2000,1,1)),
                new CashFlow(10, new DateTime(2002,1,2)),
                new CashFlow(20, new DateTime(2003,1,3))
            };

        IEnumerable<CashFlow> negcfs = new CashFlow[] {
                new CashFlow(-10, new DateTime(2000,1,1)),
                new CashFlow(-1, new DateTime(2002,1,2)),
                new CashFlow(1, new DateTime(2003,1,3))
            };

        IEnumerable<CashFlow> samedaysamecfs = new CashFlow[] {
                new CashFlow(-10, new DateTime(2000,1,1)),
                new CashFlow(10, new DateTime(2000,1,1)),
            };

        IEnumerable<CashFlow> samedaydifferentcfs = new CashFlow[] {
                new CashFlow(-10, new DateTime(2000,1,1)),
                new CashFlow(100, new DateTime(2000,1,1)),
            };

        IEnumerable<CashFlow> bigratecfs = new CashFlow[] {
                new CashFlow(-10, new DateTime(2000,1,1)),
                new CashFlow(20, new DateTime(2000,5,30)),
            };

        IEnumerable<CashFlow> zeroRate = new CashFlow[] {
                new CashFlow(-10, new DateTime(2000,1,1)),
                new CashFlow(10, new DateTime(2003,1,1)),
                };

        IEnumerable<CashFlow> doubleNegative = new CashFlow[] {
                new CashFlow(-10000, new DateTime(2008,1,1)),
                new CashFlow(2750, new DateTime(2008,3,1)),
                new CashFlow(-4250, new DateTime(2008,10,30)),
                new CashFlow(3250, new DateTime(2009,2,15)),
                new CashFlow(2750, new DateTime(2009,4,1))
            };

        IEnumerable<CashFlow> badDoubleNegative = new CashFlow[] {
                new CashFlow(-10000, new DateTime(2008,1,1)),
                new CashFlow(2750, new DateTime(2008,3,1)),
                new CashFlow(-4250, new DateTime(2008,10,30)),
                new CashFlow(3250, new DateTime(2009,2,15)),
                new CashFlow(-2750, new DateTime(2009,4,1))
            };


        double r = 0.09;
        double tolerance = 0.0001;
        int maxIters = 100;

        private TestContext testContextInstance;

        public TestContext TestContext {
            get {
                return testContextInstance;
            }
            set {
                testContextInstance = value;
            }
        }

        [TestMethod()]
        public void CalculateXNPV() {

            Assert.AreEqual(2086.6476020315416570634272814M, Algorithms.CalculateXNPV(cfs, r));
            Assert.AreEqual(-10.148147600710372651326920258M, Algorithms.CalculateXNPV(negcfs, 0.5));
            Assert.AreEqual(4.9923725815954514810351876895M, Algorithms.CalculateXNPV(bigcfs, 0.3));
        }

        [TestMethod]
        public void FindBrackets() {

            var brackets = Algorithms.FindBrackets(Algorithms.CalculateXNPV, cfs);
            Assert.IsTrue(brackets.First < 0.3733 && brackets.Second > 0.3733);

            brackets = Algorithms.FindBrackets(Algorithms.CalculateXNPV, bigcfs);
            Assert.IsTrue(brackets.First < 0.5196 && brackets.Second > 0.5196);

            brackets = Algorithms.FindBrackets(Algorithms.CalculateXNPV, negcfs);
            Assert.IsTrue(brackets.First < -0.6059 && brackets.Second > -0.6059);
        }

        [TestMethod]
        public void XIRRTest() {

            var irr = Algorithms.CalculateXIRR(cfs, tolerance, maxIters);
            Assert.AreEqual(0.3733, irr.Value, 0.001);
            Assert.AreEqual(ApproximateResultKind.ApproximateSolution, irr.Kind);

            irr = Algorithms.CalculateXIRR(bigcfs, tolerance, maxIters);
            Assert.AreEqual(0.5196, irr.Value, 0.001);
            Assert.AreEqual(ApproximateResultKind.ApproximateSolution, irr.Kind);

            irr = Algorithms.CalculateXIRR(negcfs, tolerance, maxIters);
            Assert.AreEqual(-0.6059, irr.Value, 0.001);
            Assert.AreEqual(ApproximateResultKind.ApproximateSolution, irr.Kind);

            irr = Algorithms.CalculateXIRR(samedaysamecfs, tolerance, maxIters);
            Assert.AreEqual(ApproximateResultKind.NoSolutionWithinTolerance, irr.Kind);

            irr = Algorithms.CalculateXIRR(samedaydifferentcfs, tolerance, maxIters);
            Assert.AreEqual(ApproximateResultKind.NoSolutionWithinTolerance, irr.Kind);

            irr = Algorithms.CalculateXIRR(bigratecfs, tolerance, maxIters);
            Assert.AreEqual(4.40140, irr.Value, 0.001);
            Assert.AreEqual(ApproximateResultKind.ApproximateSolution, irr.Kind);

            irr = Algorithms.CalculateXIRR(zeroRate, tolerance, maxIters);
            Assert.AreEqual(0, irr.Value, 0.001);
            Assert.AreEqual(ApproximateResultKind.ApproximateSolution, irr.Kind);

            irr = Algorithms.CalculateXIRR(doubleNegative, tolerance, maxIters);
            Assert.AreEqual(-0.537055, irr.Value, 0.001);
            Assert.AreEqual(ApproximateResultKind.ApproximateSolution, irr.Kind);

            irr = Algorithms.CalculateXIRR(badDoubleNegative, tolerance, maxIters);
            Assert.AreEqual(ApproximateResultKind.NoSolutionWithinTolerance, irr.Kind);
        }
    }
}

Creating an immutable value object in C# - Part II - Making the class better

Other posts:

• Part I - Using a class
• Part III - Using a struct
• Part IV - A class with a special value

In the previous post I showed how to trivially implement a value object. The code works but it has several issues. Some are very simple, others are more interesting.

Let's take a look at them:

• State not explicitly read-only
• Asymmetry in the usage of Union and Intersection
• Small perf issue in the Union method

The first problem is that my use of automatic properties doesn't assure that the status of the object is immutable; I can still modify it from inside the class. The simple solution is to make the fields readonly and write the getters as in:

    private readonly DateTime start;
    private readonly DateTime end;

    public DateTime Start { get { return start; } }
    public DateTime End { get { return end; } }

The second issue is more subtle. Consider this code

        DateSpan d1 = new DateSpan(new DateTime(1, 1, 2000), new DateTime(1, 1, 2002));
        DateSpan d2 = null;

        DateSpan r1 = d1.Intersect(d2);
        DateSpan r2 = d2.Intersect(d1);

I would like things in my little 'algebra' to be symmetric. In this case I'd like: r1 == r2 == null. But this code throws in the last line as I'm trying to invoke a method on a null object.

The traditional solution to this problem is to make Union and Intersect to be static methods, but then you loose the magic of calling them as instance methods (i.e. it becomes hard to chain them together as in d1.Intersect(d2).Union(d3).Intersect(d4)).

Extension methods come to the rescue here as they allow you to create static methods, but to call them as if the were instance methods. The new code for Intersect looks like the following:

    public static DateSpan Intersect(this DateSpan one, DateSpan other) {

        if (one == null)
            return null;

        if (other == null)
            return null;

        if (one.IsOutside(other))
            return null;

        DateTime start = other.Start > one.Start ? other.Start : one.Start;
        DateTime end = other.End < one.End ? other.End : one.End;

        return new DateSpan(start, end);
    }

This workaround would not work if the extension method needs to access private state of the class. In that case you would need to create a static method on the DataSpan class and invoke it from the extension method. Slightly more convoluted, but still doable.

At a more philosophical level, the asymmetry issue happens here because I'm using something outside my domain of interest (the null value) to represent a special value inside my domain of interest. More on this as we talk about structs in upcoming posts.

The last point is a very small one. In the Union method I am creating a new object unnecessarily in the following line:

        if (other == null)
            return new DateSpan(Start, End);

I can obviously avoid it by just returning "this".

This post hints to several possible issues. Is it a good idea to use null to represent special values in my domain? What if I have more than one of them (i.e. positive/negative infinite)? Would using structs solve these problems?

We'll take a look at these options in upcoming posts. Attached is the modified code.

Creating an immutable value object in C# - Part I - Using a class

Other posts:

• Part II - Making the class better
• Part III - Using a struct
• Part IV - A class with a special value

Value objects are objects for which the identity is based on their state instead of their pointer in memory. For example, a numeric Complex class is, most of the time, a value object because you can treat two instances as the same if their state (real and img fields in this case) is the same. An immutable value object is a value object that cannot be changed. You cannot modify its state, you have to create new ones.

I'm using these guys more and more in my code for a number of reasons, both practical and philosophical. The practical ones revolve around the greater robustness of programming without side effects and the greater simplicity of parallelizing your code. The philosophical ones are more interesting (and subjective). When in my design process I spend the time to aggressively looking for these kinds of objects, the resulting design ends up cleaner. I especially like when I can define some sort of "close algebra" for these guys (i.e. a set of functions that operate over them and produces new ones, not unlike '+' and '-' for numbers).

This series describes how to create immutable value objects in C# and the design decisions involved. This is a summary of an email thread I had with Mads and Luke.

The concept I will use for this series is a DateSpan. As I define it, a DateSpan has a Start and an End date. You can ask for the DataSpan that represents the Union and Intersection of two DateSpans. The tests in the attached code better define the behavior of these operations.

Given that I never use structs in my code (I'm a minimalist language user), I'll start by using a class to represent it. We'll make this class better in part II and use a struct in part III. A first stab at it is as follows:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


public class DateSpan {

    public DateSpan(DateTime start, DateTime end) {

        if (end < start)
            throw new ArgumentException(start.ToString() + " doesn't come before " + end.ToString());
        Start = start;
        End = end;
    }

    public DateSpan Union(DateSpan other) {

        if (other == null)
            return new DateSpan(Start, End);

        if (IsOutside(other))
            return null;

        DateTime start = other.Start < Start ? other.Start : Start;
        DateTime end = other.End > End ? other.End : End;

        return new DateSpan(start, end);
    }

    public DateSpan Intersect(DateSpan other) {

        if (other == null)
            return null;

        if (IsOutside(other))
            return null;

        DateTime start = other.Start > Start ? other.Start : Start;
        DateTime end = other.End < End ? other.End : End;

        return new DateSpan(start, end);
    }

    private bool IsOutside(DateSpan other) {

        return other.Start > End || other.End < Start;
    }

    public DateTime Start { get; private set; }
    public DateTime End { get; private set; }

    #region Boilerplate Equals, ToString Implementation

    public override string ToString() {
        return string.Format("Start:{0} End:{1}", Start, End);
    }
    public override bool Equals(object obj) {

        if (obj == null) return false;
        if (this.GetType() != obj.GetType()) return false;

        DateSpan other = obj as DateSpan;

        return other.End == End && other.Start == Start;
    }

    public override int GetHashCode() {

        return Start.GetHashCode() | End.GetHashCode();
    }

    public static Boolean operator ==(DateSpan v1, DateSpan v2) {

        if ((object)v1 == null)
            if ((object)v2 == null)
                return true;
            else
                return false;

        return (v1.Equals(v2));
    }

    public static Boolean operator !=(DateSpan v1, DateSpan v2) {

        return !(v1 == v2);
    }

    #endregion
}

public static class TimeLineExtensions {

    public static bool IsSuperSet(this DateSpan span, DateSpan other) {

        if (span.Intersect(other) == other)
            return true;

        return false;
    }
}

Some things to notice in this code:

1. Defining a value object with a C# class involves overriding Equals, Hashcode, "==" and "!=". It is tricky, but usually boilerplate stuff, well