6
\$\begingroup\$

I've been improving some of my old sequence generators that worked with generics and lambdas in order to support binary operators for the specified T:

public abstract class Sequence<T> : IEnumerable<T>
{
    public IEnumerator<T> GetEnumerator() => Generate().GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    protected abstract IEnumerable<T> Generate();
}

public class GeometricSequence<T> : Sequence<T>
{
    private readonly T _first;
    private readonly double _ratio;
    private readonly Func<T, double, T> _multiply;

    public GeometricSequence(T first, double ratio, Func<T, double, T> multiply)
    {
        _first = first;
        _ratio = ratio;
        _multiply = multiply ?? throw new ArgumentNullException(nameof(multiply));
    }

    protected override IEnumerable<T> Generate()
    {
        var current = _first;
        yield return current;

        while (true)
        {
            yield return (current = _multiply(current, _ratio));
        }
    }
}

I never really liked them but now that I'm experimenting with expression trees I thought I rewrite these sequences too to get rid of the lambda parameter. This is not such a huge change but I think they are much easier to use now without having to specify the binary operation that could have been changed to something else even if an addition was expected. There was no way of controlling it. Here the operations are burn into each class.

I've added an interface and removed the Generate method. Concrete sequences must now only implement GetEnumerator.

public interface ISequence<T> : IEnumerable<T> { }

public abstract class Sequence<T> : ISequence<T>
{
    public abstract IEnumerator<T> GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

These are the sequences I currently have:

FibonacciSequence

public class FibonacciSequence<T> : Sequence<T>
{
    private readonly T _one;
    private readonly Func<T, T, T> _add;

    public FibonacciSequence(T one)
    {
        _one = one;
        var leftParameter = Expression.Parameter(typeof(T), "left");
        var rightParameter = Expression.Parameter(typeof(T), "right");
        var add = Expression.Add(leftParameter, rightParameter);
        _add = Expression.Lambda<Func<T, T, T>>(add, leftParameter, rightParameter).Compile();
    }

    public override IEnumerator<T> GetEnumerator()
    {
        yield return _one;
        yield return _one;

        var previous = _one;
        var current = _add(_one, _one);

        yield return current;

        while (true)
        {
            var newCurrent = _add(previous, current);
            yield return newCurrent;
            previous = current;
            current = newCurrent;
        }
    }
}

GeometricSequence

public class GeometricSequence<T> : Sequence<T>
{
    private readonly T _first;
    private readonly T _ratio;
    private readonly Func<T, T> _multiply;

    public GeometricSequence(T first, T ratio)
    {
        _first = first;
        _ratio = ratio;
        var leftParameter = Expression.Parameter(typeof(T), "left");
        var ratioConstant = Expression.Constant(ratio);
        var multiply = Expression.Multiply(leftParameter, ratioConstant);
        _multiply = Expression.Lambda<Func<T, T>>(multiply, leftParameter).Compile();
    }    

    public override IEnumerator<T> GetEnumerator()
    {
        var current = _first;
        yield return current;

        while (true)
        {
            yield return (current = _multiply(current));
        }
    }
}

LinearSequence

public class LinearSequence<T> : Sequence<T>
{
    private readonly T _first;
    private readonly T _constant;
    private readonly Func<T, T> _increment;

    public LinearSequence(T first, T step)
    {
        _first = first;
        _constant = step;
        var leftParameter = Expression.Parameter(typeof(T), "left");
        var stepConstant = Expression.Constant(step);
        var multiply = Expression.Add(leftParameter, stepConstant);
        _increment = Expression.Lambda<Func<T, T>>(multiply, leftParameter).Compile();
    }

    public override IEnumerator<T> GetEnumerator()
    {
        var current = _first;
        yield return current;

        while (true)
        {
            yield return (current = _increment(current));
        };
    }
}

HarmonicSequence

public class HarmonicSequence<T> : Sequence<T>
{
    private readonly LinearSequence<T> _linear;
    private readonly T _first;
    private readonly Func<T, T, T> _divide;

    public HarmonicSequence(LinearSequence<T> linear, T first)
    {
        _linear = linear;
        _first = first;
        var leftParameter = Expression.Parameter(typeof(T), "left");
        var rightParameter = Expression.Parameter(typeof(T), "right");
        var add = Expression.Divide(leftParameter, rightParameter);
        _divide = Expression.Lambda<Func<T, T, T>>(add, leftParameter, rightParameter).Compile();
    }
    
