Monday, March 6, 2017

Encapsulation Two Ways

This is the third post in a series on my journey to learn more about the F# language. I'm choosing some coding exercises from Structure and Interpretation of Computer Programs and writing each one in both C# and F#. You can follow my progress here and see all my code on github.

This time, we're using the half-interval method to find roots of equations, i.e., a value x where f(x) = 0 for a continuous function f (Section 1.3.3). The idea is that, given two points a and b where f(a) < 0 < f(b), then the value x must lie somewhere between a and b. So we check the value of f at the midpoint of the interval. If it is zero, then we've found the root. If it's negative, then the root must be in the right half of the interval. If it's positive, the root's in the left half. We continue choosing smaller and smaller half-intervals until we hit a root or we decide the interval is small enough.

As usual, we start the C# version with a test. The test is split into an abstract class and a concrete class, as before, so we can re-use it later for the F# version.

public abstract class HalfIntervalTest { [Test] public void MidpointIsRoot() { Assert.AreEqual(0.0, FindSineRoot(-0.5, 0.5)); } protected abstract double FindSineRoot(double left, double right); } [TestFixture] public class HalfIntervalCSharpTest: HalfIntervalTest { protected override double FindSineRoot(double left, double right) { return HalfIntervalMethod.FindRoot(Math.Sin, left, right); } }
We're using the sine function and the first test has the root at the midpoint of the initial interval.

But we have a code smell, before we've even written any production code. There's a static method FindRoot with three parameters. For a more object-oriented style, let's encapsulate the interval in its own class, and the function in the HalfIntervalMethod class.

protected override double FindSineRoot(double left, double right) { return new HalfIntervalMethod(Math.Sin).FindRoot(new Interval(left, right)); }
This isn't a series on TDD, so I won't show all the steps to reach the final C# implementation. Here's the tests:

public abstract class HalfIntervalTest { [Test] public void MidpointIsRoot() { Assert.AreEqual(0.0, FindSineRoot(-0.5, 0.5)); } [Test] public void RootIsFoundWithPositiveValueAtLeft() { Assert.AreEqual(Math.PI, FindSineRoot(Math.PI - 0.1, Math.PI + 0.5), 1E-10); } [Test] public void RootIsFoundWithPositiveValueAtRight() { Assert.AreEqual(Math.PI, FindSineRoot(Math.PI + 0.5, Math.PI - 0.1), 1E-10); } [Test] public void ValuesWithSameSignThrowsException() { Assert.Throws(() => FindSineRoot(Math.PI/2.0, Math.PI/2.0 + 1.0)); } protected abstract double FindSineRoot(double left, double right); }
The HalfIntervalMethod class checks that the function values at the interval end points do have opposite signs. We swap the interval if needed so that we have ascending values. Then we iterate choosing the appropriate half-interval until we hit a root or the interval is small enough.

public class HalfIntervalMethod { public HalfIntervalMethod(Func<double, double> function) { this.function = function; } public double FindRoot(Interval interval) { var values = interval.Map(function); if (!values.CrossesZero) { throw new ArgumentException("Values are not opposite signs."); } return FindRootByHalfIntervals(values.Ascending ? interval.Swap : interval); } double FindRootByHalfIntervals(Interval interval) { while (interval.Size >= 1E-10) { var value = function(interval.MidPoint); if (value == 0.0) break; interval = value > 0.0 ? interval.RightHalf : interval.LeftHalf; } return interval.MidPoint; } readonly Func<double, double> function; }
The Interval class encapsulates the endpoints of the interval and has a collection of useful methods. This is a common outcome when using TDD with an object-oriented language. We start by encapsulating some primitive data types and we find a bunch of methods that are attracted to the data. It creates a good abstraction that makes the HalfIntervalMethod code very readable.

public struct Interval { public Interval(double start, double finish) { this.start = start; this.finish = finish; } public double MidPoint => (start + finish) / 2.0; public double Size => Math.Abs(finish - start); public bool CrossesZero => Math.Sign(start) == -Math.Sign(finish) && Math.Sign(start) != 0; public bool Ascending => start < finish; public Interval LeftHalf => new Interval(start, MidPoint); public Interval RightHalf => new Interval(MidPoint, finish); public Interval Swap => new Interval(finish, start); public Interval Map(Func function) => new Interval(function(start), function(finish)); readonly double start; readonly double finish; }
Now the F# version. Before we start, there's a couple of F# practices that I've learned since the last post. First, function names are started with lower case by convention. Second, we can nest functions within other functions to control their visibility, rather than using private modifiers. So here's what my squareRoot function from last time looks like now.

let squareRoot input = let rec squareRootFromGuess guess = let newGuess = (guess + input / guess) / 2.0 let goodEnough = abs((guess - newGuess) / guess) < 0.000001 if goodEnough then newGuess else squareRootFromGuess newGuess match input with | 0.0 -> 0.0 | input when input < 0.0 -> raise (new System.ArgumentOutOfRangeException()) | input -> squareRootFromGuess 1.0
Back to half intervals. We can write an Interval type in F# that's the same as the C# version: with encapsulated data and member functions. But the tutorials I've been reading suggest using data types with independent functions to fully exploit the functional capabilites of F#. So here goes:

module Interval = type IntervalType = {Start: float; Finish: float} let create start finish = {Start = start; Finish = finish} let midpoint interval = (interval.Start + interval.Finish) / 2.0 let size interval = abs(interval.Finish - interval.Start) let crossesZero interval = sign(interval.Start) = -sign(interval.Finish) && sign(interval.Start) <> 0 let ascending interval = interval.Start < interval.Finish let leftHalf interval = create interval.Start (midpoint interval) let rightHalf interval = create (midpoint interval) interval.Finish let swap interval = create interval.Finish interval.Start let map aFunction interval = create (aFunction interval.Start) (aFunction interval.Finish)
Now let's use this in the half-interval method test class. The Interval module has a constructor method that we can call from C#. In the F# code I've read so far, this seems to be a common pattern.

[TestFixture] public class HalfIntervalFSharpTest: HalfIntervalTest { protected override double FindSineRoot(double left, double right) { return FSharp.HalfIntervalMethod.findSineRoot(FSharp.Interval.create(left, right)); } }
Here's the F# implementation that passes the tests:

open Interval module HalfIntervalMethod = let findRoot aFunction interval = let rec findRootByHalfInterval interval = if size interval < 1E-10 then midpoint interval else match aFunction (midpoint interval) with | 0.0 -> midpoint interval | value -> findRootByHalfInterval ((if value < 0.0 then rightHalf else leftHalf) interval) let values = map aFunction interval if crossesZero values then findRootByHalfInterval (if ascending values then interval else swap interval) else raise (new System.ArgumentException("Values are not opposite signs.")) let findSineRoot interval = findRoot sin interval
A few final thoughts on the F# version compared to the C# version. We're using tail recursion again to iterate to the answer. Notice how we can select the right and left intervals by choosing a function to apply to the current interval: (if value < 0.0 then rightHalf else leftHalf) interval. This is the first little example of the power of functions as first-class objects.

In C#, we use a class to compose data: an interval is composed of two numbers. The class also encapsulates both data and methods. Public class members can be accessed from outside the class. Inside the class, private data and methods can be accessed from any class methods. In F#, we've used two different mechanisms for data composition and encapsulation. A type is used to compose data but we've used function nesting to control encapsulation. A nested function can only be used from within the enclosing function.

Next time: functions that return functions.

No comments:

Post a Comment