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 …
brain driven development 