2004-11-27-using-streams-to-generate-algorithmic-sequences.md

layout	title	date	categories	tags	status	type	published	meta	author
post	Using streams to generate algorithmic sequences	2004-11-27 02:52:09 -0800	Technology		publish	post	true	_wpas_done_all 1	login email display_name first_name last_name admin joeduffy@acm.org joeduffy

Lazy, functional streams go hand in hand with thunks. They enable lazy loading and calculation of algorithms, and can be particularly interesting due to the ease with which they compose. The examples I provide below make heavy use of new C# 2.0 features, such as anonymous delegates and iterators. Some will notice my undeniable influence by the Wizard book in the concepts presented here.

First, consider a new type Stream<T>:

public class Stream<T> : IEnumerable<T>
{
  //fields
  private List<T> memory = new List<T>();
  private Evaluator evaluator;
  private int count;

  public delegate Nullable<T> Evaluator();

  //ctors
  public Stream(Evaluator evaluator) : this(evaluator, -1)
  {
  }

  public Stream(Evaluator evaluator, int count)
  {
    this.evaluator = evaluator;
    this.count = count;
  }

  //properties
  public int Capacity
  {
    get
    {
      if (count == -1)
        return int.MaxValue;

      return count;
    }
  }

  public int Count
  {
    get
    {
      if (count == -1)
        return MemoryCount;

       return count;
    }
  }

  public int MemoryCount
  {
    get
    {
      return memory.Count;
    }
  }

  public T this[int index]
  {
    get
    {
      if (memory.Count <= index)
        for (int i = memory.Count; i <= index; i++)
          Memoize();

      return memory[index];
    }
  }

  //methods
  public IEnumerator<T> GetEnumerator()
  {
    int i = 0;

    while (i <= Capacity)
    {
      yield return this[i];
      i++;
    }
  }

  private void Memoize()
  {
    Nullable<T> n = evaluator();

    if (!n.HasValue)
      throw new ArgumentOutOfRangeException("No value for the specified index");

    memory.Add(n.Value);
  }
}

This takes an Evaluator delegate, a no-args method which returns an instance of Nullable<T>. I have chosen to implement a memoized stream, to make re-accessing previously computed indexes possible. This simply means that calculated values are "remembered" once they have been generated. My implementation actually wouldn't work without memoization since it uses state variables to track its computation. This will lazily load up to the index which is requested.

This can be used, for example, to calculate numbers in the Fibonacci series.

Stream<long> CreateFibStream()
{
  long i1 = 1;
  long i2 = 1;

  return new Stream<long>(delegate
  {
    long t = i1;
    i1 = i2;
    i2 = t + i2;

    return t * 4;
  });
}

This code can be used to calculate the first 10 numbers in the Fibonacci series as follows:

Stream<long> fib = CreateFibStream();

for (int i = 0; i < 10; i++)
  Console.WriteLine(fib[i]);

The output of this program is as follows:

1 1 2 3 5 8 13 21 34 55

Notice that, because of the indexer, you can request, say, the 15th Fibonacci number directly:

Console.WriteLine(fib[14]);

This prints out the number 610.

Because streams are easily composable, I've easily created a few standard factory methods which construct an augmented stream. These simply wrap an existing stream and lazily change the output as it is requested. For example, Amplifier<T> will amplify the numbers generated by a target stream by a constant number as they are retrieved.

public static Stream<U> Transform<T, U>(Converter<T, U> c, Stream<T> s)
{
  IEnumerator<T> e = s.GetEnumerator();

  return new Stream<U>(delegate
  {
    e.MoveNext();

    return c(e.Current);
  });
}

public static Stream<double> Amplifier<T>(Stream<T> s, double y)
{
  return Transform<T, double>(
    new Converter<T, double>(delegate(T x) { return Convert.ToDouble(x) * y; }),
    s);
}

For instance, we can use this in calculation of pi as follows:

Stream<double> CreatePiStream()
{
  double n = 1.0;
  double last = 0.0;

  bool add = true;

  return StreamFactory.Amplifier<double>(
    new Stream<double>(delegate
    {
      double d = 1 / n;

      if (!add)
        d *= -1;

      add = !add;

      last += d;
      n += 2;

      return last;
    }),
    4.0);
}

The first 15 iterations of this produce these numbers:

4 2.66666666666667 3.46666666666667 2.8952380952381 3.33968253968254 2.97604617604618 3.28373848373848 3.01707181707182 3.25236593471888 3.0418396189294 3.23231580940559 3.05840276592733 3.21840276592733 3.07025461777919 3.20818565226194

The 100th number is 3.13159290355855. Notice how slowly this method converges towards the real pi.

Another useful standard augmentation is a so-called Euler transform, which acts as an accelerator causing our pi generator to converge more rapidly. The technique used is to calculate any number S as Sn+1 - ((Sn+1 - Sn)2)/(Sn-1 - 2Sn + Sn+1), where n is an index into the sequence of values.

public static Stream<double> EulerTransform<T>(Stream<T> s)
{
  int i = 0;

  return new Stream<double>(delegate
  {
    double s0 = Convert.ToDouble(s[i++]);
    double s1 = Convert.ToDouble(s[i++]);
    double s2 = Convert.ToDouble(s[i++]);

    return s2 - (Math.Pow(s2 - s1, 2) / (s0 - (2 * s1) + s2));
  });
}

For example, consider this method of accelerating our generation of pi:

Stream<double> pis = StreamFactory.EulerTransform<double>(CreatePiStream());

for (int i = 0; i < 15; i++)
  Console.WriteLine(pis[i]);

The output of the first 15 iterations is as follows - notice that it converges towards pi much more rapidly than the previous example:

3.16666666666667 3.13968253968254 3.14207181707182 3.1414067184965 3.14168318920776 3.14154198599778 3.14162380666784 3.14157215448297 3.14160685134755 3.14158241824775 3.14160027369869 3.14158682862116 3.14159720571187 3.14158902894078 3.14159558652131

And, lastly, the 100th number using the Euler accelerated sequence is 3.14159264423745. Interestingly, we can do accelerate an accelerated sequence, and so on, for example as in:

Stream<double> pis = StreamFactory.EulerTransform<double>(
  StreamFactory.EulerTransform<double>(
    StreamFactory.EulerTransform<double>(
      CreatePiStream())));

Indexing into the 100th number here is 3.14159265358979, the same exact number returned by the Math.PI constant.