Computed array values in C# - reactive programming

Question

Example 1

As we know there's the concept of computed columns in databases where a column is computed based on adjacent columns' values.

The problem is that computed columns can't relate to other rows than current.

Example 2

Then we have spreadsheets (ie. Excel) where a cell can have a formula. This is similar to computed column, but more powerful. A formula can be related to any cell (or set of them) in the spreadsheet and not just current row/column as in RDB.

The problem

The concept of computed (or auto-updated values) is great but how can I do something similar in a set of values/objects in C#?

I would like to create a list (or array) of values where each of them is related to some other (or set of) value in the same list? It's like spreadsheet cell values... Change a value and related ones change along (and the whole related subtree values as well).

Is there a concept like that in C#?

How am I about to do this in the most clever way? I know I could have a LinkedList of objects where object's properties' values would relate to other objects in the same list and get evaluated whenever value gets accessed (evaluation on demand). This may mean that several (all ancestor nodes) get evaluated along the way. Is there a better way that would work more like spreadsheet cells where they get evaluated first and then accessed individually (propagated evaluation)?

This should of course be applicable to multidimensional arrays as well.

Answer 1

This concept is called Reactive Programming. .NET has something called Reactive Extensions that would allow you to achieve what you have described. Specifically you need to use something called Behavior

Answer 2

You could create an object with an indexer property which would contain your computation:

class Foo {
    public int this[int index] {
        get {
            return index*2; //Your computation here
        }
    }
}

or

class Foo {
    public int this[int row,int col] {
        get {
            return row*col; //Your computation here
        }
    }
}

Alternatively, if you want to use a linked list or somesuch, you could store "Cell" objects in the list structure and have a property or method on those "Cell" objects to perform the calculations:

class Cell {
    private int _row;
    private int _col;

    public Cell(int row,int col) {
        _row = row;
        _col = col;
    }

    public int Value {
        get {
            return _row * _col;
        }
    }
}

Answer 3

You can create your own array class that takes functions instead of values:

class ComputedArray<T>
{
    private Func<T>[] _array;

    public T this[int index] { get { return _array[index]( ); } }

    public void Set(int index, Func<T> func)
    {
        _array[index] = func;
    }

    public ComputedArray( int size )
    {
        _array = new Func<T>[size];
    }
}

Now you can store values using lambda expressions:

ComputedArray<int> ar = new ComputedArray<int>( 2 );
ar.Set( 0, ( ) => 2 );
ar.Set( 1, ( ) => ar[0]*2 );
Console.WriteLine( ar[0] );
Console.WriteLine( ar[1] );

Answer 4

This is perfect for OO languages as the way references work. At an abstract level I would handle this as such:

Create an abstract class, Expression, that will be the base type for all values in our program. Something like:

public abstract class Expression
{
    List<Expression> linkedExpressions;
    protected Expression lhs; // left hand side, right hand side
    protected Expression rhs;

    protected Expression(Expression x, Expression y)
    {
        List<Expression> linkedExpressions = new List<Expression>();
        lhs = x;
        rhs = y;
        // let the expressions know that they have a expression dependant on them
        lhs.NotifyExpressionLinked(this); 
        rhs.NotifyExpressionLinked(this);
    }

    private void NotifyExpressionLinked(Expression e)
    {
        if (e != null)
        {
            linkedExpressions.Add(e);
        }
    }

    private void NotifyExpressionUnlinked(Expression e)
    {
        if (linkedExpressions.Contains(e)
        {
            linkedExpressions.Remove(e);
        }
    }

    // this method will notify all subscribed expressions that
    // one of the values they are dependant on has changed
    private void NotifyExpressionChanged()
    {
        if (linkedExpressions.Count != 0) // if we're not a leaf node
        {
            foreach (Expression e in linkedExpressions)
            {
                e.NotifyExpressionChanged();
            }
        }
        else Evaluate() 
        // once we're at a point where there are no dependant expressions 
        // to notify we can start evaluating
    }

    // if we only want to update the lhs, y will be null, and vice versa
    public sealed void UpdateValues(Expression x, Expression y)
    {
        if (x != null)
        {
            lhs.NotifyExpressionUnlinked(this);
            x.NotifyExpressionLinked(this);
            lhs = x;
        }

        if (y != null)
        {
            rhs.NotifyExpressionUnlinked(this);
            y.NotifyExpressionLinked(this);
            rhs = y;
        }

        NotifyExpressionChanged();
    }

    public virtual float Evaluate()
    {
        throw new NotImplementedException(); // we expect child classes to implement this
    }
}

Create a class for each of the types of expressions we will need. At the very bottom you will have a LiteralExpression, which is just a number:

public class LiteralExpression : Expression
{
    private float value;

    public LiteralExpression(float x)
        : base(null, null) { } // should not have any linked expressions

    public override float Evaluate()
    {
        return value;
    }
}

One thing to note about this class - because of the way it works, UpdateValue() shouldn't be used on it. Instead, just create a new LiteralExpression to replace it.

Then, you need to build child classes for all expressions you will want (for example, here is addition):

public class AdditionExpression : Expression
{
    public AdditionExpression(Expression x, Expression y)
        : base(x, y) { };

    public override float Evaluate()
    {
        return lhs.Evaluate() + rhs.Evaluate();
    }
}

Not how this is all the code we have to write for each expression - all the heavy lifting is handled by the abstract class. There are a few design flaws in this program - it won't detect circular references, and it won't stop you from passing null values to expressions (which in the case of LiteralExpression is required), but those problems shouldn't be too hard to fix.

Then, all that needs to be done is to implement all of the child classes that inherit from expression.

There may be better methods to doing this, but from an OO viewpoint this is a nice example of making an generic abstract class that implements common behaviours and having a lot of small, specific implementations for each 'flavour' of that class.