When working through the project euler problems in visual basic we very quickly run into a limitation of the language, visual basic does not support iterators. Unfortunately, iterators probably won’t make it into the next version of vb either. So time to get our hands dirty and roll our own iterator support.
Problem 2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million
Using the C# yield statement to generate the Fibonacci sequence
The first step to solving the problem is writing a function to generate a Fibonacci sequence. This is trivial in C#.
IEnumerable<int> Fibs()
{
int n1 = 0;
int n2 = 1;
while (true)
{
int n3 = n1 + n2;
yield return n3;
n1 = n2;
n2 = n3;
}
}
Basically the yield statement returns a new number in the sequence each time Fibs function is iterated over. A much more in depth explanation of what the yield statement is doing can be found in wes dyer’s blog entry.
http://blogs.msdn.com/wesdyer/archive/2007/03/23/all-about-iterators.aspx
Writing our own VB class to do the work of the C# compiler.
If your read the blog entry above then you know the c# compiler generates a class in place of the simple function. This class implements both IEnumerable(of T) and IEnumerator(of T) to allow for the results of the function to be iterated over. Let’s build this class in VB.
Public Class FibsIterator
Implements IEnumerable(Of Integer)
Implements IEnumerator(Of Integer)
Private a = 0
Private b = 1
Public Sub New()
End Sub
Private Function Calculate() As Boolean
b = a + b
a = b – a
Return True
End Function
Public Function GetEnumerator() As System.Collections.Generic.IEnumerator(Of Integer) Implements System.Collections.Generic.IEnumerable(Of Integer).GetEnumerator
Return Me
End Function
Public Function GetEnumerator1() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
Return Me
End Function
Public ReadOnly Property Current() As Integer Implements System.Collections.Generic.IEnumerator(Of Integer).Current
Get
Return b
End Get
End Property
Public ReadOnly Property Current1() As Object Implements System.Collections.IEnumerator.Current
Get
Return b
End Get
End Property
Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
Return Calculate()
End Function
Public Sub Reset() Implements System.Collections.IEnumerator.Reset
Throw New NotImplementedException()
End Sub
Private disposedValue As Boolean = False ‘ To detect redundant calls
‘ IDisposable
Protected Overridable Sub Dispose(ByVal disposing As Boolean)
If Not Me.disposedValue Then
If disposing Then
‘ TODO: free other state (managed objects).
End If
‘ TODO: free your own state (unmanaged objects).
‘ TODO: set large fields to null.
End If
Me.disposedValue = True
End Sub
#Region ” IDisposable Support “
‘ This code added by Visual Basic to correctly implement the disposable pattern.
Public Sub Dispose() Implements IDisposable.Dispose
‘ Do not change this code. Put cleanup code in Dispose(ByVal disposing As Boolean) above.
Dispose(True)
GC.SuppressFinalize(Me)
End Sub
#End Region
End Class
And now we can write our workflow/monad/Linq expression to solve the problem.
Dim result = New FibsIterator().TakeWhile(Function(x) x < 4000000).Where(Function(x) x Mod 2 = 0).Sum()
Console.WriteLine(result)
Extract superclass into a reusable generator
Having to write a class that implements IEnumerator(of T) and IEnumerable(of T) every time is both a pain in the butt and hard to read. Lets factor out what we’ll always need into a superclass.
Public MustInherit Class Generator(Of T)
Implements IEnumerable(Of T)
Implements IEnumerator(Of T)
Private mCurrent As T
Public Sub New()
End Sub
Protected MustOverride Function Generate() As T
Public Function GetEnumerator() As System.Collections.Generic.IEnumerator(Of T) Implements System.Collections.Generic.IEnumerable(Of T).GetEnumerator
Return Me
End Function
Public Function GetEnumerator1() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
Return Me
End Function
Public ReadOnly Property Current() As T Implements System.Collections.Generic.IEnumerator(Of T).Current
Get
Return mCurrent
End Get
End Property
Public ReadOnly Property Current1() As Object Implements System.Collections.IEnumerator.Current
Get
Return mCurrent
End Get
End Property
Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext
mCurrent = Generate()
Return True
End Function
Public Sub Reset() Implements System.Collections.IEnumerator.Reset
Throw New NotImplementedException()
End Sub
Private disposedValue As Boolean = False ‘ To detect redundant calls
‘ IDisposable
Protected Overridable Sub Dispose(ByVal disposing As Boolean)
If Not Me.disposedValue Then
If disposing Then
‘ TODO: free other state (managed objects).
End If
‘ TODO: free your own state (unmanaged objects).
‘ TODO: set large fields to null.
End If
Me.disposedValue = True
End Sub
#Region ” IDisposable Support “
‘ This code added by Visual Basic to correctly implement the disposable pattern.
Public Sub Dispose() Implements IDisposable.Dispose
‘ Do not change this code. Put cleanup code in Dispose(ByVal disposing As Boolean) above.
Dispose(True)
GC.SuppressFinalize(Me)
End Sub
#End Region
End Class
Now all we have to do is inherit from this superclass and write out generator function.
Public Class Fibs
Inherits Generator(Of Integer)
Private a = 0
Private b = 1
Protected Overrides Function Generate() As Integer
b = a + b
a = b – a
Return b
End Function
End Class
Much easier to read and works just the same way.
Dim result = New Fibs ().TakeWhile(Function(x) x < 4000000).Where(Function(x) x Mod 2 = 0).Sum()
Console.WriteLine(result)
Voila, problem solved and although we have to use a class instead of a function it’s still pretty easy to read and understand. We’ll be using this generator class a lot to solve the Euler problems. So we’ve built ourselves a handy number generator, but can we use this method to add our own Linq operators? We’ll take a look at this next time.
[...] « Simulate the Yield Statement in Visual Basic Part 1 [...]