Functional Scala: Curried Functions and spicy Methods

Welcome back to another episode of functional Scala!

As said some time before, we’ve by far not reached the end when it comes to all those basic concepts of functional 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 arguments to some other functions. You may remember our function filter, which not only takes a list of elements to be filtered, but also a function (a so called predicate function, resulting into a boolean value) which decides for every list element to be in the filtered list or not.

In this episode, we’ll see that we’re not only restricted to accept another function as an argument but could also come up with some sensible functions which may return another function as their result. Again, this is nothing special if you look at a function as an ordinary value which can be passed around like any other value of any other type. While on that road, we’ll naturally discover how that idea is closely related to what’s called function currying. So hold on, you’ll see what’s that all about in the next minutes …

Game of sight

Let’s pretend we wanna write a ‘Game of sight’. Within that game, it’s critical to detect if a certain object is within a certain area so that it’s visible or just not (hence invisible). To keep things easy, let’s play that game on a two dimensional area which can be described using a cartesian coordinate system. Further, let’s use a circle (described as a center with a radius) and a simple point on that coordinate system and try to calculate if that point (as a representative for the position of an object) is within that circle (hence visible from the center of that circle) or just outside of that circle (hence invisible from the center of that circle).

Business Player

First, what about defining our main actors in that game? Sounds good? Let’s start with a simple point. All we need is an algebraic datatype which just denotes a point within our two dimensional coordinate system:


case class Point( val x :Int, val y :Int )

As you’ve might seen, we’ve annotated our constructor parameters with val, making absolutely clear that a point is an immutable value (hence, we can’t mutate a given point, but only deriving new points from existing points, e.g. for moving the position of an object). From here, it’s just a very short jump to come up with the definition of a circle. It’s just a point to depict the center of that circle and a certain radius. That’s all for describing a full featured circle in our game world:


case class Circle( val center :Point, val radius :Int )

(Pre-) Requisites

Before we get down to our initial question, what about some small functions in order to warm up? Let’s say we wanna completely exclude the use of Scala’s object oriented features and hence don’t wanna call a Circles getter methods in order to retrieve its center or radius. Hugh? But how we’re supposed to get those fields then? Well, we could leverage Pattern Matching in order to retrieve a circles components. Observe:


val radius : Circle => Int
    =
    circle => {

        val Circle( center , radius ) = circle
        radius
    }

What we have here is a so called selector function. In fact, you could see the constructor as a function which takes some arguments and creates a new value of the given type. Then, a selector is nothing else than another function which takes such a constructed value and picks a certain component from within that value. In our case, we did that with a certain form of pattern matching: we just introduced a new value by revealing all its components with a name (center and radius). Those are then bound to the actual values of the given circle. In fact, we could’ve make use of our famous underscore for the first component, since we’re only interested in the radius here.

With that knowledge on board, it’s rather easy to come up with a selector function for the center of a circle:


val center: Circle => Int
    =
    circle => {

        val Circle( center , _ ) = circle
        center
    }

Given those two key players and our two selectors, we only need to come up with an idea on how to detect if a certain point is within the area of a certain circle. There’s a simple solution, thanks to the genius of Pythagoras …

Two points and a distance to go

It turns out, that the Pythagorean theorem is a perfect model for calculating the distance of two points (with the center of our circle as the one and the point in question as the other point) in a cartesian coordinate system (what a fortunate coincidence, since our game’s based on such). If the distance is shorter than the radius of our circle, then the point in question is clearly within the circle (otherwise not).

As you can see from the picture, we simply need to calculate the difference of our two points both x-coordinates and the same with both y-coordinates to come up with the length for the adjacent and the opposite leg (with the distance between our two points as the hypotenuse then). Then the only thing left to do is to solve the famous equation a² + b² = c². If the point in question is within the circle (or on the circles edge), then a² + b² need to be smaller or equals than radius².

Let’s pour our hard earned knowledge into a Function:


val isWithin : ( Circle, Point ) => Boolean
    =
    ( circle, point ) => {

        val Point(a, b) = center( circle )
        val Point(x, y) = point

        pow( x-a, 2 ) + pow( y-b, 2 ) <= pow( radius( circle ), 2 )
    }

Aaahh, a neat function which takes two arguments – a circle and a point, resulting into a Boolean value which indicates if the given point lies within the circles area. Again we’re leveraging pattern matching to reveal the x- and y-coordinates of the given center and point. We then simply utilize our knowledge about Phytagoras for the final answer.

With our new function at hand, let’s just try some scenarios:


val observerView = Circle( Point( 2, 2 ), 3 )

