Monthly Archives: August 2016

Haskell Flavoured Curry

curry

Reading time: 10 minutes
Currying is a very useful pattern in functional programming. It is a way of breaking up a function which takes multiple parameters in to a chain of outer to inner functions, each of which, takes one parameter. It allows arguments which are known at one point in program execution to be captured and used in a later execution of a function requiring more arguments. In some ways, it’s similar to when an Object is instantiated in OO with one or more property values which are used in later function executions involving that object.

I have found that the subject of currying can be confusing for developers who are new to functional programming. It was for me at the start anyway. I used to try and relate everything back to OO but I discovered that using a substitution model approach based on the Lambda Calculus really simplified things. I won’t go into the specifics of Lambda Calculus here but I’ll give a short example of using a substitution approach in the context of understanding currying.

So, we have a function which transforms a String by prepending a certain number, n, of characters to the start of it returning a new String.

So, in pseudocode this could look like:

prepend(n, c, s) = put n c's at the start of s

Now lets execute this function:

prepend(3, 'z', "Tom")

This would result in

"zzzTom"

This function is completely pure in that it has no observable interaction with its outside context. This is extremely useful because it means that anywhere we see this function called in a program, we can substitute the call arguments into the function’s implementation without changing the meaning of our program. Functional programmers love to say “functional programming is easier to reason about” and this isn’t just a catchphrase. It is this ability to substitute arguments for parameters in expressions, along with all the other functional programming goodness like immutability, that does actually make functional programming easier to reason about.

So, using a simple substitution model, when we call

prepend(3, 'z', "Tom")

in our program, we can replace it with its implementation expression by substituting into it the arguments 3, ‘z’ and “Tom” for the parameters n, c and s respectively.

so

prepend(3, 'z', "Tom")

becomes

put 3 'z' 's at the start of "Tom"

For a curried version of this function we can break it up into three one parameter functions: (I’m using

->

here to separate a function name with its parameter and the function’s expression body – again this is pseudocode)

prependA(n) -> prependB(c) -> prependC(s) -> put n c's at the start of s

Okay, hold a while here! I know this looks kind of weird as we have three functions, starting with the outer prependA function and returning an inner function until we reach the innermost expression. This is where, before, I would have gained initial understanding by thinking about each outer closure returning its inner closure working from the outmost function, prependA to the innermost, prependC – outer to inner functions/closures is the subject of one of my earlier blogs: Closures For OO Developers – 1.
I find that trying to think in this way can start to bend the brain a little bit as higher order functions become more complex. If we look at how this works using the substitution model, things become way easier!

Okay, so lets say we know how many characters we want to prepend to a String but we don’t know what the character is or what the String is just yet. That’s okay!
We can still call our function

prependA(n)

.
So, if n is 3, we call,

prependA(3)

and substituting we 3 for n in its implementation expression, we get

prependB(c) -> prependC(s) -> put 3 c's at the start of s

Okay now, we have a function which can take, as a parameter, the character that we are prepending. At some point, we know that the character we want to prepend is ‘z’, so we call

prependB('z')

substituting z for c in its implementation expression, we get

prependC(s) = put 3 'z' 's at the start of s

Now we have a function which can take a String, s, and prepend three ‘z’ characters to the front of it to produce a new String.

At some point, we find out that the String we want to transform is “Tom” so we call:

prependC("Tom")

Now, we substitute again and this becomes:

put 3 'z' 's at the start of "Tom"

which is back to what we had when we called the original prepend(3, ‘z’, “Tom”)

Haskell likes its Curry

In the above example, I have actually shown, in a simplified way, how the function substitution would work in the Lambda Calculus.
With Haskell being an implementation of the Lambda Calculus, all functions are curried. This doesn’t mean that all functions have to be written as one parameter functions. When a function is declared with multiple parameters, Haskell breaks this up into a series of outer to inner one parameter curried functions underneath the hood. So, our prepend function from above could be declared in Haskell in a way that doesn’t look like its curried.

