Posts Tagged With 'Higher Order Programming' RSS Feed

Divvy up my list? Aye!

pheaven — Thu, 31 Jan 2008 04:28:52 -0700

I wasn't born in Yorkshire, but I spent most of my childhood growing up there. Yorkshire, a large county in the north east of England, has its own collection of slang, not least including the word "aye", which it appears is appropriate in response to pretty much any situation. Another slang phrase is "divvy up". Basically, this just means to divide a bunch of things up somehow.

These days, I spend a lot of my time writing C#. If I'm dealing with a bunch of things in C#, I'll usually store them in a generic List collection, or some other collection. This got me thinking: how can I divvy up a List in C# into multiple Lists? And that's when I decided to implement the Divvy extension method.

What we're aiming for

Suppose we have a list of scores:

var Scores = new List<int>()
    { 87, 32, 45, 60, 91, 10, 58, 77, 66, 71 };

We want to categorize them by grade. For example, anything over and including 85 is a grade A, anything from 70 to 84 is a grade B and so on. This is where our Divvy extension method is going to come in useful. We'll look at what the following code means and how to implement the Divvy method in a moment, but using it will look like this:

// Split them up by grade.
var GradeScores = Scores.Divvy(new Dictionary<string, Predicate<int>>()
{
    { "Grade A", x => x >= 85 },
    { "Grade B", x => x >= 70 && x < 85 },
    { "Grade C", x => x >= 50 && x < 70 },
    { "Fail",    x => x < 50 }
});

It will give us back a Dictionary where the keys are the names of the categories we supplied when calling Divvy and the values are lists of items in that category. Therefore, we can loop over like this:

// Display results.
foreach (var Grade in GradeScores.Keys)
{
    Console.Write(Grade + ": ");
    foreach (var Score in GradeScores[Grade])
        Console.Write(Score.ToString() + " ");
    Console.WriteLine();
}

Which will give us the following output:

Grade A: 87 91
Grade B: 77 71
Grade C: 60 58 66
Fail: 32 45 10

Neat, huh? Let's take a look at how on earth we make this work.

Extension Methods

The first problem is that we want to have a method on the List class. However, that class is in the .Net class library, so we can't go changing it. We also don't want to have to start using a subclass of List all over the place just to get the extra method.

C# 3.0 allows you to write extension methods (detailed tutorial here). These are static methods that can be called as if they were instance methods. This way, we can write a method that can be called on instances of the List class. So our starting point is:

namespace Jnthn.ListExtensions
{
    public static class DivvyUp
    {
        public static void Divvy<T>(this List<T> TheList)
        {
            
        }
    }
}

Note the use of the "this" keyword to mark this as an extension method. Also note that List is a generic type - it takes a type parameter T. However, we don't know what this type is, and we want to make Divvy generic too. Thus we declare it as Divvy<T>.

The Return Type

We are going to split the List into many other Lists, based upon the category the item gets placed into. The categories are named by strings, e.g. "Grade A" and "Grade B". Therefore, for our return type we can use:

Dictionary<string, List<T>>

That is, a Dictionary where the keys are strings and the values are List<T>s, where T is the type of the original List that we were called on. Therefore, our method is now:

public static Dictionary<string, List<T>> Divvy<T>(
    this List<T> TheList)
{
    // Implementation goes here.
}

The Categorizers Parameter

Now we need a way to specify how to divvy up the list into the different categories. This is a mapping (from category name to something that determines whether an item is in that category), so we can use a Dictionary. The keys will be category names, which are of type string:

Dictionary<string,?>

However, what should the type of the values be? Well, they will be functions that take an item of type T and return a bool (true or false) depending on whether the item is in that category or not. There is a delegate in the .Net class library named Predicate<T> that specifies this type of function. Therefore, our parameter's type will be:

Dictionary<string, Predicate<T>>

Meaning that our full method declaration is:

public static Dictionary<string, List<T>> Divvy<T>(
    this List<T> TheList,
    Dictionary<string, Predicate<T>> Categorizers)
{
    // Implementation goes here.
}

You'll be glad to know that the implementation is simpler than the signature.

Initializing The Result Dictionary

Before we start categorizing the items, we need to set up the result Dictionary. We'll instantiate a Dictionary with the same type as the return type we worked out earlier. Then we will loop over the keys of the Categorizers parameter, which are the names of the categories, and create mappings in the Result dictionary from the names to empty Lists.

var Result = new Dictionary<string, List<T>>();
foreach (var Category in Categorizers.Keys)
    Result.Add(Category, new List<T>());

