Which is quicker? Iteration or Recursion?

For a simple problem, see Project Euler #1, I thought it would an interesting exercise to code alternative implementations and time them. You see, when I originally solved the problem way back in the mists of time (well, perhaps not that long ago as it was done using F# 1.9.9 as far as I recall) I was using PE as a tool to teach myself F#. Nowadays I'm comfortable with F# so I thought I would return to PE and explore a little more. So, follows is some F# code which solves problem #1. Spoiler alert! If you haven't already solved it and intend to do so, stop reading now!

 let first = fun (a,b) -> a
  
 let second = fun (a,b) -> b
  
 let upperLimit = 1000 // ie we want to act upon the integers which are less than 1000
  
 let maxLoops = 25000 // an arbitrary large integer - the number of times to repeat the core calculation in a single (timed) execution
  
 let howMany = 15 // ie the number of times we want to perform the calculation in order to find the average calculation time
  
 let st = new System.Diagnostics.Stopwatch()
  
 let Impl1a = fun () ->
  
   let whichImpl = "Iteration"
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let mutable sum = 0    
  
     for i = 1 to upperLimit-1 do
  
       sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl1b = fun () ->
  
   let whichImpl = "Iteration with mutable creation outside loop"
  
   st.Restart()
  
   let mutable sum = 0    
  
   for loop = 1 to maxLoops do
  
     sum <- 0
  
     for i = 1 to upperLimit-1 do
  
       sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl1c = fun () ->
  
   let whichImpl = "Reverse iteration"
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let mutable sum = 0    
  
     for i = upperLimit-1 downto 1 do
  
       sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl1d = fun () ->
  
   let whichImpl = "Reverse iteration with mutable creation outside loop"
  
   st.Restart()
  
   let mutable sum = 0    
  
   for loop = 1 to maxLoops do
  
     sum <- 0
  
     for i = upperLimit-1 downto 1 do
  
       sum <- if (i%3 = 0 || i%5 = 0) then sum + i else sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl2a = fun () ->
  
   let whichImpl = "Iteration using List higher-order fns"
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = [1..upperLimit-1] |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl2b = fun () ->
  
   let whichImpl = "Iteration using List higher-order fns with pre-compiled integer range"
  
   st.Restart()
  
   let input = [1..upperLimit-1]
  
   for loop = 1 to maxLoops do
  
     let sum = input |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl2c = fun () ->
  
   let whichImpl = "Iteration using Seq higher-order fns"
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = seq {1 .. upperLimit-1} |> Seq.filter (fun i -> i%3=0 || i%5=0) |> Seq.fold (fun state i -> i+state) 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl2d = fun () ->
  
   let whichImpl = "Reverse Iteration using List higher-order fns"
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = [upperLimit-1 .. -1 .. 1] |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl2e = fun () ->
  
   let whichImpl = "Reverse Iteration using List higher-order fns with pre-compiled integer range"
  
   st.Restart()
  
   let input = [upperLimit-1 .. -1 .. 1]
  
   for loop = 1 to maxLoops do
  
     let sum = input |> List.filter (fun i -> i%3=0 || i%5=0) |> List.fold (fun state i -> i+state) 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl2f = fun () ->
  
   let whichImpl = "Reverse Iteration using Seq higher-order fns"
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = seq {upperLimit-1 .. -1 .. 1} |> Seq.filter (fun i -> i%3=0 || i%5=0) |> Seq.fold (fun state i -> i+state) 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl3a = fun () ->
  
   let whichImpl = "Recursion with Accumulator"
  
   let rec Impl3p counter acc =
  
     if counter=upperLimit then
  
       acc
  
     else if counter%3=0 || counter%5=0 then
  
       Impl3p (counter+1) (acc+counter)
  
     else
  
       Impl3p (counter+1) acc
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = Impl3p 1 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl3b = fun () ->
  
   let whichImpl = "Recursion"
  
   let rec Impl3p counter =
  
     if counter=upperLimit then
  
       0
  
     else if counter%3=0 || counter%5=0 then
  
       counter + Impl3p (counter+1)
  
     else
  
       Impl3p (counter+1)
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = Impl3p 1
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl4a = fun () ->
  
   let whichImpl = "Iteration incrementing a pair of counters"
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let mutable sum = 0
  
     let mutable loopDiv3,loopDiv5 = 0,0
  
     while loopDiv3<upperLimit do // because loopDiv3 increases slower than loopDiv5
  
       loopDiv3 <- loopDiv3 + 3
  
       loopDiv5 <- loopDiv5 + 5      
  
       // if we haven't already added it in loopDiv5 ...
  
       sum <- sum + (if loopDiv3 < upperLimit then (if loopDiv3 % 5 <> 0 then loopDiv3 else 0) else 0)
  
       sum <- sum + (if loopDiv5 < upperLimit then loopDiv5 else 0)
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl4b = fun () ->
  
   let whichImpl = "Recursion using a pair of counters"
  
   let rec Impl4p counterDiv3 counterDiv5 =
  
     if counterDiv3>=upperLimit then
  
       0
  
     else 
  
       (if counterDiv3 % 5 <> 0 then counterDiv3 else 0) + (if counterDiv5 < upperLimit then counterDiv5 else 0) + Impl4p (counterDiv3+3) (counterDiv5+5)
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = Impl4p 0 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl
  
 let Impl4c = fun () ->
  
   let whichImpl = "Recursion with Accumulator using a pair of counters"
  
   let rec Impl4p counterDiv3 counterDiv5 acc =
  
     if counterDiv3>=upperLimit then
  
       acc
  
     else 
  
       Impl4p (counterDiv3+3) (counterDiv5+5) ((if counterDiv3 % 5 <> 0 then counterDiv3 else 0) + (if counterDiv5 < upperLimit then counterDiv5 else 0) + acc)
  
   st.Restart()
  
   for loop = 1 to maxLoops do
  
     let sum = Impl4p 0 0 0
  
     ignore sum
  
   st.Stop()
  
   st.ElapsedMilliseconds, whichImpl  

 let run (whichImpl : unit -> int64 * string) = 
  
   let res = [ for count = 1 to howMany do yield whichImpl() ]
  
   let name = res |> List.head |> second
  
   let elapsed = res |> List.map first
  
   elapsed |> List.iter (fun elem -> printfn "%s : %i iterations took %i milliseconds" name maxLoops elem)
  
   let avg = float (elapsed |> List.fold (fun state i -> state+i) 0L) / float (List.length elapsed)
  
   name, avg
  
 let implementations = [ Impl1a; Impl1b; Impl1c; Impl1d; Impl2a; Impl2b; Impl2c; Impl2d; Impl2e; Impl2f; Impl3a; Impl3b; Impl4a; Impl4b; Impl4c ]
  
 implementations |> List.map (fun impl -> run impl)
  