prepend :: Int -> Char -> String -> String 
prepend n c s = take n (repeat c) ++ s

The expression in the implementation of the prepend function above just says:
take the character, c repeated n times and stick it onto the String s to form a new String (without mutating the original String s).
The type signature is

prepend :: Int -> Char -> String -> String 

Type signatures in Haskell show the curried nature of functions with a series of types separated by

->

with the last being the return type of the function.

The prepend function above takes three parameters, n, c, and s just like the prepend function in our earlier pseudocode. However, just like how I broke this up into a series of outer to inner one parameter functions in the pseudocode, Haskell does this automatically for us.

This allows us to do some really handy stuff!

So, say we want a function to pad a String with a number of characters to the left of the String but we know that we will always want 10 characters. We can declare this as our pad10 function below.

pad10 :: Char -> String -> String 
pad10 = prepend 10

In the above code, we have simply assigned pad10 to prepend but we are only calling the prepend function with one argument, 10. Because the pretend function is automatically curried, when we call pretend 10, we get back another function which takes a character, c which in turn, when called with a character argument, will return the innermost expression which is the expression that actually does the String prepending.

We can continue with this pattern.

So, say we always want to pad a String to the left with 10 white space characters.

pad10WhiteSpaces :: String -> String 
pad10WhiteSpaces = pad10 ' '

In the Haskell code above, we again take advantage of Haskell’s automatic currying and call pad10 with 1 argument, the

' '

character. We can follow a similar substitution to our pseudocode so:

substituting

pad10 ' '

we get

prepend 10 ' '

and substituting this, we get:

take 10 (repeat ' ') ++ s

So when we call

pad10WhiteSpaces "Tom"

this substitutes to

take 10 (repeat ' ') ++ "Tom"

when executed, will produce

"          Tom"

Haskell’s automatic currying can take a bit of getting used to but it makes for beautiful code! It really shines when you want to re-use a multi parameter function to create a function that can only take fewer or even one parameter. For example, if we had a list of Strings and we wanted to produce a list of all the these same String values but with each one padded with 10 spaces. All we need is the original prepend function and this transformation would be as simple as mapping (prepend 10 ‘ ‘) over the list of Strings:

map (prepend 10 ' ') ["I", "like", "curry", "a", "lot"]

Isn’t that handy!

Executing this results in

["          I","          like","          curry","          a","          lot"]

Function Composition Is So Damn Nice in Haskell !

Reading time: 5 minutes

Haskell has some beautiful constructs and really allows for very expressive code along with maintaining strong, static typing and purity. I’ve been taking a deep dive into Haskell and the more I learn about the language, the more I’m falling for it! There are some really beautiful ways to express functional programming concepts in this language.Function composition, especially when used with point free function references, is one of them.

So, what is function composition anyway?

This is a common approach in functional programming to build a pipeline of operations by combining functions to form new functions. Its very useful in reusing existing pure functions to produce a new transformation.

e.g
f(x) = x^2
g(x) = x + 2

Functions f and g can exist on their own but maybe we want a new function which takes a number, squares it and then adds 2 to it. We don’t want to create a whole new implementation for this when the transformation in question can simply be made up of two sub transformations, the functions f and g.
So, we create a new function, call it z, which takes, the number x, calls f on it and calls g on the result of that.
So we get
z(x) = g(f(x))

Simplified expression of composition in Haskell

Functional Programming languages usually each have their own special construct for expressing the composition of functions. This can be especially useful if there are multiple functions being composed as it cuts out the need for multiple groupings of expressions. For example, if we also have the functions,

h(x) = x * 3
k(x) = x / 4

and we decide we want a new transformation to square a number, add 2 to it, then multiply it by 3 and then divide it by 4,
we end up with a composition like this:

z(x) = k(h(g(f(x))))

I know this is just pseudocode but, even still, it is becoming hard to read! And also, bear with me. I know composing transformations as simple as arithmetic is a bit contrived and could be done with just one overall arithmetic expression. The example is deliberately contrived but if you imagine a pipeline with more complex transformations like, say, processing financial trades or something, being able to break an overall transformation up into small composable transformations becomes incredibly useful!