Divvying Up

Finally, we get to the code that's going to do the real work, and it's actually really quite straightforward.

foreach (var Item in TheList)
    foreach (var Category in Categorizers.Keys)
        if (Categorizers[Category](Item))
        {
            Result[Category].Add(Item);
            break; // Since we've divvy'd it into a list.
        }

The outer loop iterates over each item in the List that we were invoked on. The inner loop iterates over the names of the categories. The only slightly tricky part is the condition. Remember that the keys of the Dictionary are actually Predicate<T>s - functions that will return a bool when passed a value of type T. So we just call that function, passing the current Item as a parameter. If it returns true, then we know the item is in the current category. We add it to the correct result list, and then break. This takes us out of the inner loop, and we continue onto the next item in the List.

Putting it all together

Here's the Divvy method as a whole.

public static Dictionary<string, List<T>> Divvy<T>(
    this List<T> TheList,
    Dictionary<string, Predicate<T>> Categorizers)
{
    // Initialize result dictionary of lists.
    var Result = new Dictionary<string, List<T>>();
    foreach (var Category in Categorizers.Keys)
        Result.Add(Category, new List<T>());

    // Go through list items and divvy 'em up.
    foreach (var Item in TheList)
        foreach (var Category in Categorizers.Keys)
            if (Categorizers[Category](Item))
            {
                Result[Category].Add(Item);
                break; // Since we've divvy'd it into a list.
            }

    // And that's it.
    return Result;
}

Looking Back At The Call To Divvy

Let's take another quick look at the call to Divvy to better understand what is going on.

var GradeScores = Scores.Divvy(new Dictionary<string, Predicate<int>>()
{
    { "Grade A", x => x >= 85 },
    { "Grade B", x => x >= 70 && x < 85 },
    { "Grade C", x => x >= 50 && x < 70 },
    { "Fail",    x => x < 50 }
});

Here we are using two features of C# 3.0: collection initializers (tutorial here) and lambda expressions (tutorial here). First we instantiate a new Dictionary, with keys of type string and parameters of type Predicate<T> - exactly what we declared the Categorizers parameter of Divvy to be. Then we use a collection initializers to specify a list of key/value pairs. Each goes in curly brackets, separating the key from the value by a comma. Therefore, "Grade A", "Grade B" and so on are keys.

The values are lambda expressions. If you read where "=>" as "where", you can read the first one as, "x where x is greater than or equal to 85". Note that we are declaring x here - it is just a parameter name. Remember that a lambda expression declares an anonymous method (or function), and what comes to the left of the => is a parameter list. "x =>" declares the x, and "x >= 85" uses it.

Aye!

And that's your lot. Enjoy divvying up your lists, and I'm off to tuck into a nice Yorkshire pudding.

Higher Order Programming Is Easy!

pheaven — Tue, 22 Jan 2008 07:09:07 -0700

Higher Order Programming is one of those things that to many people sounds weird, magical, mysterious or just too hard for them to be able to do. It's not. If you have ever passed a function or method as a parameter to another function or method, then you have done higher order programming. If you have ever used a function pointer in C or a delegate in C# or some kind of callback mechanism, then you have done higher order programming.

Define it!

We are all used to writing code that takes parameters. We do it whenever we write subroutines, functions or methods. Normally these parameters are data. In higher order programming, one or more of these parameters is code rather than data. That is, you can pass code, functions and/or methods around, just as you can pass data around. That's all there is to it.

Show me an example

Let's look at C#, because the syntax will not be too unusual to programmers in many languages. Suppose we have a List of scores for a test.

var Scores = new List<int>() { 2, 7, 9, 5, 6, 10, 8 };

We want to get all scores that were considered passes. Suppose the test is out of ten, and to pass you need to get more than half marks. We can write a method to determine whether a score is a pass and that returns a boolean (true or false value).

public bool Pass(int Score)
{
    return Score > 5;
}

Then we can use the FindAll method to find all scores that were considered passes.

var Passed = Scores.FindAll(Pass);

Notice what we have done here. We did not call the Pass method ourself. Instead, we passed the Pass method to the FindAll method as a parameter. Internally, it looped over the values in the list and called the Pass method on each of them, and put those that it returned true for into a new list and returned it.

You are probably now thinking, why go to all the trouble when I could have just written a loop? And it's true - you could have written a loop that did the test in an if statement and build a new list.

var Passed = new List<int>();
foreach (var Score in Scores)
    if (Score > 5)
        Passed.Add(Score);

