Functional Scala: High, Higher, Higher Order Functions

Welcome to the sixth episode of Functional Scala!

This time, we’ll finally dive into one of the most powerful concepts i consistently referred to again and again within almost every previous part of this series: Higher Order Functions. Isn’t that cool? I know it’s not, since a cool name alone can’t set you on fire. I will demonstrate you some of its coolness and show you some essential aspects which induce not few voices to accuse Higher Order Functions as one of the basic principles for elegance, compactness and efficiency in Functional Programming.

So what’s a Higher Order Function then? Is there some meta-magic in it or why they are called higher ordered? Let’s develop a sense for them by firstly focusing on a common problem: Duplication of code. Let’s start by writing a simple Function which can be applied to a list of integer values, resulting into another filtered list, containing only all even values of the incoming list:

val filterEven  =  ( xs :List[Int] )  => {

    for(  x <- xs;   if x % 2 == 0  )  yield x
}

So here you have it. A simple function, accepting a list of integer values which is then used as a generator within a comprehension. How lovely, since we already covered Scala’s modell of comprehensions within the last episode, we shouldn’t have any problems to understand what’s going on here:  While we’re running through all possible values for output variable x (coming from the generator), the given Guard will only pass such values to the output function, which will satisfy the given predicate. And the predicate x % 2 == 0 is only met by – tadaaa – even numbers.

Just for the records: the critical part for detecting all proper values which will be selected for the resulting list, seems to be the predicate which is used by that guard. The other stuff around it is just the mechanical armamentarium which will filter the good ones from the bad ones, but the crucial decision is been made by the predicate. In order to emphasize its exceptional position in this game, we could extract the predicate and put it into a function of its own:

val filterEven  =  ( xs :List[Int] )  =>  {

    val even  =  ( x :Int )  =>  x % 2 == 0

    for(  x <- xs;  if even( x )  )  yield x
}

So far, nothing really exciting happened. We’ve only extracted the predicate and defined it within a local function (we’ve already seen local functions while we’ve focussed on Closures), so we can refer to that local function afterwards within the comprehension’s guard. Again, since the comprehension expression is the last one within the function, the value of that expression is automatically the result of the whole function: it’s simply the filtered list, yielded by the comprehension.

Ok, just for fun – let’s filter a list of integer values again, but now retain all odd values of the incoming list. Since we have some experience now in writing filtering functions and it’s a real pleasurable exercise to write some more filters, this one should be business as usual and written down before i can say ‘Bob’s your uncle':

val  filterOdd = ( xs :List[Int] )  =>  {

    val odd  =  ( x :Int )  =>  x % 2 == 1

    for(  x <- xs;  if odd( x )  )  yield x
}

… and ‘Bob’s your uncle’

Wow, that was fast and really really fun! Ok, now we could write some more filters, e.g. primes, numbers between a certain range, multiples of five, numbers with a certain checksum, fibonacci numbers, natural factors of a certain number …
Sounds still funny? Well, it might be for long cold nights, where time’s not going by. But for all others with excellent sleep,  is there any way to avoid that repeating task of coming up with that repetitive filtering scaffold again and again? You surely have figured out, that the only thing that’s changing is the predicate for all those different filters. So why not abstract away the task of filtering (the pure act of separating the good ones from the bad ones) on the one side and the task of deciding which are the good ones on the other?

Too bad that we can’t separate the function which represents the predicate from the rest of the filter…
Hey, wait a minute! Didn’t we say that functions are first class values? Yep, we did! So they don’t differ from other values? Yep, they differ only in type. Apart from that they are nothing special – just like a value of type Int for example. Then also just like a value of type List[Int]? Exactly! And if we can pass a value of type List[Int] as an argument to our filter function, that means … that means …? Holy grail, you got it! That means you can also pass functions – like our predicate function – as ordinary arguments to a function!

The only question left is how we declare the predicate function as an additional argument to our filter function? We need to know the precise type of the predicate function. As an intermediate step, we could extend our last function above and annotate the type of the predicate function explicitly:

val  filterOdd = ( xs :List[Int] )  =>  {

    val odd : Int => Boolean  =  ( x :Int )  =>  x % 2 == 1

    for(  x <- xs;  if odd( x )  )  yield x
}

Ahh, as sure as eggs is eggs and as long as our predicate has to decide if a value of type Int qualifies for the resulting list (true) or not (false), our predicate function is of concrete type Int => Boolean. Now we only transfer that function (with that needed type) as another incoming value to the argument list of our filter function and be done:

val  filter = ( predicate :Int => Boolean, xs :List[Int] )  =>  {

    for(  x <- xs;  if predicate( x )  )  yield x
}

Congratulations, you’ve just created your first Higher Order Function! There’s nothing esoteric about. It’s just a function which is accepting another function as an argument. And while a function maps argument values to a result value (and just in case you’ve forgotten that a function is a value), it’s also completely legal that a function’s result may also be a function. So as soon as a function takes another function as one of its arguments or results into another function, it’s called a Higher Order Function. That’s all, folks!

You may wonder right now, why there’s all that whoopee about higher order functions. Hold on, we’ve just scratched the surface and only pushed the door open to the manifold fields of application for higher order functions (which we’ll discover in more than one of the following episodes). For now, we’ve just discovered a new tool which will turn out to be very flexible, yet powerful. If McGyver would be a functional programmer, he surely would pick it as one of his favorite tools. And you know what McGyver is able to produce even out of a simple paper-clip …

What’s left? We’ve successfully encapsulated the pure mechanics for filtering a list of integer values in one single function filter. In doing so, the filter predicate (responsible for the decision which value is kept in the filtered result list) was abstracted away into a function of its own. And while our filter function can now be parameterized with any filter predicate we want, we’re now able to refer to one and the same filter function and use it in multiple ways just by passing different predicate functions:

val even =  ( x :Int ) => x % 2 == 0
...
val odd =  ( x :Int ) => x % 2 == 1
...

val candidates = List( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 )

val evenValues = filter( even, candidates )
val oddValues = filter( odd, candidates )

Ok, one last but slightly more complex exercise for today. If you get this one, you’ll surely got all the basic aspects of Higher Order Functions!  Let’s write another filter predicate so we’re able to filter a list for primes. We will do so in at least two steps and try to leverage some of the concepts we’ve learned so far within the past episodes. First of all, let’s think about the characteritics for a number to qualify as a prime. Could we agree on the fact, that there should be no natural factor between 2 and at least the half of that number? Ok!

Now, before we get back to the prime predicate, we will write another one which will screen a list for all numbers which may be a natural factor for another, fixed integer number. Under normal conditions, we would write a function which will take two arguments; the first argument may represent an arbitrary number and the second one a possible factor for that number:

val isFactor =  ( num: Int, factor :Int ) => num % factor == 0

Too bad that we cannot use that function as a filter predicate since filter asks for a function of type Int => Boolean (while the above one is of type (Int, Int ) => Boolean). So if we want to filter a list of integer values for all factors of – say – 1oo, we need to come up with a predicate function like so:

val isFactorOfHundred =  ( factor :Int ) => 100 % factor == 0

Ok, looks good? Now we want to filter for all factors of 99, then 1000, next 1558, next … Hm, does this sound familiar?  Similarly to our filter function, we don’t wanna write a new predicate function for every number we want to filter a list for its factors. Higher Order Functions to the rescue! What about a function which will take just an arbitrary number and result into another function which will again take just another number and test if this one is a factor for the first one? Sounds confusing? All becomes quickly clear, if we look at that function in action:

val isFactorOf  =  ( num :Int ) => {

    ( factor :Int ) => num % factor == 0
}
...
val isFactorOfHundred = isFactorOf( 100 )
val isFactorOfNinetyNine = isFactorOf( 99 )
val isFactorOfThousand = isFactorOf( 1000 )

Wowowow … hold on! What is that for an artwork? Our function isFactorOf is simply a higher order one: this time because it results into another function. What you see inside its body is simply the definition of another function, which is constructed every time isFactoryOf gets called. And while that function definition is the last expression inside the function body, the value of that expression (that is the function value) is the result of the whole function. At the same time, the resulting function can be called a closure. See why? Well, num is a free variable, since it’s not declared as an argument. In this case, closing over takes place and the free variable gets bound to the argument of the surrounding function. So now we’re able to filter a list of integers for those factors of an arbitrary number:

val factorsOfHundred =  filter( isFactorOf( 100 ), candidates )

Again, nothing really exiting here. We’ve got all ingredients to fully understand what’s going on – only the first argument is of real interest: we applied isFactorOf to the value 100 which results into a function, which in turn is taking another integer value and decides if this one is a factor of 100. This ad hoc generated function is of type Int => Boolean and therefore an appropriate predicate function for filter. Now filter will use that predicate function in order to decide which number of the incoming list candidates will made it to the filtered outgoing list.