val observesFirstPoint = isWithin( observerView, Point( 3, 4 )               // => true

val observesSecondPoint = isWithin( observerView, Point( 2, 2 )         // => true

val observesThirdPoint = isWithin( observerView, Point( 6, 6 )            // => false

val observesFourthPoint = isWithin( observerView, Point( 8, 2 )         // => false

Wow, our function seems to work … but at what price?

Spicing up a tasteless Function …

If you take a closer look at our scenario, there might be a little annoyance which comes into mind. We always want to know if different objects (points) become visible to always the one and same observer (circle). So we always need to pass the same circle to our function, over and over again. Even worse, since our function does not know, that we’re always passing the same circle, it also calculates the quadratic power of the circles radius over and over again, which might be a waste of resources.

Can we do better? Yes we can! What if we could say ‘here’s a (fixed) circle. Now provide me a function which always calculates if an arbitrary point is within the area of that (fixed) circle’ ? As a little hint, think about our bronze bullet – those higher order functions. I bet your bell’s already ringing, right? What we need is a function maker, a function which produces (and returns) another function! Hey, and as we know that functions are nothing special or better than values of other types, let’s do it:


val isWithin : Circle => ( Point => Boolean )
    =
    circle => {

        val radSquare = pow( radius( circle ), 2 )
        val Point(a, b) = center( circle )

        point => {

            val Point(x, y) = point

            pow( x-a, 2 ) + pow( y-b, 2 ) <= radSquare
        }
    }

Oh boy, not so fast! Let’s anatomize what we have here and strip it down to its single pieces! The first interesting element is the type signature, given at line 1. The type says that we have a function which just takes a single circle (before the first function arrow) and results into something we’ll inspect in a moment (all within that round brackets after the first function arrow). So we have clearly a function in front. Now take a closer look at the type of the functions result (all inside that round brackets). But look, it must be again a function, taking a single Point and resulting into a boolean value! Clearly, the whole construction must be our function maker!

Let’s inspect how it’s going to produce that function. We can detect it as the last expression (which also becomes the return value in Scala automatically) within the body of our function maker, beginning at line 8 upto line 13.  This function only takes a single point and then starts our well known calculation. An instance (value) of that function is created whenever our function maker is called with a certain circle. And since this ad hoc created, resulting function is anonymous (look, it even lacks a name) it must be a … tataaa … lambda expression!

But wait, where come those values like x, y or even radSquare? Since those values aren’t defined as arguments of our resulting function, we have some free variables which only got bound by closing over into the lexical scope where the function is created (that is the body of our function maker, were we’ve calculated the square of the circles radius only once). So the delivered function must be a … tataaa … closure!

Now let’s look how we could bring our function maker into use:

val observerView = Circle( Point( 2, 2 ), 3 )

val observes : Point => Boolean = isWithin( observerView )

val observesFirstPoint = observes( Point( 3, 4 ) )

val observesSecondPoint = observes( Point( 2, 2 ) )

val observesThirdPoint = observes( Point( 6, 6 ) )

val observesFourthPoint = observes( Point( 8, 2 ) )

Please direct your attention to line 3, where we just called our function maker isWithin which returns another function observes which in turn can be used further on to test if all those arbitrary points lie in the area of the predefined circle (which is kind of fixed within the resulting function observes)! Of course we could still use our function maker and the resulting function in one go:

val firstObserverView = Circle( Point( 2, 2 ), 3 )

val obervedByFirst = isWithin( firstObserverView )( Point( 3, 4 ) )

...
val secondObserverView = Circle( Point( 17, 21 ), 5 )

val obervedBySecond = isWithin( secondObserverView )( Point( 23, 17 ) )

So if we want to use our new construction just once for different circles, we can just apply that circle to our function maker, which in turn results into our function for doing the final calculation, which in turn is immediately applied to the given point. Since we do two function calls in a row, we provide those two arguments (one for each function) within two different argument lists.

Where’s the curry, mom … ?

Now, look where we’ve come from. We started with a function, taking two arguments, resulting into a boolean value:

( Circle , Point ) => Boolean

We then massaged that function into another function which we called a function maker. Now if you look at the type of that higher order function, you’ll see that they are not so different from each other:

Circle => Point => Boolean

I’ve omitted the round brackets – they’re not needed since our function arrow is right associative (of course you can always keep the brackets for your own clarity). So if we look at the players of both types, they’re the same! Further, given the same circle and point, the final result also remains the same, no matter if you call the first or second version. We’ve only translated the first version which takes two arguments (a circle and a point) into a version which is taking a single argument (a circle), resulting into another function which in turn takes a single argument (a point), resulting into a boolean.

We could generalize this idea, taking any function with an arbitrary number of arguments and translate it into a function which just takes the first argument, resulting into a function which just takes the second argument, resulting into another function which just takes the third argument, which … (you get the idea) … resulting into the final result.

This transformation process is well known in the functional world where it deserves its own name. It’s called ‘Currying‘ (according to the name of Haskell Brooks Curry, a famous mathematician and logician). The result of currying a given function is then called a curried function. In fact, this kind of transformation could be done in a pure mechanical way. Let’s try to define a function curry, which takes a function of two arguments and returning a curried version of it:

def curry[A,B,C]( func : (A, B) => C ) : A => B => C    =    a => b => func( a, b )

Wow, let’s take a closer look at it. First of all, we need to fall back to a method definition (starting with a def), since Scala doesn’t support polymorphic functions: because we wanna preserve the given arguments and return types of the function to curry, we need to introduce those types as type parameters. Now look at the  argument func of method curry: it’s a function, taking two arguments (of type A and B) resulting into a value of type C. The curried version of such a function would be a function taking a single argument of type A, resulting into another function which in turn accepts a single argument of type B, finally resulting into a value of type C. But look at the return type of our curry method – it’s exactly of that type – hurray!  In fact, the method body can’t do anything other than what the return type already predicts …

Now we could use our new function curry in order to apply it to our inital version of isWithin

val isWithin : ( Circle, Point ) => Boolean = ...

val curriedIsWithin : Circle => Point => Boolean = curry( isWithin )

So this kind of mechanical currying is surely a no brainer. It’s so no brained, that it’s of course already provided within the interface of Scala’s FunctionN types:

val isWithin : ( Circle, Point ) => Boolean = ...

val curriedIsWithin : Circle => Point => Boolean = isWithin.curried

You’ve surely already noticed, that this kind of mechanical currying is only able to solve the problem of not handing a circle (as the first argument) to our function over and over again. It simply pulls the arguments apart, providing a chain of nested function makers which only take one single argument each. Of course it can’t provide any optimization, e.g. calculating the square of the circles radius only once, serving as a value to close over.

Summary

Within this episode, we transformed a given function by hand: we took a function with more than one argument and massaged it into a function (we called it a function maker) which always took a single argument at a time, resulting into another function until there’s no argument left, resulting into the final result. Again, we saw that functions are nothing better than ordinary values which can be produced and returned by other (then higher order) functions.

We also saw that this kind of transformation can also be done in a more mechanical way, but then lacking some more intelligent separation strategies like optimization of resource usage. Either way, that transformation process is so prominent in the functional world, that it’s marked with an own name: Currying. We’ll see some more interesting usage scenarios of Currying and its result – curried functions – in some future episodes.

So far we only used Currying on functions. But what about methods? Is there a similar way to produce some kind of curried methods where we could provide only one (or some) arguments at a time? And if so, can we also apply some optimization strategies like we did with our function isWithin or use a function curry to transform a method into a curried one? If you’re eager to know, that’s good!  We’ll solve all those questions in the next episode. Would be glad to see you again …


Side Note
The idea of transforming a function with multiple arguments into a curried one was not invented by Haskell Curry. Curry was only the one which popularized the idea in the field of combinatory logic. The initial idea came from a russian mathematician of name Moses Schönfinkel. So whenever to use Currying, we should not forget about Moses! At least, i guess not calling the process after him, is that Schönfinkeling doesn’t sound that good …

There’s no average, dumb Java Joe!

Wow, it’s been quite a long time since i’ve blogged the last time (that’s for the one or other reason that would only bother you, so in essence – please excuse) . But now i can’t keep calm any longer, since there’s an increasing number of articles, claiming that e.g. Functional Programming – in particular using Scala – is too hard to get for the average programmer.

First of all,  there isn’t any ‘Java Joe’  (as a synonym for all those so called ‘dumb’ Programmers) out there. Well ok, if it is, then i’m the ideal protoype of that Joe! And as such  i can tell you, if you’re willing to learn some new ideas and try to improve your programming skills, than Scala may provide you with a bunch of whole new concepts, not only from the functional world (and i’m not even talking about type systems here).

In fact, i don’t care if it’s Scala, Haskell or any other language, as soon as it may widen my horizon. But i would answer to all those who think Scala is to hard to grasp, that it’s only a matter of how you would pick up those persons. Granted, it may be difficult to meet those ‘newcomers’ at their common ground – there are some complaints out there that some Scala community members might behave too elitist when it comes to blaming Scala as being too difficult (like ‘it’s not Scala which is too difficult, it’s only you who don’t understand it’).

Frankly, i can follow those complaints. If you’re willing to learn and may have some problems to grasp some blog posts about Scala (or any other language) or even some code snippets, it is by way no solution to retreat to a position, saying your just to dumb (or lazy or whatsoever) to get it. Spitting out some code snippets or short articles everey now and then is easy – especially if they come without any context or any larger explanation. That’s really the easy part! The hard part is meeting that so called average Java Joe at his level and escort him intellectually!

So as a community of Scala fellows (or in any other way), we need to stop  judge over those large herd of programmers as being too dumb. That’s simply not true! There may be some individuals too sluggish to learn and excel. But for all those others, who may have a hard job and having no chance to deal and become proficient with Scala at day (and therefore have only some hours at night) , we need to provide a way of guidance. And that’s best done to face that before mentioned reality. It’s not the people who are dumb. We as a community are dumb if we don’t react to that reality and welcome those people on their ground!

Appendix

In order to walk the talk, i decided to resume my work on writing about functional Scala! Hopefully some may still find it a useful intro to get into the ideas of functional programming in Scala.

Functional Scala: Quiz with Lists – common list functions, handcraftet

Welcome to another episode of Functional Scala!

As promised within the last episode, we’re going to take another detailed look at some more commonly used list functions. As we wanna become well acquainted with the functional side of Scala, we’re again going to implement those list functions one by one. Along the way, we’ll get a better and better understanding on how to apply some of the typical tools within the world of functional programming, like pattern matching, recursion or function composition.

As it turned out, most of us learn best in a synthetical way (that is not by dissecting the frog, but to build one). For that, we’re gonna change the style of the following sections. For every useful function, we’re first looking at their intended behaviour, maybe along with some exemplary showcases. Only when we grasp the intention, we’re trying to come up with a sensible idea for their realization and finally with an implementation. You might consider the whole episode like a little quiz and try to come up with your own solutions before you’ll take a closer look at the presented ones. Read the rest of this entry »

Functional Scala: Essential list functions

In the last two episodes we came up with the basic idea of persistent (read immutable) list-like data structures and how to construct and deconstruct (read pattern match) them using a sugarized notational form. We also talked big about their non-destructive nature when it comes to e.g. updating a given list or removing some elements. In this episode, we’ll finally inspect some of those commonly used list functions. While we’re going to reimplement the most essential ones,  you’ll hopefully get a better feeling for the  basic principles and characteristics which build the foundation for operating on persistent data structures in a non-destructive way (preserving the structure of given list values). Read the rest of this entry »

Functional Scala: List sugarization

In the last episode we started to look at persistent list-like data structures. We came up with an algebraic datatype which allows to construct arbitrary lists, featuring parametric polymorphism with regard to the type of the lists content. So far, we didn’t see the non-destructive nature of those datatypes when it comes to updating a given list or removing some elements.

Bear with me. We’re going to inspect a bulk of widely accepted, commonly used list functions, operating on persistent data structures in a non-destructive way! But before, we’ll need to prepare ourself with a set of tools for an easier way of tinkering with our list-like data structure. Read the rest of this entry »

Posted in Scala. 2 Comments »

Functional Scala: Tinkerbell, Frogs and Lists

Welcome to another episode of Functional Scala!

What do you know about Frogs? Well, i mean beyond the most common facts you learn from books. One way to learn more about Frogs might be to dissect one, as you may have done back in school. That would be the analytic way. But there’s a better way: if you really want to learn about the nature of a frog, you should build one! By building a being that has froglike characteristics, you’re going to learn what makes a frog a frog and how frogs are adapted to their particular environment. It’s a perfect example of learning by synthesis!

Well, as this isn’t a series about biology but about Functional Programming with Scala, we’re going to focus on another research object, which will be list-like data structures in a functional environment. We’re going to construct a simple, functional list type and explore its characteristics along the way. So let’s start and play Tinkerbell … Read the rest of this entry »

Functional Scala: Expressions, Extensions and Extractors

Welcome back to another episode of Functional Scala.

This one is the sequel to our extended sample on representing and resolving arithmetic expressions using algebraic datatypes and pattern matching. In this second part i try to answer a legitimate question: what are the advantages and disadvantages of algebraic datatypes (consisting of pure data, no behaviour), espacially if we wanna expand our expression language  – and what’s that all to do with the visitor pattern? Read the rest of this entry »

Follow

Get every new post delivered to your Inbox.

Join 42 other followers