However, step back and think about what we just achieved from a software engineering perspective. It is a well known principle that separation of concerns helps to reduce code complexity. Here we have separated the concerns of:

Testing each element of a list and building a new list of elements that passed the test

The test itself

Therefore, higher order programming is a tool that enables us to reduce our code complexity by separating concerns, and also increase code re-use along the way.

Code without a name

You might be thinking, "huh, I just wrote more code than I would have; I had to define a whole extra method!" You can also argue, quite reasonably, that we have actually made the program harder to understand now too, because you have to go and find the Pass method to fully understand the code.

While sometimes we may have complex conditions that we wish to re-use in many places in our program - in which case writing a separate function or method is the right thing to do - in this case it would be nice if we could take advantage of higher order programming without having to resort to writing a separate method.

Enter anonymous methods, or lambda expressions. These allow you to define a method (or function, depending on your language) without a name and inside another method. Let's re-write the previous example using a lambda expression.

var Passed = Scores.FindAll(Score => Score > 5);

The "=>" is the syntax for defining an anonymous method in C# 3.0. Anything to the left of it is a parameter that the method takes. In this case, it takes a single parameter named "Score". To the right of it is the body of the method, with an implicit "return" (that is, it will return the boolean result of testing whether its parameter Score is greater than 5).

You could read the "=>" quite nicely in this case as "where". That is, "find all scores where the score is greater than five".

Yes, you can return code too

Suppose that I want to work out how many scores got different grades. For example, Grade A was given for scores between 8 and 10, Grade B for given for between 5 and 7, and so forth. We could write:

var GradeA = Scores.FindAll(Score => Score >= 8 && Score <= 10);
var GradeB = Scores.FindAll(Score => Score >= 5 && Score <= 7);

However, it would be nice if we could make something that read more clearly, such as:

var GradeA = Scores.FindAll(Range(8,10));
var GradeB = Scores.FindAll(Range(5,7));

How could this work? Well, FindAll expects a method that takes an int and returns a bool. This type of method - that is, a method with that signature - has a name: Predicate. Therefore, the Range method needs to have a return type of Predicate (actually, Predicate<int>, which means that the parameter it takes is of type int).

public Predicate<int> Range(int LowerLimit, int UpperLimit)
{
}

And what do we write inside the Range method? Well, we return an anonymous function that takes a single parameter and tests if it is squeezed between the two values we supplied as parameters to the Range method.

public Predicate<int> Range(int LowerLimit, int UpperLimit)
{
    return x => x >= LowerLimit && x <= UpperLimit;
}

And that's it.

What languages support this?

Here's the stinger: not all languages support these kinds of programming techniques. C# started out with the ability to do higher order programming, but without anonymous methods. In C# 2.0 they introduced anonymous methods, but with a fairly cumbersome syntax. In C# 3.0, they introduced the nice "lambda" syntax that I have shown here. Essentially, the language designers have realized more and more the value of higher order programming and worked to make it as easy as they make object oriented programming. The C# of today is a truly multi-paradigm language.

Many of the dynamic languages provide good support for this, including Perl, Python and Ruby. C enables it through function pointers, though there's no anonymous method or lambda style syntax. Java, however, has so far chosen to stick to its object oriented roots rather than embracing the multi-paradigm approach. We'll leave arguing about whether that's a good or a bad thing for another time. And primarily functional languages, such as ML and Haskell, make extremely heavy use of higher order programming techniques.

Taking it further

The examples I've shown here are trivial, but they are enough to give you a taste of what higher order programming is about. Try writing some code like this yourself, or reading up on higher order programming in a language of your choice. And when you're trying to work out a good way to get better code reuse and reduce code complexity, keep it in mind as one of the tools in your toolbox, alongside the other paradigms (such as object oriented programming, procedural programming and generic programming) that you are probably already more familiar with.

Functional programming: what’s it all about?

pheaven — Mon, 03 Dec 2007 02:35:32 -0700

Most programmers today will be familiar with a number of programming paradigms. The age-old procedural programming paradigm, where a program is broken down into a number of procedures or routines, is still very much alive and the right solution for a number of problems. Object Oriented programming is one of the most popular and fashionable paradigms today, allowing for a good level of code re-use through mechanisms such as instance management (one class can be instantiated many times to give many objects), data hiding (think private variables in a class) and inheritance.

Another paradigm cross-cuts these two: that of imperative programming. This simply means that a program consists of a sequence of instructions that are executed one after the other (or at least appear to be; both the compiler and the CPU may well re-order instructions to improve performance when it does not affect the behavior of the program). In fact, when I was younger my definition of a computer program included the words “a sequence of instructions”.

At that time, probably like many programmers today, I hadn’t been exposed to any programming languages that worked differently to this. Java, C#, all of the many dialects of Basic, Pascal…all of these frequently used languages are imperative. This is not a bad thing; in fact, it’s psychologically comfortable for us as humans, since we tend to plan how to achieve a task by breaking it down into a set of steps or follow sequences of instructions ourselves (for example, when making food).

Today I’m going to talk a little about functional programming. If you’ve seen it before this may be nothing new. If you have not, then hopefully it challenges a few assumptions you may have made about programming and arms you with another approach to solving some problems. Just as you can fake out object orientation somewhat in languages without direct OOP support, you can use functional techniques in some non-functional languages.

ML

It is going to be useful to have a language to provide examples in. I have selected the Standard ML language, and you can download the Moscow ML interpreter for free, should you want to try some of the examples for yourself.

Yes, functional programming uses functions

A function takes one or more parameters and, based upon them, computes a value. This is sounding somewhat like procedural programming so far, but remember that we’re not supposed to be writing our programs as sequences of instructions. Instead, we will write programs by writing functions that call other functions to build up their result.

Let’s start off with a simple example: the function double, which multiplies a number by 2.

- fun double(x) = 2 * x;
> val double = fn : int -> int

The “-“ is the prompt in the Moscow ML interpreter. The rest of the first line is what I typed to define the function. The “x” in the brackets is the name of the parameter the function takes. Following the “=” is the computation that the function performs: multiplying the value passed as the parameter “x” by 2. I can apply this function to a value, for example the number 21:

- double(21);
> val it = 42 : int

Giving the answer 42, surrounded by words of cryptic wonder. But what on earth are these responses that the ML interpreter gives us?

An Aside On Type Inference

After I specified the function “double” the ML interpreter gave me a somewhat cryptic looking response.

> val double = fn : int -> int

Notice that I did not specify the type of the parameter “x” or the type of the function “double”. Instead, ML has worked out the type of the function for me. Intuitively, it has looked at the function, seen that we have multiplied the parameter by an integer (type “int”) and therefore inferred that the parameter “x” must be an integer too, and that the overall result of the function is also going to be an integer. It has therefore given it the type “int -> int”, the arrow symbol “->” denoting that this is a function type (rather than just the type of a simple value, such as the number 42 with just has type “int”) that takes a value of the type to the left of the arrow and returns a value of the type to the right of the arrow.

This is called type inference. Type inference is a process by which a compiler can determine the types of your variables and functions. This is unlike languages like C, C# and Java, where we write the types ourselves and the compiler just checks them. It is often (but not always) found in functional languages. The type that is inferred will always be displayed after a colon.

It’s worth noting that functional languages often have elaborate type systems, and if you want to really understand a language like ML then you have to understand the type system too. We’re simply using ML to understand functional programming here, so we will put the type system aside for today.

Composing functions

I said earlier that we build functions up from other functions. Here is an example of us defining a “triple” function in terms of the double function:

- fun triple(x) = x + double(x);
> val triple = fn : int -> int

We can see something in this program, however, that does not appear to be a function – the “+” operator. In other functional languages, you would be forced to write something more like:

+(x, double(x))

ML provides some nicer syntax, but conceptually you can think of it as just that – syntax that really maps to calling some addition function. In fact, if we have a language that only gives us functions (and no other built-in data types, such as the integers), it is possible to write a program to perform any computation that you would be able to in any other language you might have worked in. This property is called Turing Completeness, and I mention it here so you can see the true power of functional programming. Of course, a language with no basic data types would be impractical for any real world usage.

Name Binding – Liberation From Assignment

In a pure functional programming language, the concept of assigning a value to a variable does not exist. That is, there are no storage locations. When I have been using the “=” operator, it has not been doing assignment; instead, it has been doing something known as name binding. I can, for example, write the following code:

- val a = 21;
> val a = 21 : int
- triple(a);
> val it = 63 : int

You may be thinking “there is a storage location with name a”, but actually the correct way to think of this is “the name a is bound to the value 21”. When I use “a” as the parameter for the function “triple”, it is as if the value “21” is textually substituted in for “a”. If I later write the following:

- val a = "badger";
> val a = "badger" : string