With this Predicate Function Maker on board, we can now switch back and concentrate again on our main predicate for filtering primes. Let’s reflect on how our Function Maker might help us for identifying a number as prime. We’ve got already agreement on the fact, that there should be no factor for any given number in the range between 2 and half of that number. Does this ring a bell? How can we check if there’s no factor within a collection of integer values? Well, how about filtering that collection by an appropriate predicate – let’s say only factors of that number? If the filtered list is empty, than there’s obviously no factor for that number within that range. Hence that number must be a prime:

val prime = ( num :Int )  =>  num > 1  &&  filter( isFactorOf( num ), (2 to num/2).toList ).isEmpty

Violá, here’s our predicate function, testing for prime – based on filtering – which in turn can be used for filtering …

Summary

In this episode we’ve discovered the meaning of so called Higher Order Functions. While we focussed mainly on its basic characteristics – functions which accepting other functions or returning functions – i think you’ve already got a little glimpse for their power. In fact, for many computational tasks within the world of functional programming they are indispensable (as we well see). They not only allow for new ways of abstraction (for example resource control – you may have already heard of the so called Loan pattern within Scala), kind of simulating or capturing state (as we will see when looking at difference lists) but also lay the foundation for some other well known, powerful features of functional programming (like currying, as we will also see in some future episode).


Addendum

Since Scala is a hybrid language which blends object oriented and functional features, Scala’s List type (in fact List is a type constructor, but that’s again a topic for another episode) provides a generic filter method already. That is, if you hold a list of integer values (an object of type List[Int]), you can call a method filter on that object and pass an arbitrary predicate function of type Int => Boolean (just as we did with our filter function):

val candidates = List( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 )

val evenValues = candidates.filter( even )                   // List( 2, 4, 6, 8, 10 )
val oddValues = candidates.filter( odd )                     // List( 1, 3, 5, 7, 9 )
val factorsOfTwelve = candidates.filter( isFactorOf( 12 ) )  // List( 1, 2, 3, 4, 6 )
val primes = candidates.filter( prime )                      // List( 2, 3, 5, 7 )

So if you want, this method could be called a Higher Order Method.

About these ads
Posted in Scala. 10 Comments »

10 Responses to “Functional Scala: High, Higher, Higher Order Functions”

  1. Functional Scala: Lambdas and other shortcuts « brain driven development Says:

    [...] Scala: Lambdas and other shortcuts December 5, 2010 — Mario Gleichmann In the last episode, we discovered one of the most powerful concepts within the world of functional programming – [...]

  2. Functional Scala: Turning Methods into Functions « brain driven development Says:

    [...] C’mon – this is boring. We already knew that. Yeah, i know! But the one thing i want to re-emphasize is the fact, that every concrete function always boils down to a value of a certain function type (in this case Int => Boolean). And since a function is a value, it can be assigned to a name (in this case isEven) and passed to another function just as all other ordinary values like Lists or integer values (in this case function isEven is passed to function filter, which qualifies filter to be a so called Higher Order Function). [...]

  3. Good blog post on Higher Order Functions « Let's do some scala coding Says:

    [...] http://gleichmann.wordpress.com/2010/11/28/high-higher-higher-order-functions/ Like this:LikeBe the first to like this post. Categories: Uncategorized Comments (0) Trackbacks (0) Leave a comment Trackback [...]

  4. Functional Scala: Curried Functions and spicy Methods « brain driven development Says:

    [...] programming. One of the most powerful ideas we’ve discovered so far, was that of so called higher order functions. Since functions can be treated as values (like Numbers or Strings), we can pass them as ordinary [...]

  5. Functional Scala: Curried Functions and spicy Methods « brain driven development | TechRetriever Says:

    [...] programming. One of the most powerful ideas we’ve discovered so far, was that of so called higher order functions. Since functions can be treated as values (like Numbers or Strings), we can pass them as ordinary [...]

  6. Lloyd Muccio Says:

    Very clear progression from literal to abstract. I found it very helpful.

  7. Richard Says:

    Thank you! This saved me from pulling out my last strands of hair!

  8. Minnie Says:

    I think that is one of the most important info for me.
    And i am happy studying your article. But wanna commentary
    on some general issues, The site style is ideal, the articles is really nice : D.

    Good task, cheers

  9. fibonacci Says:

    Hello my loved one! I wish to say that this article is awesome, nice written and come
    with approximately all significant infos. I’d like to
    see extra posts like this .


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 43 other followers

%d bloggers like this: