Archives
-
Reminder - DC ALT.NET Meeting 7/24/2008 - LINQ Deep Dive
Just as a reminder from the previous post, the July meeting for DC ALT.NET will be on July 24, 2008 from 7PM-9PM. Check out our site and our mailing list for more information as it becomes available. This month, K. Scott Allen, of OdeToCode and a co-host of Herding Code, will present a deep dive into LINQ and a code-along so that we can follow along. The intent is to go as deep as we can with LINQ to find out what works, what doesn't and how to use it effectively. So, bring your laptops and get ready...
LINQ
K. Scott Allen has recently recorded an episode on Herding Code dedicated to LINQ. It's well worth a listen as he talks about the following LINQ topics:
- What is it?
- How introducing LINQ to .NET changed the framework
- LINQ Providers
- LINQ to XML
- LINQ to SQL - how it’s different from EF, tips and tricks, when to use it
Special Thanks
Once again I'd like to thank Cynergy Systems, Inc for sponsoring this month's event. As a side note, they are actively looking for experienced .NET developers with interest in WPF and Silverlight. So, if you're looking for a great company that is a leader in the Rich Internet Applications area and want to work in downtown Washington D.C., definitely check them out.
Details
DateTime:
7/24/2008 - 7PM-9PM
Location:
Cynergy Systems Inc.
1600 K St NW
Suite 300
Washington, DC 20006
Show Map
Be there and hope to see a passionate crowd! And don't forget to bring your laptop!
-
Recursing into List Processing
Lately I've been getting back to basics with regards to recursion. This is a basic and essential skill, especially in the functional programming world. Today's dive will be into immutable lists and recursion. I'll do my best to provide the F# and C# equivalent to each call. This is in part of the back to basics and from here I'll move onto other subjects.
Let's catch up to where we are today:
Recursive List Processing
In the functional programming world, and especially in the functional programming world are singly linked immutable lists. Each of the items in the list is a cell with a reference to the next item in the list. For functional programming, unlike imperative programming, they are optimized for recursion. By that I mean that they have a head (the first item) and the tail (the rest of the list). F# has the use of this through the List<'a> class.
Let's walk through a simple example of how you might sum up all items in a list using recursion as well as one for calcuating the length of the list. In F# this is pretty simple, using pattern matching.
F#
#light module ListExtensions = let rec sum = function | [] -> 0 | h::t -> h + sum t let rec length = function | [] -> 0 | h::t -> 1 + length t [1..20] |> ListExtensions.sum |> print_any [1..10] |> ListExtensions.length |> print_any
This function above had a simple pattern matching over the list which said for an empty list, the result would be zero, else it would be the sum of the head and the calculation of the rest of the list and eventually winds its way down to the end of the list. Likewise inthe length, it adds 1 to the calculation of the length function until it winds down to nothing left in the list. In the base .NET libraries, we don't have a list like this, but it's actually not that hard to create one. Let's walk through a simple immutable linked list much like the List<'a> in F#.
Let's define in C# what something like that might look like. I'll start with something the way Wes Dyer had it but with a few changes:
public interface IImmutableList<T> : IEnumerable<T>
{
T Head { get; }
IImmutableList<T> Tail { get; }
bool IsEmpty { get; }
bool IsCons { get; }
}
As you can see, we have a head, a tail and a way to determine if this list is empty or if it is a cons. All very important pieces to the puzzle. This also inherits the IEnumerable<T> interface as well so that we can iterate this should we need to. Now, let's go into the implementation details of the immutable list.
public class ImmutableList<T> : IImmutableList<T>
{
public class EmptyList : ImmutableList<T> { }
public class ConsList : ImmutableList<T>
{
internal ConsList(T head, IEnumerator<T> enumerator)
{
Head = head;
this.enumerator = enumerator;
}
}
private static readonly IImmutableList<T> empty = new EmptyList();
IImmutableList<T> tail;
IEnumerator<T> enumerator;
public T Head { get; private set; }
public static IImmutableList<T> Cons(T head, IImmutableList<T> tail)
{
return new ConsList(head, tail.GetEnumerator());
}
public static IImmutableList<T> Cons(IEnumerator<T> enumerator)
{
return enumerator.MoveNext() ? new ConsList(enumerator.Current, enumerator) : empty;
}
public IImmutableList<T> Tail
{
get
{
if (enumerator != null)
{
tail = Cons(enumerator);
enumerator = null;
}
return tail;
}
}
public bool IsCons { get { return this is ConsList; } }
public bool IsEmpty { get { return this is EmptyList; } }
public static IImmutableList<T> Empty { get { return empty; } }
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable<T>) this).GetEnumerator();
}
public IEnumerator<T> GetEnumerator()
{
for (IImmutableList<T> current = this; !current.IsEmpty; current = current.Tail)
yield return current.Head;
}
}
Now what I have done here is implemented two internal lists to represent a "cons" and one to represent an empty list. This helps when determining whether the list is empty or not without having to check references and whether something is null. Inside my ConsList<T>, I'm able to create a new instance of the ImmutableList<T> with the head value and the rest of the list.
The head of the list is just simply that, the first item. When the tail property is called, I create a new IImmutableList<T> with my enumerator by calling the Cons method. I also have properties which define and empty list, whether it is empty or whether it is a "cons". Like I said, there's nothing hard about this.
Then I'm able to define a Sum and Length methods much as above with something like this:
public static int Sum(this IImmutableList<int> list)
{
if (list.IsEmpty)
return 0;
return list.Head + Sum(list.Tail);
}
public static int Length<T>(this IImmutableList<T> list)
{
if (list.IsEmpty)
return 0;
return 1 + Length(list.Tail);
}
And then invoking this is pretty straight forward through the main method:
static void Main(string[] args)
{
var enumerator = Enumerable.Range(1, 10).GetEnumerator();
var list = ImmutableList<int>.Cons(enumerator);
var sum = list.Sum();
var length = list.Length();
Console.WriteLine("List sum : {0}", sum);
Console.WriteLine("List length :{0}", length);
}
But what about tail recursion when doing list processing? Let's walk through one more example of tail recursion with lists. In this example, I'm going to go ahead and return the last item in the list. It's a pretty simple and straight forward function which determines whether the list only has a head, or if it also has a tail, then recurse on the function again.
F#
#light
module ListExtensions =
let rec last = function
| [] -> invalid_arg "last"
| [h] -> h
| h::t -> last t
[1;5;3;2;6;] |> ListExtensions.last |> print_any
Now the C# version should look just as familiar to you. Basically instead of the pattern matching, which I'd love to have in C#, I'm using if statements to determine whether I'm returning the head, or the evaluation of the Last function again until I wind down to the head.
C#
public static T Last<T>(this ImmutableList<T> items)
{
if(items.IsEmpty)
throw new ArgumentNullException("items");
var tail = items.Tail;
return tail.IsEmpty ? items.Head : tail.Last();
}
var e1 = new List<int> {1,5,3,2,6}.GetEnumerator();
var items = ImmutableList<int>.Cons(e1);
var last = items.Last();
Console.WriteLine("Last item: {0}", last);
In the past I covered why tail recursion is important in my previous post. Unfortunately, the C# code won't do much for you uniless the compiler is optimized for tail calls, or you are using the x64 version of Windows. I have some of these samples in my Functional C# samples on MSDN Code Gallery.
Wrapping it Up
As you can see, recursion is a pretty interesting topic. One of the best ways to avoid mutable state in your programs is through recursion. I've shown some simple examples of where recursion can help to solve some of those issues. This will wrap up a lot of the discussions about recursion and then I'm moving into such topics as memoization, continuations and so on. The code samples will be available on the Functional C# Samples during this back to basics trip.
-
Learning Erlang - Erlang Gaining Momentum
You may have noticed that I've been talking a bit about concurrency and Erlang recently. I've started to notice that others are taking notice and giving Erlang another look. I've been a fan of the language for a while, although it is a functional language ala a Haskell, OCaml, F# and so on, it's key strengths doesn't come necessarily from that, but from how it handles concurrency. I'm really fond of the language succinctness and beauty using pattern matching, higher order functions and so on much as I have with F#.
Gaining Momentum
As I stated before, many people are starting to give Erlang another look. For more than 20 years since its inception around 1987, Erlang has received little notice outside of the telecomm industry from whence it came. Then in 1998, it was released as open source, but still not much momentum gathered around the language. But, then things started to change recently. Moore's law started to change, not from faster CPUs, but more cores to the CPUs. Our traditional methods of sequential imperative programming couldn't scale and utilize a lot of the machine this way.
Then we started thinking about locks, monitors, mutexes, but the programming model isn't exactly easy. And to boot, they tend to be a bit low-level for most pieces that we need. Instead, we need more constructs such as guaranteeing pure functions and this function is ok for concurrency at either a language level or at least a library level. Erlang is designed with this in mind, as it is a functional language, so functions are values, and values are immutable. But not only that, the isolation of the processes allows for lightweight processes with no shared state between them. This allows for a given process to fail without taking down the whole system, another important concurrency item that is important.
With this, companies started to take notice. As noted by a post by Chris Vertonghen in his post "Erlang, or Utility-computing vs. Appliance-computing", he notes a few items of interest such as:
- Amazon SimpleDB is built on Erlang
- IMDB switching from PERL to Erlang
- Facebook chat written in Erlang
- Google Gears using "Erlang-style" concurrency
Other places are also looking at Erlang. According to the GitHub blog, there is a project called egitd and is a replacement for the stock git-daemon that ships with git. Erlang is perfect for these massively concurrent systems with good failover capabilities.
Getting Started
Getting started in Erlang is pretty easy. Joe Armstrong's Programming in Erlang book tells you all you need to know on how to set it up. I downloaded the distribution from the Erlang site for the runtime and I used Eclipse with Erlide to run through the samples in the book. I had no issues setting it up and it's quite easy to use.
I highly recommend that you get Joe Armstrong's Programming Erlang book as well as check out the Pragmatic Programmer screencasts on Erlang which you can find here.
From the F# Perspective
I've stated before that Erlang-style messaging through mailboxes is already supported in F#. But, it's nowhere near as capable as Erlang. Let's hope these kinds of issues can be raised and added to the libraries. But, let's look at it from another perspective. If you know functional programming and F#, you shouldn't have trouble in Erlang whatsoever. In fact, I have a few examples of functions written in both Erlang and F# that do the same thing.
Pattern Matching
Pattern matching is pretty important in Erlang. Such constructs as for loops do not exist, instead relying on patterns instead to handle the basic control flow. Let's look at a simple area calculator written in Erlang.
-module(geometry)
-export(area/1)
area({rectangle, Width, Ht}) -> Width * Ht;
area({circle, R}) -> 3.14159 * R * R;
area({square, X}) -> X * X.
geometry:area({rectangle, 10, 5}).
geometry:area({circle, 1.4}).
geometry:area({square, 2.5}).
What this sample did was used a tuple to wrap up the type of rectangle, circle and square. Then I create multiple area functions that are my pattern. Then at the bottom, after compiling and exporting my functions through my module, I'm able to call the functions with the given values. How about in F#?
module Geometry =
type Shape = Circle of float | Rectangle of float * float | Square of float
let area = function
| Circle R -> 3.13159 * R * R
| Rectangle (Width, Ht) -> Width * Ht
| Square X -> X * X
Geometry.area (Geometry.Rectangle(10.0, 5.0))
Geometry.area (Geometry.Circle(1.4))
Geometry.area (Geometry.Square(2.5))
I changed the shape to be a discriminated union because overloading of functions to take different tuples is not allowed. Instead, I then switched to a union and pattern matched against that, thus giving the value. Let's move onto more quick examples on how they differ
Lists
Simple list processing is also pretty important. F# and Erlang are also quite similar in this respect as well. There are a few things F# doesn't have such as the remove operator, but for the most part, it's pretty comparable. Functional languages have much different collections than imperative ones, which are optimized for recursion. This includes the feature of the head, the first item in the list, and the tail, the rest of the list. Let's look at a simple sum function in Erlang.
-module(MyLists)
-export(sum/1)
sum([H|T]) -> H + sum(T).
sum([]) -> 0.
L = [1,3,10]
MyLists:sum(L)
What I am able to do is pattern match against the head and the tail of the given list to add the head value to the recursive call to the tail through linear recursion. Next, I'll take that same sample and port it to F# to show how little difference there is.
module MyLists =
let rec sum = function
| [] -> 0
| H::T -> H + sum(T)
let l = [1;3;10;]
let lResult = MyLists.sum(l)
Applying lambda expressions on top of lists is pretty simple as well. Here is a simple map function on a list in both Erlang and F#.
-import(lists, [map/2]).
L = [2,4,6,8,10].
LResult = lists.map(fun(x) -> x*x end, L).
And then in F#, to be able to do the map:
[2;4;6;8;10] |> List.map(fun x -> x * x)
As you can see, there are some differences, but for the most part, I haven't had any issues jumping between the languages. This was just meant to be a little exercise about how you can learn from each language. There is much to be learned from both languages, especially in regards to concurrency. I hope to cover more of that shortly.
Wrapping It Up
Functional languages such as Erlang and F# have a lot to offer in terms of concurrency oriented programming. I think now that Moore's law has changed in a way that standard sequential programming doesn't work as well, it's time to start discovering what the functional programming people and for that matter Erlang people have been talking about. This is meant to give you just a little kickstart to look at Erlang, and indeed F# for concurrency. But, not only that, but take the ideas from here and apply them to your other language of choice whether it be C#, Ruby, Python and so on.
The real keys to success for Erlang reside not only in the language itself, but also the frameworks around it, and the tooling, such as the IDEs, etc. Ruby became popular as a language due to the Rails framework although the tooling still isn't the best for it. How will Erlang grow in this area remains to be seen, but I am optimistic.
-
Aspects of Functional Programming in C# Presentation and Code
As noted before, I was scheduled to give a presentation on Aspects of Functional Programming in C# 3.0 yesterday at the Rockville .NET User Group (RockNUG). Unfortunately, before the presentations were to commence, the power went out and the event was scrapped for the evening. Instead, the intention is to reconvene next month at the same time to present again. So, I expect I'll be there once again the same time next month. In the mean time, I've decided to post my slide deck and code samples for all to see. I'll cover that more below.
Here are some resources that will be helpful in covering functional programming aspects:
Functional Programming
C# Futures
Functional Programming Aspects with C#
- Functional C# Revisited - Into the Great Void
- Functional C# - Unfolding Lists
- Functional C# - Learn from F# and LINQ
- Recursing into Linear, Tail and Binary Recursion
- Define Recursion - See Recursion
Podcasts
- .NET Rocks Episode 310 - Simon Peyton Jones on Functional Programming and Haskell
- .NET Rocks Episode 270 - Erik Meijer on LINQ
- Software Engineering Radio Episode 97 - Anders Hejlsberg
As I said before, I'm making the code available as I put it up on MSDN Code Gallery as the FunctionalCSharp project. This is intended to be a library of functional programming techniques in C# 3.0 and some demonstrations of moving from imperative style programming to a more functional programming style. This is an ongoing project and more will be added in time, and I may end up just putting them up not as samples, but as a library.
Some of the topics covered in these code projects are:
- Closures
- Currying
- Filter High Order Function
- Fold High Order Function
- Iterators
- Lazy Evaluation
- LINQ
- Lists (Immutable and Recursive)
- List Comprehensions
- Map High Order Function
- Memoization
- Monads
- Operators (Forward, Reverse, etc)
- Recursion
- Unfolding and Generators
My slide deck can be found here and my code snippets once again can be found here.
-
DC ALT.NET - 7/24/2008 - LINQ Deep Dive with Scott Allen
The July meeting for DC ALT.NET will be on July 24, 2008 from 7PM-9PM. Check out our site and our mailing list for more information as it becomes available. This month, K. Scott Allen, of OdeToCode and a co-host of Herding Code, will present a deep dive into LINQ and a code-along so that we can follow along. The intent is to go as deep as we can with LINQ to find out what works, what doesn't and how to use it effectively. So, bring your laptops and get ready...
I'd like to thank Cynergy Systems, Inc for sponsoring this month's event. As a side note, they are actively looking for experienced .NET developers with interest in WPF and Silverlight. So, if you're looking for a great company that is a leader in the Rich Internet Applications area and want to work in downtown Washington D.C., definitely check them out.
The information is as follows:
DateTime:
7/24/2008 - 7PM-9PM
Location:
Cynergy Systems Inc.
1600 K St NW
Suite 300
Washington, DC 20006
Show Map
Be there and hope to see a passionate crowd!
-
Recursing into Linear, Tail and Binary Recursion
In my previous post, I talked about some of the basics of recursion and why you might want to use it to your advantage. Today, let's dive a little deeper into the different kinds of recursion, including linear, tail recursion and finally binary recursion. This is in a series of back to basics covering recursion in some depth.
Starting Off
Where we left off is to take a simple imperative statement and make it not only recursive, but we could also hypothetically turn it into tail recursive as well. Let's start off with the simple, yet overused factorial example in a very imperative way using looping:
C#
public static int Factorial(int n)
{
var fact = 1;
var i = n;
while (i > 0)
{
fact = fact * i;
i--;
}
return fact;
}
F#
let factorial_imperative n =
let mutable fact = 1
let mutable i = n
while i > 0 do
fact <- fact * i
i <- i - 1
fact
So, what we're left with is mutation galore. That's perfectly ok in the imperative world, but it doesn't make sense to me in the functional world since we have such things as recursion. Functional languages make you go out of your way to make values mutable, because by default they aren't mutable at all.
Linear Recursion
Linear recursion is by far the most common form of recursion. In this style of recursion, the function calls itself repeatedly until it hits the termination condition. After hitting the termination condition, it simply returns the result to the caller through a process called unwinding. Most of my samples I posted in the previous post followed this way of recursion.
C#
public static int Factorial(int n)
{
if (n <= 1)
return 1;
else
return n * Factorial(n - 1);
}
F#
let rec factorial_linear n =
if n <= 1 then 1 else n * factorial_linear (n - 1)
As you noticed, the last call here is a calculation, which helps unwind itself to the termination condition of 1. Of course it's also guarded against negative input as well which would cause an infinite loop, which would be pretty bad. But with large input, this could be a problem.
Tail Calls
As I've mentioned before, it's pretty important to think about the stack when you do recursion. For the reasons of stack overflows, it's pretty important to mention. When you call an F# function, stack space is allocated and then freed when the function returns, or, when a tail call is performed. We have to be aware of this, because a very deep set of nested function calls will cause a StackOverFlowException to be thrown. Below is a simple example on how this can occur.
#light
let rec recursiveFunc i : unit =
if i >= 1000000 then
()
else
if i % 1000 = 0 then
printfn "Recursing at %i" i
recursiveFunc (i + 1)
printfn "Just called the function with %i" i
recursiveFunc 100
The above function actually recurses, but that's not the last thing the function does. It in turn calls a printf end line function to display the result. If you let this run, you'll get a nice StackOverFlowException and it will take down your F# Interactive (fsi) session. How do you fix this situation? Well, it's a topic called tail recursion which will expand upon this.
Tail Recursion
Tail recursion is a specialized form of the linear recursion where the last operation of the function happens to be a recursive call. The difference here is that in my previous samples, I've been calling functions which perform a calculation on the result of the recursive call. That could lead to stack overflows should the recursion get too deep. Instead, I don't want to do any work during the unwinding phase, just return the value from the function.
Let's take the above sample and make it tail recursive:
#light
let rec recursiveFunc i : unit =
if i >= 1000000 then
()
else
if i % 1000 = 0 then
printfn "Recursing at %i" i
recursiveFunc (i + 1)
recursiveFunc 100
All I had to do was get rid of the last statement and now the last statement is simply a calling of the function again with no work performed. If I run it through the F# interactive again, I get no problems at all, and it runs through smoothly. Let's refactor our factorial to be tail recursive in F#, and then look at a C# solution.
F#
let rec factorial_tail n =
let rec factorial_inner acc x =
if x <= 0I then acc
else factorial_inner (x * acc) (x - 1I)
factorial_inner 1I n
As you can see, the last calls to my recursive inner function is indeed tail recursive as no work is being done to the result of any calls. From there, my outer function should be able to call passing in the accumulator of 1 and the number we're passing in. Since I'm using BigInt, I don't have a problem with overflow either in regards to really large input. This is something that the .NET BCL was working on, but kept it internal in the System.Core.dll it seems. But, F# was nice enough to give us BigNum and BigInt implementations, as F# tends to be rather math centric.
The Problem with C# and Tail Calls
Now turning our attention to the C# counterpart to this, let's try our implementation of the above functionality in it. Instead of just another function, I'll inline the accumulator function inside as an anonymous function:
C#
public static ulong Factorial(ulong n)
{
Func<ulong, ulong, ulong> factorial_acc = null;
factorial_acc = (acc, x) =>
{
if (x <= 0) return acc;
return factorial_acc(x * acc, x - 1UL);
};
return factorial_acc(1UL, n);
}
But the problem is, is that this won't work on a 32 bit machine. Why you might ask? Well, as Jomo Fisher, an F# team member, points out in his post about recursion in three languages, the C# compiler does not do tail call optimization. Instead, all managed languages have a second opportunity to optimize through either NGEN or the JIT compiler. As it turns out, the x64 version of the JIT will optimize the tail call right now, whereas the 32 bit compiler will not. By default on your C# projects, it's targeted at AnyCPU which in my case since I'm running on a VPC, targets x86, will cause the overflow, whereas if I had been running on my base machine, it would have been ok.
This is another in the line of reasons why F# is the better language for recursion as well as functional programming fundamentals. C# will get you partially there, but there are things such as these which will trip up developers and leaving themselves nowhere to go. To which I say, pick the best language for the job at hand, whether it be F#, C#, Ruby, Python, Erlang, Haskell, JavaScript, etc.
Binary Recursion
Another form of recursion is binary recursion. This form of recursion has the potential for calling itself twice instead of once as with before. This is pretty useful in such scenarios as binary trees as well as the trite and overused Fibonacci sequence. Such an example is below:
let rec fibonacci n =
if n <= 2 then 1
else fibonacci (n - 1) + fibonacci (n - 2)
But what's interesting is that we could do this better through tail recursion through the use of our inner auxiliary function, such as this:
let fib n =
let rec fib_acc a b x =
if x <= 1 then b
else fib_acc b (a + b) (x - 1)
fib_acc 0 1 n
But, back to the point, here's another use of binary recursion to print out the values in a tree.
type Tree<'a> = | Leaf of 'a | Node of Tree<'a> * Tree<'a>
let rec printBinaryTreeValues t =
match t with
| Leaf x -> printfn "%A" x
| Node (l, r) ->
printBinaryTreeValues l // called once
printBinaryTreeValues r // called twice
printBinaryTreeValues (Node ((Node (Leaf "jeden", Leaf "dwa")), (Node (Leaf "trzy", Leaf "cztery"))))
As you can see from this example, I printed out the values from the binary tree, leaf by leaf using binary recursion.
Wrapping It Up
As you can see here, I've covered a bit of ground on more recursive algorithms. There is still yet more to be covered including processing of lists, unbalanced trees, continuations and so on. More on that soon! In the mean time, I hope you rediscover recursion and what it can do for you in terms of condensing code. But, it's also important to see where it makes sense and where it doesn't.
-
RockNUG Meeting - 7/9/2008 - Functional C#
Next week I will be presenting a lightning talk at the next Rockville .NET Users Group (RockNUG) on Functional C#. I've talked about this topic quite a bit recently on a couple of threads now:
- Functional C# Revisited - Into the Great Void
- Functional C# - Unfolding Lists
- Functional C# - Learn from F# and LINQ
- Currying
- Filter
- Map
- Option Types
- Tuples
- Folding and Unfolding
- Recursion
- Lazy Evaluation
- And more...
Anyhow, here are the details:
Date/Time:
Wednesday, July 9, 2008 - 6:30-9:00 PM
Location:
Montgomery College, Rockville
Humanities Building - Room 103
Rockville, MD
Directions
Hope to see you there!
-
Define Recursion - See Recursion
Lately, I've noticed a few blogs are doing the come back to basics post, such as Scott Hanselman's. I think that's an effort that should be lauded, because many have a tendency to go off on pretty advanced topics, yet not provide enough for those just starting to get the full context. So, with that, I'm going to dig into one piece of programming that should have been ingrained should you have been a CS major in college or at least took some courses.
Recursion
Recursion is one of those basic topics that come up time and time again as one of the core topics. It's not as often talked about in the imperative and object oriented world, but in the functional programming world, it matters a whole bunch. Not only to be able to describe what it is, but the benefits, and where you might be able to break your problem down into using it.
So, before we get too far, what exactly is it, and how do we get there? Basically recursion is to allow a function to call itself repeatedly during the body of that function. Most imperative languages from the C world use for loops, while loops and so on, so many times recursion isn't needed. Functional languages such as F#, allow for recursion, but makes them a special designation to enforce its behaviors.
When coming to a place such as Microsoft, understanding these concepts are key. Chances are you may get asked some of these questions, because people like me, when walking through complex structures, use recursive algorithms. It's a nice tool to have in the toolbox.
Let's first look at an example not using recursion, then move towards recursion. First start off with a pretty obvious one in computing a factorial:
public static int Factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
result *= i;
return result;
}
To me, that's pretty horridly imperative. We can make the code much more concise through the use of recursion and not mutate state during the operation. With the proper attention of course to decrementing the counter so that we don't get into infinite loops. An important lesson to learn is to not recurse infinitely, but in a controlled manner towards termination through a technique called "Well Founded Recursion". Let's rewrite this to a much more manageable way:
C#
public static int Factorial(int n)
{
if (n <= 1) // Exit condition
return 1;
return n * Factorial(n - 1);
}
F#
let rec factorial n =
if n <= 1 then 1 else n * factorial (n - 1)
The basic idea is to break down your problems into smaller instances of the same problem. Sometimes, the last thing we do in this function is return the recursion of the function. This is called "Tail Recursion". Below is a simple example of tail recursion:
let rec last l =
match l with
| [] -> invalid_arg "l"
| [head] -> head
| head :: tail -> last tail
The above sample will ultimately give me the last item in a list since F# has pointers to the head of the list, we need to get the last one. We'll get more into tail recursion in the next post, but I thought I'd introduce it now. It's very important as well to know.
Let's take another example, this time walking a directory structure to lazily display all files in a directory. Of course we can note that the Directory.GetFiles already has the capability of getting all files in all folders, but for this exercise, let's pretend it doesn't exist. How might we do this? Let's try the lazy approach the first time around through IEnumerable<string>.
C#
public static IEnumerable<string> GetFiles(string rootPath)
{
foreach(var file in Directory.GetFiles(rootPath))
yield return file;
foreach (var directory in Directory.GetDirectories(rootPath))
foreach (var file in GetFiles(directory))
yield return file;
}
F#
let rec getFiles rootFolder =
seq {
for file in Directory.GetFiles(rootFolder) -> file
for dir in Directory.GetDirectories(rootFolder) ->> getFiles dir
}
What this allows me to do is recurse through a given directory hierarchy by first grabbing all the files and then going through a tail recursion through all the subdirectories. The F# way is a bit more concise through the use of Sequence Workflows, which I'll get to at another time. If you understand anything about F#, understanding workflows is by far one of the most important.
Mututal Recursion
Another interesting way to express recursion is to define them simultaneously by separating the definitions. This allows the functions to play off each other and work towards a deterministic end. The cannonical example of this is the odd/even sample. Let's walk through that quickly in both C# and F#:
C#
public static bool IsEven(int number)
{
if (number == 0)
return true;
else
return IsOdd(number - 1);
}
public static bool IsOdd(int number)
{
if (number == 0)
return false;
else
return IsEven(number - 1);
}
F#
let rec even n = (n = 0) || odd(n - 1)
and odd n = (n <> 0) && even(n - 1)
As you can see, I decrement the counter each time and call the complement function until I reach 0 and at that point, I can determine which one hits 0 and then it becomes apparent whether it is odd or even. F# goes a bit further to simplify this so that I can declare those functions as a pair through the use of the and keyword. Parsing of trees is particularly useful using mutual recursion. But just as easily, we could have done the above sequence without using recursion at all such as this:
public static bool IsEven(int number)
{
return number % 2 == 0;
}
public static bool IsOdd(int number)
{
return !IsEven(number);
}
So, that's not really a good example. instead, let's look at a Hofstadter Male-Female Sequences instead.
The pair of sequences is defined by Female(0) = 1 and Male(0) = 0 and
Female(n) = n - Male(Female(n - 1)
Male(n) = n - Female(Male(n - 1)
This is defined as the same way as before, but we recursively call in the Male to the Female and back to the male, whereas it's the opposite in the FemaleSequence method. This is just a simple implementation of the above algorithm in our C# and F# code respectively.
C#
public static int MaleSequence(int n)
{
if (0 == n)
return 0;
return n - FemaleSequence(MaleSequence(n - 1));
}
public static int FemaleSequence(int n)
{
if (0 == n)
return 1;
return n - MaleSequence(FemaleSequence(n - 1));
}
F#
let rec maleSequence n = if n = 0 then 0 else n - femaleSequence(maleSequence n - 1)
and femaleSequence n = if n = 0 then 1 else n - maleSequence(femaleSequence n - 1)
There are more examples out there, but in the mean time, there's plenty more to cover with recursion. Next, let's cover lists.
Walking Lists
Another thing we can do with recursion is the ability to walk lists. Most people think of lists as an ordered collection with a beginning and an end, with one right after another. How terribly imperative if you think that way... When we think of lists in a recursive way, we think of a list to have an item, and the rest of the list, or just an empty list. C# and the base class library does not have this of course defined in any meaningful way, so let's look at the F# version of a list.
module List =
val hd: 'a list -> 'a
val tl: 'a list -> 'a list
What that tells us is that the head item is the first, and the tail is the rest. Let's do a quick recursion to calculate the length of a list using some pattern matching:
let rec length l =
match l with
| [] -> 0
| head :: tail -> 1 + length tail
What I'm doing is pattern matching against the list. What the pattern matching allows me to do is short circuit if it's an empty list, else, I'm splitting the head and the tail, and adding one to the length of the tail call with the tail of the list. Let's look at another to concat a list of lists into a single list:
let listOfList = [[1;2;3;];[4;5;6;];[7;8;9]]
let rec concatList l =
match l with
| [] -> []
| head :: tail -> head @ concatList tail
There is much more to cover here and I'll do that in subsequent posts.
Why Recursion?
Now that we covered some of the basics, it's time to ask the question why. Why is recursion important and why use it? Well, to answer that lightly, in order to walk such things as trees, directories, and so on, it's an absolute essential. But, let's consider just a general functional programming question of why use it.
It's often the case that when people first start out with programming in F#, they are often in the imperative and OO mindset still. That's ok since F# allows for this, but there are better ways to accomplish in the functional mindset. Many times, people will port over their C# code directly to F# with the mutable variables or reference cells and leave an ugly mess. Some of that can be solved with recursion. Let's take a pretty naive example:
C#
public static void CountDown(int n)
{
while(n > 0)
{
DoOperation();
WaitSome();
n -= 1;
}
}
When translated directly to F# looks like this:
let countDown n =
let mutable localN = n
while localN > 0 do
DoOperation()
WaitSome()
localN <- localN - 1
What we've had to do is use reference cells so that we could change the value of n directly. From there, we have to use special operators to change and alias the value of n. Not the prettiest code. Not only that, but there is mutation galore, and I have to do extra work when creating a local iterating variable. instead, we should focus on recursion and look at the problem slightly differently.
let rec countDown n =
match n with
| 0 -> 0
| _ ->
DoOperation()
WaitSome()
countDown (n - 1)
What this allows me to do is get rid of the local mutables, but also helps me break my problems into smaller, more similar problems which can be recursed. This allows for better code reuse and maintenance I think.
Wrapping It Up
I'd like to spend some more time with tail recursion as I think it's pretty important. As well, I'll also talk about how you can do the same in C# as well (with a little work of course). But in the mean time, I hope I've demonstrated the simple act of recursion, when to look for it, and how to exploit it. Not all problems are ready for recursion, but when you find the right opportunities for them, it's quite powerful.