    public override IEnumerator<T> GetEnumerator()
    {
        return _linear.Select(divisor => _divide(_first, divisor)).GetEnumerator();
    }
}

For each sequence I have a static helper class to make the creation easier:

public static class FibonacciSequence
{
    public static FibonacciSequence<T> Create<T>(T one) => new FibonacciSequence<T>(one);
}

public static class GeometricSequence
{
    public static GeometricSequence<T> Create<T>(T first, T ratio) => new GeometricSequence<T>(first, ratio);
}

public static class LinearSequence
{
    public static LinearSequence<T> Create<T>(T first, T step) => new LinearSequence<T>(first, step);
}

public static class HarmonicSequence
{
    public static HarmonicSequence<T> Create<T>(LinearSequence<T> linear, T first) => new HarmonicSequence<T>(linear, first);
}

Example

This nicely works for all types that support the required operators like for example a fibonacci sequence with a time-span.

FibonacciSequence.Create(one: 1).Take(5).Dump();
FibonacciSequence.Create(one: TimeSpan.FromSeconds(1)).Take(5).Dump();
GeometricSequence.Create(first: 10, ratio: 0.5).Take(5).Dump();
LinearSequence.Create(first: 1, step: 3).Take(5).Dump();
HarmonicSequence.Create(LinearSequence.Create(first: 1, step: 3), first: 4).Take(5).Dump();
\$\endgroup\$
4
\$\begingroup\$

It's a shame that you have to use such a complicated mechanism because the language doesn't support strong enough type constraints. Given the limitations of the language, this looks like an elegant solution.


I find the naming slightly curious. Given GeometricSequence, I expect the linear one to be called ArithmeticSequence. Alternatively, LinearSequence would fit with ExponentialSequence.

Also, in HarmonicSequence I don't understand the name first. I would find that clearer if it were numerator, although I'm sure there are some who would argue that it should be dividend. Also, from a perspective of naturality, I would consider changing the order of the constructor parameters.


Three of the enumerators could be simplified a bit by rewriting to only have one yield return. E.g. Fibonacci could be just

    public override IEnumerator<T> GetEnumerator()
    {
        yield return _one;

        var previous = _one;
        var current = _one;

        while (true)
        {
            yield return current;

            var newCurrent = _add(previous, current);
            previous = current;
            current = newCurrent;
        }
    }

In my opinion the overhead of pre-calculating a value which won't be returned until the next invocation of GetNext() is a trivial cost to pay for the simplification.


HarmonicSequence<T> seems like a specialisation. Is the reason that you haven't made a version which takes a general ISequence<T> YAGNI? There are a number of options here:

  1. Leave it as is.
  2. Replace HarmonicSequence<T> with a class which takes scaled reciprocals of a general sequence, but keep the static HarmonicSequence.Create<T>(LinearSequence<T>, T) for the name alias convenience.
  3. Factor that general class out of HarmonicSequence<T> and make the latter a subclass whose only declared member is a constructor.
  4. As 2 but replace the static method with HarmonicSequence.Create<T>(T dividend, T divisorStart, T divisorStep) => new ReciprocalSequence<T>(dividend, LinearSequence.Create(divisorStart, divisorStep));. (There's also a 4b option of having both static utility methods).
  5. As 4 but make the return type of all the static creator methods be ISequence<T>.

When I started addressing this I had only thought of options 1 and 2, but then the return type change of point 5 occurred to me and I refactored the answer. From an abstract point of view I favour 5 as coding to the interface rather than the implementation, but your use cases may push you away from it.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Oh, I messed up the naming a little bit. Great suggestions, especially the 4th one ;-) Yeah, it's a pitty that there is no other way for performing binary operations on T but by using expressions but at least we have this workaround, better then nothing ;-) \$\endgroup\$ – t3chb0t Oct 5 '17 at 17:48
3
\$\begingroup\$

One other suggestion is that the expression you are building don't change based on the value you pass into the constructors (besides GeometricSequence which you still could make a parameter instead of a constant).

You could build your expression in the static constructor since it only changes by type. Or make a static Lazy field that builds the expressions and compiles them.

This way if you call it multiple times they can reuse the value functions instead of building the expression and compiling them each time.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Definitely! This would be the same principle as in my last question. I guess I was too focused on the sequences and loops and forgot that we already had this one once ;-) \$\endgroup\$ – t3chb0t Oct 5 '17 at 19:51
2
\$\begingroup\$

While I was following CharlesNRice's advice to make the expressions lazy, I realized that I actually create the same expressions multiple times so I moved them into a new utility class BinaryOperation that I can reuse everywhere and later probably in other projects too:

public delegate T BinaryFunc<T>(T left, T right);

public static class BinaryOperation<T>
{
    private delegate BinaryExpression BinaryExpressionFunc(Expression left, Expression right);