Well, well! How interesting! Using F# interactive, these are the results obtained from my test run:

  [("Iteration", 252.8);
  
   ("Iteration with mutable creation outside loop", 255.0666667);
  
   ("Reverse iteration", 225.0);
  
   ("Reverse iteration with mutable creation outside loop", 236.1333333);
  
   ("Iteration using List higher-order fns", 3509.933333);
  
   ("Iteration using List higher-order fns with pre-compiled integer range", 386.6);
  
   ("Iteration using Seq higher-order fns", 4848.933333);
  
   ("Reverse Iteration using List higher-order fns", 3679.466667);
  
   ("Reverse Iteration using List higher-order fns with pre-compiled integer range", 396.7333333);
  
   ("Reverse Iteration using Seq higher-order fns", 4883.266667);
  
   ("Recursion", 242.4);
  
   ("Recursion with Accumulator", 231.9333333);
  
   ("Iteration incrementing a pair of counters", 48.6);
  
   ("Recursion using a pair of counters", 90.4);
  
   ("Recursion with Accumulator using a pair of counters", 53.26666667)]  

Monads ... hang on, I'm thinking

So I'm thinking about monads and the shockingly non-functional try...catch...finally in C# and I what I want to do is something like this.

var results = Try(()=>doSomething()).Catch(()=>catchIt()).
     Catch(()=>YouveGotABiggerProblemNow()).Finally(()=>TidyUp());