Then the name “a” is now bound to the string value “badger”. Notice that the result of this is to give “a” a different type. This is fine because “a” does not refer to some storage location of a given type, it is just a name that refers to a value. To really make the semantics clear, consider this example:

- val multiplier = 5;
> val multiplier = 5 : int
- fun multiply(x) = multiplier * x;
> val multiply = fn : int -> int
- multiply(5);
> val it = 25 : int
- val multiplier = "badger";
> val multiplier = "badger" : string
- multiply(5);
> val it = 25 : int

Everything is as expected for the first six lines. However, when I re-bind the name “multiplier” to the string “badger”, the “multiply” function continues to use the value that the name was bound to when it was defined. Therefore the outcome of the multiply function does not change. This behavior is very different to the behavior you would get with assignment.

Having modifiable storage locations actually makes programs harder to reason about formally and to understand intuitively. Most programmers have learnt not to use global variables unless they really need to, since they can be modified by any part of the program at any point in time. Even the best C programmers have likely screwed up with pointers and spent hours tracking down the resultant problems at some point. It’s clear that assignment has its issues, and that getting away from it can help.

I’m not by any means saying that name binding is a good answer for all problems. Indeed, ML does provide you with references and a mutable (modifiable) store. Sometimes you need that for performance, or now and then because doing without it is just plain hard. You can comfortably write a lot of programs free of assignment, however.

Name binding is hard to take to everyday languages because they don’t really do it a great deal. Where they tend to do it, at least conceptually, is when passing parameters to a procedure or method. We can probably learn that assigning to parameters is a bad idea. I really don’t want to advocate not using any variables in a procedure and just expressing it entirely in terms of the parameters, but it follows that shorter procedures will need to introduce less extra variables. Writing many shorter procedures or methods rather than a single big long one has been common advice for ages anyway, though.

Recursion Replaces Iteration

The fact that there is no mutable storage means that loops as they exist in non-functional languages are not really possible. There is no way to have a counter for a for loop, for example. Therefore recursion tends to be used in its place. For example, we can re-write the following loop (written in pseudo code):

for i = 1 to x
    sum += i
next i

As the following functional program using recursion:

- fun sumfirst(x) = if x = 0
                    then 0
                    else x + sumfirst(x - 1);
> val sumfirst = fn : int -> int
- sumfirst(10);
> val it = 55 : int

A common response to this is that “recursion is slow”. This is true, but if we re-organise the program to maintain and pass on a running total:

- fun sumfirst(x,t) = if x = 0
                      then t
                      else sumfirst(x - 1, t + x);
> val sumfirst = fn : int * int -> int
- sumfirst(10,0);
> val it = 55 : int

Then the result of calling the function, in the recursive case, only depends on the function “sumfirst” itself. Therefore ML is able to make an optimisation called a tail call. This means that instead of making a new call frame, we re-use the current one, since it is no longer needed. This makes the program run faster than a recursive program normally would and, most importantly, it will not build up a large call stack and use a lot of memory. (While on the subject, Parrot, a virtual machine for dynamic languages, has a JIT compiler that can spot tails calls and sometimes can optimize them to loops at the machine code level, meaning recursively defined functions can be as fast as their loop-based counterparts.)

A recursive solution to a problem can often be very elegant, though be aware that tail calling isn’t implemented in many non-functional languages. Interestingly, the .Net CLR supports it.

List Processing and Pattern Matching

We can introduce a list containing the numbers from one to ten like this:

- val onetoten = [1,2,3,4,5,6,7,8,9,10];
> val onetoten = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : int list

A list, unlike an array, is not mutable. We do not index into it at a certain point as we would with an array; instead we recursively move through the list. We can use the “cons” (written “::”) constructor to break a list into its first element (called the head) and the rest of the list (called the tail). The following function extracts the head of the list:

- fun head(h::t) = h;
! Toplevel input:
! fun head(h::t) = h;
!     ^^^^^^^^^^^^^^^
! Warning: pattern matching is not exhaustive
> val 'a head = fn : 'a list -> 'a
- head(onetoten);
> val it = 1 : int

We have been given a warning here, which cryptically tells us that we did not specify what to do in the case of an empty list. This means that we will get an exception if we try to pass an empty list to this function:

- head([]);
! Uncaught exception:
! Match

We may choose to return zero when the list is empty:

- fun head(h::t) = h
    | head([])   = 0;
> val head = fn : int list -> int
- head(onetoten);
> val it = 1 : int
- head([]);
> val it = 0 : int