    private static readonly Lazy<BinaryFunc<T>> AddFunc = new Lazy<BinaryFunc<T>>(() => CreateBinaryFunc(Expression.Add));
    private static readonly Lazy<BinaryFunc<T>> SubtractFunc = new Lazy<BinaryFunc<T>>(() => CreateBinaryFunc(Expression.Subtract));
    private static readonly Lazy<BinaryFunc<T>> MultiplyFunc = new Lazy<BinaryFunc<T>>(() => CreateBinaryFunc(Expression.Multiply));
    private static readonly Lazy<BinaryFunc<T>> DivideFunc = new Lazy<BinaryFunc<T>>(() => CreateBinaryFunc(Expression.Divide));

    public static BinaryFunc<T> Add => AddFunc.Value;
    public static BinaryFunc<T> Subtract => SubtractFunc.Value;
    public static BinaryFunc<T> Multiply => MultiplyFunc.Value;
    public static BinaryFunc<T> Divide => DivideFunc.Value;

    private static BinaryFunc<T> CreateBinaryFunc(BinaryExpressionFunc binaryExpression)
    {
        var leftParameter = Expression.Parameter(typeof(T), "left");
        var rightParameter = Expression.Parameter(typeof(T), "right");
        var binaryOperation = binaryExpression(leftParameter, rightParameter);
        return Expression.Lambda<BinaryFunc<T>>(binaryOperation, leftParameter, rightParameter).Compile();
    }
}

An updated finbonacci-sequence (as well as the other ones) now only contain the core logic for creating the sequence:

public class FibonacciSequence<T> : Sequence<T>
{
    private readonly T _one;

    public FibonacciSequence(T one)
    {
        _one = one;            
    }

    public override IEnumerator<T> GetEnumerator()
    {
        yield return _one;

        var previous = _one;
        var current = _one;

        while (true)
        {
            yield return current;

            var newCurrent = BinaryOperation<T>.Add(previous, current);
            previous = current;
            current = newCurrent;
        }
    }
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ IMHO, the class BinaryOperation should provide methods which call the delegate internally instead of providing properties that return the delegate. \$\endgroup\$ – JanDotNet Oct 6 '17 at 9:25
  • \$\begingroup\$ I like the BinaryOperation class. Its a neat way to realize "generic arithmetic operation"! Great idea! \$\endgroup\$ – JanDotNet Oct 6 '17 at 9:27
  • \$\begingroup\$ @JanDotNet I think you're right... let's turn them into methods. \$\endgroup\$ – t3chb0t Oct 6 '17 at 9:36
1
\$\begingroup\$

Great Idea!

I really like that way to realize "generic arithmetic operations", even if it may result in run time errors when the type does not support the corresponding operation. However, its great that it works with all types that implement the corresponding operator - even with custom types :).

Performance

My first thought was: That must be slow compared with the static version - but it isn't. The static version is less then double so fast than the expression version. On my Computer, 10.000.000 add operations can be executed in a few 100 milli seconds. Therefore, the overhead can be ignored for the most use cases.

Code

Most points are already mentioned by other answers... just yet another:

Instead of having one class that provides the 'Create' method, I would prefer to have one class that provides all that methods and returning an IEnumerable:

public static class Sequence
{
    public static IEnumerable<T> Fibonacci<T>(T one) => new FibonacciSequence<T>(one);
    public static IEnumerable<T> Geometric<T>(T first, T ratio) => new GeometricSequence<T>(first, ratio);
    public static IEnumerable<T> Linear<T>(T first, T step) => new LinearSequence<T>(first, step);
    public static IEnumerable<T> Harmonic<T>(T dividend, T divisorStart, T divisorStep) => new HarmonicSequence<T>(LinearSequence.Create(divisorStart, divisorStep), dividend);
}

In productive code, the methods should be commented. Especially the prerequisite that T has to provide the corresponding operator ;).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Mhmm... maybe there is a way to check whether T implements the required operator? Let's see if reflection helps with that one too. Then I could also throw a better exception rather then waiting until an expression doesn't work. Thanks for testing for speed :-) \$\endgroup\$ – t3chb0t Oct 6 '17 at 9:53
  • \$\begingroup\$ Haha, this is not what I had expected ;-D \$\endgroup\$ – t3chb0t Oct 6 '17 at 9:55
  • \$\begingroup\$ Sure, it is possible to check it using reflection - but the error message is already meaningful: "The binary operator Add is not defined for the types 'Test' and 'Test'.". Probably it is possible to add custom checks to compile time using Roslyn ;) \$\endgroup\$ – JanDotNet Oct 6 '17 at 9:58
  • \$\begingroup\$ lol, the old try { int.Parse(str); return true; } catch { return false; } trick ;) \$\endgroup\$ – JanDotNet Oct 6 '17 at 10:01
  • 1
    \$\begingroup\$ How To Write a C# Analyzer and Code Fix - a nice exercise for anybody who wants to become familiar with the roslyn API ;D \$\endgroup\$ – JanDotNet Oct 6 '17 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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