Haskell has a beautifully simple way of expressing function composition. Lets have a look and I’ll explain the Haskell code along the way.

module FunctionComposition where 
 
f x = x^2 
 
g x = x + 2 
 
h x = x * 3 
 
k x = x / 4 
 
 
z x = k . h . g . f $ x

In the Haskell code above I have declared the four functions, f, g, h and k that I showed earlier, along with the function z which is a composition of those four. I would usually write associated type signatures with every function I write in Haskell but I have left typing out of this example to focus on the function composition construct and also an explanation of Haskell typing definitely merits its own blog post!
The function declaration syntax in Haskell is, in itself, very concise and elegant. It is simply the name that the function is being bound to followed by a space and one or more parameters, each separated by spaces, followed by = and then the expression of the function body.
So, in the case of

 f x = x^2

the name that the function is bound to is f, there is only one parameter and this is x and the expression of the function body is after the = and is
x^2

The function composition part is in the declaration of the function, z.
z x = k . h . g . f $ x

The composition is handled by the

.

in between each of the functions being combined together.

.

is in itself a function which takes which takes 2 functions, say (in pseudocode) g(x) and f(x) and returns a new function z(x) = g(f(x)). To compose up multiple functions is so simple and elegant with this simple composition function.

The

$

is just a function which applies what is on its left to what is on its right. It has the lowest precedence though so it means the function composed of f, g, h and k on its left is fully composed before being applied to x.

Also, if you prefer the reading of the sequence of transformations from left to right instead of right to left, you can simply add this just under the module declaration in the above Haskell code.

import Control.Arrow

And now, we can use >>> instead giving

z x = f >>> g >>> h >>> k $ x

What’s this “point free” thing?

Point free means expressing functions without their arguments. This may sound kind of strange for people coming from OOP or other paradigms but it actually makes for code where the reader can concentrate on the transformation that is being expressed without the code being obscured by unnecessary argument names. It is made possible in functional programming because functions can be treated as first class values and they can be bound to names just like any other values.

So, say we compose z just from the functions g and f above, the Haskell function composition would be:
z x = g . f $ x

but the x argument serves no purpose here. All we need to do is bind to z, the function which is composed of g and f. A type signature (left out here as typing is a subject for another blog post) here would serve the purpose of expressing the type of the parameter that z expects when applied. So, using the point free style the functional composition is made even more elegant and can be expressed as:

z = g . f

and composing the 4 functions f, g, h and k simply becomes:

z = k . h . g . f

Now that really is quite beautiful!

Closures For OO Developers – 2 – FP in an OO Language

Reading Time 5 to 10 minutes

In a previous blog post Closures For OO Developers – 1, I described how I initially thought about closures when I came to Functional Programming. I related an inner closure having access to the environment of the outer closure that created it as being conceptually similar to an inner object having access to the properties of the outer object that created it.

I thought I would back up a bit and show that a closure can really just be thought of as a one method object. There is a quote floating around something like “A Closure is a poor man’s object and visa versa”. I’m not sure of the exact origin of that quote but really the point is that closures and objects are almost the same thing. Closures, in a sense, when thought of as one method objects, bridge the gap between OO programming and functional programming.

It is possible to apply functional programming principles in an object oriented language using closures as one method objects even when the language in question isn’t a fully featured functional programming language. I’m going to take an example of a very common transformation in functional programming – map. This is a function over a data structure which also takes a mapping function as a parameter and applies this mapping function to each element in the data structure to create new data structure elements and, ultimately, a new data structure.

Closures to make OO more Functional