The vertical bar introduces a highly powerful technique called pattern matching. You can think of it somewhat like overloading methods with the same name and different parameter lists. However, we specify all of the behaviors within the one function – only writing the name once. Here we use pattern matching to specify what to do in each of the possible cases: when there is an element in the list that we can extract and when there isn’t (one of which must always be the case). Inductive proofs of program correctness can often quite closely follow the structure of code like this.

Programs And Data Are Equivalent

Many programmers like to keep their program and the data it works on separated in their mind. We have variables that hold data and we pass them to procedures or methods that make up the program. In functional programming, however, functions are just another form of data too. That is, you can pass a function as a parameter to another function. We already saw this the other way round earlier, when I stated that you could encode any other data type (such as the integers) just using functions.

Some of the most useful examples involve dealing with lists. Let’s take our previous list of the integers between 1 and 10.

- val onetoten = [1,2,3,4,5,6,7,8,9,10];
> val onetoten = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] : int list

Now suppose I wanted to extract just the even elements of the list; I could write the following function:

- fun justevens ([])    = []
    | justevens (x::xs) = if x mod 2 = 0
                          then x :: justevens(xs)
                          else justevens(xs);
> val justevens = fn : int list -> int list
- justevens(onetoten);
> val it = [2, 4, 6, 8, 10] : int list

I could define a function to get just the odd elements of the list in a similar way:

- fun justodds([])    = []
    | justodds(x::xs) = if x mod 2 = 1
                        then x :: justodds(xs)
                        else justodds(xs);
> val justodds = fn : int list -> int list
- justodds(onetoten);
> val it = [1, 3, 5, 7, 9] : int list

However, we’ve now duplicated all of the code that moves through the list. It would be good to separate the condition that we want to use when choosing items from the list from the code to move through the list. We start by writing two “predicate” functions (a fancy name for functions that return a boolean) that will test whether a single integer is even or odd:

- fun iseven(x) = x mod 2 = 0;
> val iseven = fn : int -> bool
- fun isodd(x) = x mod 2 = 1;
> val isodd = fn : int -> bool
- iseven(2);
> val it = true : bool
- isodd(2);
> val it = false : bool

These return true or false depending on whether the number is even or odd. We will now write a function that takes a list and one of these predicate functions and uses the predicate to decide whether the element should be in the result list.

- fun filter([], p) = []
    | filter(x::xs, p) = if p(x)
                         then x :: filter(xs, p)
                         else filter(xs, p);
> val 'a filter = fn : 'a list * ('a -> bool) -> 'a list

We can now pass the “iseven” and “isodd” functions to the “filter” function. Then, when we call “p”, passing it the parameter “x”, it will call whatever function we passed. In fact, if you were to substitute the body of “iseven” or “isodd” in place of “p”, you’ll find that we get back to the same code as we had for the original two “justevens” and “justodds” functions we wrote earlier. The behaviour is the same, too:

- filter(onetoten, iseven);
> val it = [2, 4, 6, 8, 10] : int list
- filter(onetoten, isodd);
> val it = [1, 3, 5, 7, 9] : int list

However, our program is now shorter and exhibits better code re-use. A function that takes another function as a parameter is usually called a higher order function. When you are using this kind of technique, you are doing higher order programming.

Anonymous Functions

Anonymous functions are also commonly used in functional programming. That is, you can define a function without giving it a name. The syntax for this is “fn parameter list => body”. In the following example we define and pass a predicate function that checks if the value is less than 5.

- filter(onetoten, fn x => x < 5);
> val it = [1, 2, 3, 4] : int list

The ability to pass functions is one of the most useful techniques we can lift out of functional programming, and many languages have. C and C++ had function pointers. C# 1.0 had delegates, C# 2.0 introduced anonymous methods and C# 3.0 introduces syntax almost identical to the ML anonymous function syntax shown here. Perl, Python and Ruby all allow for higher order programming too.

So What Have We Learnt?

Functional programming isn’t scary nor solely for academics. It provides some pretty neat ideas, and the languages that most programmers are used to working in are starting to incorporate them. Here’s a summary.

Writing a sequence of instructions isn’t the only way to write a program.

A programming language that only had functions and nothing else would be totally impractical but you could still write any program in it that you wished.

There is life without variables and assignment.

Recursion can replace iteration, and with tail recursion that can be efficient.

Lists are a way to do array like stuff in a functional language, and free us from worrying about bounds checking.

Pattern matching is mighty and powerful and makes functional languages great for writing compilers. And writing compilers is fun and good for the soul, right?

Higher order functions are making their way into everyday languages and can improve code re-use.