Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 30. January 2012 01:32

As happy as I am with how Bumblebee came out so far, there was one sore spot bugging me. I tried my best to write it in a functional style, but failed in one place. The inner part of the Search algorithm, which processes bees coming back in the queue with a new solution, was written as a while loop, using two mutable references to maintain the best solution found so far, and the list of solutions stored by the inactive bees.

And then it hit me yesterday, as I was reading some material on F# Azure worker roles.

Novice:

   Master, I fail to find the path to the immutable way.

Master:

   Immutable way?

   Nothing changes, just call the

   Immutable way.

This is an execrable Haiku, and a reminder to myself. When I get stuck with my old mutable ways in F#, usually the answer is recursion.

In this case, all it took was rewriting the inner loop as a recursive function. The original loop looked along these lines:

while cancel.IsCancellationRequested = false do
   match returnQueue.IsEmpty with
   // the returning bees queue is not empty
   | false -> 
      let success, bee = returnQueue.TryDequeue()
      match success with
      // a returning bee has been found in the queue
      | true -> 
         inactives := waggle !inactives bee
         let candidate = Hive.solutionOf bee
         if candidate.Quality > best.Value.Quality then
            best.Value <- candidate
            foundSolution.Trigger(new SolutionMessage<'a>(candidate))
         else ignore ()
      // more code, irrelevant to the point

The recursive version simply includes in its arguments list all the previously mutable variables, and calls itself, passing along the result of the updates, along these lines:

let rec loop (queue: ConcurrentQueue<Bee<'a>>) best inactives (cancel: CancellationTokenSource) =
   if cancel.IsCancellationRequested then ignore ()
   else
      let success, bee = queue.TryDequeue()
      if success then
      // a returning bee has been found in the queue
         let updatedInactives = waggle inactives bee
         let candidate = Hive.solutionOf bee
         let updatedBest = bestOf candidate best
         if candidate.Quality > best.Quality 
         then foundSolution.Trigger(new SolutionMessage<'a>(candidate))
         
         dispatchBee updatedInactives pickRandom waggle bee

         loop queue updatedBest updatedInactives cancel

      else loop queue best inactives cancel

The structure is essentially the same, but all the mutable variables are now gone; instead, the recursive function passes forward new “updated” values.

I think what tripped me up is the fact that I never used recursion to run an “infinite loop” before – I always saw them done using while true statements. Conversely, I always used recursion to produce an actual result, computing intermediary results until a termination condition was met. This one is a bit different, because the recursion simply passes along some state information, but doesn’t return anything (its return is unit) or terminate until a cancellation happens.

by Mathias 21. August 2011 16:15

Let’s take a last stab at our beer-delivery problem. We tried out a Sieve, we used the Microsoft Solver – time for some recursion.

How can we organize our recursion?

If we had only 1 type of beer pack, say, 7-packs, the best way to supply n bottles of beer is to supply the closest integer greater than n/7, that is, $$\lceil {n \over 7} \rceil$$

If we had 7-packs and 13-packs, we need to consider multiple possibilities. We can select from 0 to the ceiling of n/7 7-packs, and, now that we have only one type of case pack left, apply the same calculation as previously to the remaining bottles we need to supply – and select the best of the combinations, that is, the combination of beer packs closest to the target.

If we had even more types of beer packs available, we would proceed the same way, by trying out the possible quantities for the first pack, and given the first, for the second, and so on until we reach the last type of pack – which is pretty much the outline of a recursive algorithm.

More...

by Mathias 26. June 2011 17:06

I have been digging into the Task Parallel library lately, and enjoying it a lot. As an exercise, I wondered if I could implement the classic FizzBuzz problem, using only Tasks, no loop-related keyword, and no method or property. To enforce this is, we’ll get FizzBuzz to run in the Main() method of a simple console, using only variables created locally.

Note: this is clearly a totally preposterous way to use the Task Parallel library. There is absolutely no benefit in using it in this context, I am doing this only for the sake of exploring how tasks work.

So how would we go about that?

A Task represents an asynchronous operation; it wraps a block of code, waiting to be executed. For instance, the following code queues up work to print out “Starting” to the console, and begins execution when we request the Task to start:

private static void Main(string[] args)
{
   var rootTask = new Task(
      () =>
         {
            Console.WriteLine("Starting");
         });
   rootTask.Start();
   Console.ReadLine();
}

We clearly need something more for FizzBuzz. If we want to avoid looping constructs, we need to have a form of recursion going on, so that we can work on increasing integers, until we reach the limit we set to our FizzBuzz.

Fortunately, Tasks are about more than simply executing a block of code; they can be composed, defining what tasks can be started when some precursor tasks are finished. In particular, Tasks allow Continuations: what to do once a specific task terminates can be defined, by using Task.ContinueWith(), as in this example:

private static void Main(string[] args)
{
   var rootTask = new Task(
      () =>
      {
         Console.WriteLine("Starting");
      });

   var nextTask = new Task(
      () =>
      {
         Console.WriteLine("Next task!");
      });

   rootTask.ContinueWith(it => nextTask.Start());

   rootTask.Start();
   Console.ReadLine();
}

Here we define our root task, still printing “Starting”, and another task, which will print “Next task!”, and we pass that nextTask as a follow-up task to the rootTask via ContinueWith. Running this code will execute first the rootTask, and upon completion, kickstart the second one, and print both expected lines to the Console.

More...

by Mathias 16. May 2010 08:14

I have been working with trees quite a bit lately, because I am coding something which involves probability trees: based on the state of the system, there is a number of things which can happen, each with a certain probability.

I ended up writing a simple generic Node class, which can contain anything, and can have multiple children, along these lines:

public class Node<T>
{
  public Node()
  {
     this.Children = new List<Node<T>>();
  }

  public T Content
  {
     get;
     set;
  }

  public List<Node<T>> Children
  {
     get;
     private set;
  }

  public bool IsLeaf
  {
     get
     {
        return (this.Children.Count() == 0);
     }
  }
}

Pretty quickly, I realized I would need to get the list of all nodes under a certain node, as well as the list of its leaves (a leaf being a node that has no children, i.e. an endpoint of the tree). This is a job tailor-made for recursion: if a node is a leaf, return it, otherwise, search further in all his children. 

More...

Comments

Comment RSS