Lets have a look at how this may have been achieved with closures in Java pre Java 8. I will then show the same thing in Java 8 using Java 8 lambdas which are closures.

 
 
    public static <T, U> List<U> map(List<T> list, Mapping<T, U> mapping) { 
 
        List<U> result = new ArrayList<U>(); 
        for (T elem : list) { 
            result.add(mapping.apply(elem)); 
        } 
        return result; 
    } 
 
 
    private interface Mapping<T, U> { 
        U apply(T element); 
    } 
 
    public static void main (String[] args) { 
        List<String> inputList = 
                Arrays.asList("functional", "programming", "with", "closures"); 
 
        Mapping<String, Integer> stringToStringLength = 
          new Mapping<String, Integer>() { 
            public Integer apply(String element) { 
                return element.length(); 
            } 
        }; 
        List<Integer> mappedList = map(inputList, stringToStringLength); 
        System.out.println("Initial List: " + inputList); 
        System.out.println("Mapped List: " + mappedList); 
    }

In the example above, there is a map function which takes a list but it also takes another object as a parameter which will decide how each element in the list will be transformed into a new element for the resulting list. In functional programming, functions are treated as first class values and can be passed as arguments into other functions in the same as any other type of value.

In order to do this in an OO language such as Java pre Java 8, this function argument, mapping, needs to be first wrapped in a one method object. In this case the one method object will be an implementation of the one method interface, Mapping. This interface has one method, apply. The method is essentially the first class function that could be passed around in a functional programming language. An instance of this one method interface can be called a closure. In functional programming, this one method object is represented simply as a function and can also be called a closure.

The main method uses this map function to transform a list of strings into a new list representing the length of each string in the original list. An instance of the Mapping interface is created with an anonymous class. This is the one method object or closure or “function” which is passed as an argument to the map function in order to tell the map function how to transform the list of strings.

Lambdas/Closures in Java 8 – Coating on one Method Objects

Now lets refine the above example a bit to show how, essentially, Java 8 hides this under the covers (but I’m sure it provides optimisations along the way) with its lambda syntax.

 
 
    public static <T, U> List<U> map(List<T> list, Function<T, U> mapping) { 
 
        List<U> result = new ArrayList<U>(); 
        for (T elem : list) { 
            result.add(mapping.apply(elem)); 
        } 
        return result; 
    } 
 
    public static void main (String[] args) { 
        List<String> inputList = 
                Arrays.asList("functional", "programming", "with", "closures"); 
 
        List<Integer> mappedList = map(inputList, s -> s.length()); 
 
        System.out.println("Initial List: " + inputList); 
        System.out.println("Mapped List: " + mappedList); 
    }

In the above example, the Mapping interface is no longer required because Java 8 has a library of one method interfaces, called Functional Interfaces, out of the box. The map function, apart from using the Java 8 Function interface, has remained the same in its implementation. In the main method, instead of having to create and instantiate an anonymous class, we can use a Java 8 lambda which is essentially a function implementation.
s -> s.length()
This is defining a function implementation which takes a String (or anything which has a .length() method and returns an Integer) and returns the length of that String. It can really be thought of as a syntax replacement for the anonymous one method class that we had to declare in the previous example.

Refined more with Java 8 Streams

Using Java 8 streams we can take this further by simply using the map method already available on Java 8 streams. It is typical for any functional programming language to provide this map method out of the box.

 
 
    public static void main (String[] args) { 
        List<String> inputList = 
                Arrays.asList("functional", "programming", "with", "closures"); 
 
        List<Integer> mappedList = inputList.stream().map(s -> s.length()).collect(toList()); 
 
        System.out.println("Initial List: " + inputList); 
        System.out.println("Mapped List: " + mappedList); 
    }

The above example is refined to use Java 8 streams. The whole transformation can now be done in the main method using the map function from the Java 8 API. The lambda which is passed to this function remains unchanged from the one passed to the earlier implementation of map.

Haskell Beauty!!

To finish, here is the same mapping transformation implemented in the fully fledged, pure functional programming language that is Haskell.

map length ["functional", "programming", "with", "closures"]

In the Haskell above, we are simply declaring that we want to map the length function over the list of strings.

Conclusion

Thanks for reading this. I hope this post brought some value to developers looking to move into the functional programming world and also to developers already doing functional programming along with anyone with any other interest in functional programming. Feel free to comment.