I think that reads reasonably well and is a close approximation to a monad. The question in my mind at the moment is whether it will work as an extension to my already-created Exception Monad (MException if you're following me on Google Code) or whether I will need to create a new monad class, which would be annoying. In the latter case I would probably require an adapter, but that's okay because what do you think Bind() is supposed to be? LoL

LINQ group by

This one caught me out a couple of days ago. Recall to mind the good old IEnumerable . It's a good idea to act and code as if they can be traversed once only. As it happened we had some test code which iterated through two streams. Foolishly and without applying enough thought we wrote some linq which joined the two datastreams (ok so far) and then grouped them. Var a = from b in Bs From c in Cs Select new { b , c}; Var aa = from j in a group j by j.c.name; Oh dear. The group caused the Cs to be looped through one complete traversal for each element in Bs! Not good, because the stream was not restartable and so it went horribly wrong. The temporary solution is to turn Bs and Cs into lists and take the cross-product on the chin for now.

Countdown - solver in C#

Countdown: presented with six integers they should be combined using the four arithmetic operators +, -, * and / to approach the target as closely as possible. Example code:

using System;
using System.Linq;
using System.Collections.Generic;
using NUnit.Framework;

namespace Test.Unit.Utils
{
    class NonIntegralDivisionResult:Exception {}

    [TestFixture]
    class Countdown
    {
        [Test]
        public static void CountdownTest1()
        {
            var operators = new Dictionary<string, Func<int, int, int>>
                            {
                                {"+", (a, b) => a + b},
                                {"-", (a, b) => a - b},
                                {"*", (a, b) => a*b},
                                {"/", (a, b) =>
                                         {
                                             var resAsDouble = a/(double) b;
                                             var dbl = (double) (a/b);
                                             if (resAsDouble != dbl) throw new NonIntegralDivisionResult();
                                             return a/b;
                                         }
                                    }
                            };
            var startNos = new[] {1, 5, 6, 7, 9, 10};
            var target = 127;

            var result = new Dictionary<int,List<string>>();

            foreach (var num1 in startNos)
                foreach (var op1 in operators)
                    foreach (var num2 in startNos.Except(new[] { num1 }))
                        foreach (var op2 in operators)
                            foreach (var num3 in startNos.Except(new[] { num1, num2 }))
                                foreach (var op3 in operators)
                                    foreach (var num4 in startNos.Except(new[] { num1, num2, num3 }))
                                        foreach (var op4 in operators)
                                            foreach (var num5 in startNos.Except(new[] { num1, num2, num3, num4 }))
                                                foreach (var op5 in operators)
                                                    foreach (var num6 in startNos.Except(new[] { num1, num2, num3, num4, num5 }))
                                                    {
                                                        try
                                                        {
                                                            var value = op5.Value(op4.Value(op3.Value(op2.Value(op1.Value(num1, num2), num3), num4), num5), num6);
                                                            var name = String.Format("{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}{10}", num1, op1.Key, num2, op2.Key, num3, op3.Key, num4, op4.Key, num5, op5.Key, num6);
                                                            var key = Math.Abs(value - target);
                                                            if(result.ContainsKey(key)) result[key].Add(name);
                                                            else result.Add(key, new List{name});
                                                        }
                                                        catch(DivideByZeroException) {}
                                                        catch(NonIntegralDivisionResult) {}
                                                    }

            var output = result.OrderBy(kvp => kvp.Key).Take(25);
            foreach(var line in output)
                foreach(var value in line.Value)
                    Console.WriteLine("Key: {0} Value: {1}", line.Key, value);
        }
    }
}

Linq makes creating dictionaries easy

Previously, I wrote example code that used one of my library functions to construct a dictionary when given a list or pair of list. Since the place of gainful employment moved to .NET 3.5 I have been able to write some truly linq-y code, and have observed many wonderful things, in particular the extension methods of IEnumerable. Check out ToDictionary( keyFn, valueFn) It's exactly what I was writing in my Functional.array.toDict function. Good work, Microsoft!

Functional composition, fluent programming and command line processing

We have a very repetitive and, to me, offensive piece of code which appears in several places throughout the codebase. The only variation between instances are the names of the parameters and the decision about which ones are mandatory. So I wrote some nice simple, functional code to do the heavy lifting, and now it's a one-liner, more or less!

            string defaultDate = DateTime.Today.ToShortDateString();
            const string defaultCheckType = "pnl";
            
            Dictionary<string, string> mandatoryArgs = Functional.array.toDict(new string[] { "filedir" });
            Dictionary<string, string> optionalArgs = Functional.array.toDict(new string[] {"interfaces", "filename", "reportingdate", "check"},
                                                                              new string[] { string.Empty, string.Empty, defaultDate, defaultCheckType });

            bool result = args > SplitArgsInto(mandatoryArgs, optionalArgs).Then(Validate(mandatoryArgs));

            return new Arguments(mandatoryArgs["filedir"], 
                                    optionalArgs["filename"],
                                    DateTime.ParseExact(optionalArgs["reportingdate"], "dd/MM/yyyy", CultureInfo.InvariantCulture),
                                    (CheckTypeEnum) Enum.Parse(typeof (CheckTypeEnum), optionalArgs["check"]), 
                                    optionalArgs["interfaces"]);

Lovely! Now the arguments are split into mandatory and optional, the mandatory arguments have all been validated and the program receives by return a structure containing the names and values that are relevant. Smashing!

In case you were wondering, the functional composition is hidden in the Then function, which is actually the composition operator in C# land. It takes Func<A,B>, Func<B,C> and returns Func<A,C>.

F# - Active patterns

I like active patterns. I have yet to explore their possibilities completely but one pattern which crops up all the time in our code is checking whether a string is empty and acting accordingly.

In C# we have

if(!String.IsNullOrEmpty(myString))
{
    doSomethingWithTheString(myString);
}
else
{
    doSomethingInNullCase();
}

Clearly, the

doSomething...()

methods will usually be more than a simple procedure, often involving local variables and transformations thereof, but the essence of the pattern is captured above.

We could, of course, transliterate this directly into F# and that is the first step in the conversion process. Thus we have

if(not <| String.IsNullOrEmpty myString) then
    doSomethingWithTheString(myString)
else
    doSomethingInNullCase()

So what? I hear you say. Well, this is a step in the right direction. Functional programmers prefer pattern matching to indiscriminate use of the

if

statement though. The question, therefore, is what pattern can we match to achieve the end and how. Crucially, in F# one cannot match against a general function. Instead one uses what is known as an Active Pattern. There are three forms of Active Patterns: single-valued, partial and multi-valued. The names are mine but they are similar to the official names. I think of 'partial' active patterns as slightly different from the other two.

First, a single-valued active pattern:

let (|EmptyString|) str = String.IsNullOrEmpty str

which could be used in this manner:

match myString with | EmptyString true -> "Empty" | _ -> "Not empty"

I think the syntax for active patterns leaves a little to be desired so let me explain what is happening here. Clearly the match is being performed on

myString

. The match criterion first considered is

EmptyString

. All bar the final parameter (in this case, there are no additional parameters in the match criterion) are evaluated in the context of

myString

. The final parameter in the matching pattern is compared with the return value of the active pattern. In other words, the criterion is

EmptyString myString

which returns a

bool

against which we match

true

.

A multi-valued pattern is similar. For example:

let (|EmptyString|String|) str =
    if String.IsNullOrEmpty str then EmptyString else String(str)

Notice that this pattern looks much more like a discriminated union. Also, whilst it is not necessary to return a value in the 'constructor', if you will, in either case, we do so here for illustrative purposes. This pattern could be used as follows:

match String.Format("Is {0} empty?", myString) with
| EmptyString -> "It's empty"
| String str -> str

Thus

str

holds the string that was successfully matched.

Partial active patterns are a slight change again:

let (|NotEmpty|_|) s = if String.IsNullOrEmpty s then None else Some(s)

Note that I have changed the specified portion of the pattern to

NotEmpty

so that we can return the string that was matched successfully. Note also that this pattern returns an

option

type where the multi-valued pattern returns a

Choice

.

The partial pattern is used similarly:

match String.Format("Is {0} empty?", myString) with
| NotEmpty str -> str
| _ -> "It's empty"

As you can see, the construct is powerful and I haven't demonstrated how to pass additional parameters or match multiple values. Check Wikibooks for further information and then try the broader t'internet.