4. 1st Class Functions – Power is in simplicity

One of the most interesting article I read about programming languages has been published by the author of Chibi, a small scheme implementation (https://synthcode.com/blog/2009/06/Small_is_Beautiful). The latter tries to defend the idea that beauty and power of programming languages is achieved through simplicity.

While people understand that hiding complexity behind abstractions is a fundamental concept helping mastering problem complexity, they tend to think that adding syntax, and features to programming languages makes them more powerful. I think it is wrong. Programming languages are before of all languages, what matters is their expressivity, not how much keywords they have. Some simple concepts can be really powerful and add a real value while others are insignificant and just add complexity.

The Revised 5th Report on Scheme (R5RS) even states:

The simplicity, power, and expressiveness of functional programming languages come from their core: functions.

Although they may look similar they are not the functions you have in imperative languages. They are lambdas (from the mathematical field of lambda calculus). As imperative functions they allow create a new scope and allow code reuse, however what makes lambdas so special is that:

1- They are 1st class values which means they can be bound, passed as arguments or return values from other functions like any other values :

2- They have the interesting property of capturing a part of their environment of definition (we also call them closures) :

Let’s have a closer look at the definition of the makeAdder function:

Look at the x parameter, this parameter is used in the body of the addX function without being declared in its definition parameter list! What happens here is that the addX function definition captured this parameter from its parent scope, we says that x is a free variable in the context of addX. This lambda property may appear useless at the first sight but actually it is the more powerful!

Thanks to the fact that lambda functions capture data, we don’t need data structures anymore! Functional programming languages make the gap between code and data disappear. If you know OOP, you know that the fundamental idea behind it, is to put data with code and encapsulate it, it is exactly what lambdas provide. 

F# provides a complete object layer, but let me show you how you could build OOP objects just by using the concept of lambdas:

makePerson is a constructor for person objects with the getFirstName getLastName and getFullName methods. firstName and lastName are free variables in the context of their respective getter methods. I used the unit operator () as an argument in the let expressions in order to ensure that  I am binding functions and not just values, indeed let getFirstName = firstName would have bound the value firstName to the symbol getFirstName not built a function.

We can try to play with this code in the interactive console:

The p object represents a person, we can use method on it like this: (p “methodName”)()   if the method doesn’t exist we get a failure exception. This object model is simple and well suited for non dynamically typed languages like LISP or even JavaScript, however it is heavy to use in statically typed languages such as F# or Haskell. Indeed, if you try to add a method with a type different than unit –> string it won’t work (though you could use list of objects for arguments…).

3- They can be partially applied (in F# and Haskell for example) and composed :

Lambda functions are defined in mathematics as single input, single output functions, they have a type of ‘a –> ‘b with ‘a and ‘b generic types. However we can use several lambdas together to model a multiple inputs function from unary functions.

For example if we look at the type of the List.map function in the interpreter we get:

Each time you see the (–>) operator it means you are dealing with an unary function whose input is on the left and output on the right of this operator.

The type ((‘a –> ‘b) –> ‘a list –> b’ list) tells us that List.map is an unary function which takes as first parameter an unary function of type (‘a –> b) and returns an unary function list of ‘b and then returns a list of ‘b. When no parenthesis are present in the type, unary functions are considered  as forming a multiple inputs function, the right most type being the type of the output. So List.map is a function taking an unary function of type (‘a –> ‘b) as first parameter and a list of ‘a as second parameter and returning a list of type ‘b.

By the way it is interesting to notice that just by reasoning about the type you can discover what a function does, in the case of map you have a  function from ‘a to ‘b and a list of ‘a as input and a list of ‘b as output, you can guess that the unary function is applied to each element of the list, and the result collected in the output list.

Ok now that I tell you that, you may think that it is rather complicated for nothing. Except the fact it fits the mathematical model, from a practical programmer point of view what are the benefits of decomposing multiple parameters functions into unary functions?

It allows you to do something powerful called partial application (left currying), which consists in creating new specialized functions from older ones by omitting parameters:

An other interesting feature is composition, function composition and partial application allow you to write really concise code. To compose functions from right to left (the mathematical way) use the (<<) operator function, to compose functions from left to right (can be more natural) use the (>>) operator function.

Focus on the processData function definition, can you guess what this short line of code does?

• It reads data from a file
• It tokenizes the text of the file using the ‘:’ separator
• It converts textual numbers to integers
• It multiplies them by 2
• Removes those greater than 30
• Returns the list of numbers

Do you see how short this function definition in term of code is! That’s a part of the magic coming with functional programming. Composition works with function, in case you would like you start expression to be your value, you can use the pipe operator we saw previously:

Here, we call readData at the beginning of the pipeline, so we are chaining values. Of course the result is the same.

4- They are anonymous, and can be defined when needed.

Lambdas are anonymous values, if they have a name it is only because you bound them to this name. if you want to declare an anonymous lambda you can use the fun keywords. The advantage of anonymous function is that you can create and use them immediately when you need it (see more about it in my article on Sequences and infinite streams).

Below an example showing three ways of defining the same function:

You can also use the function keyword to build an anonymous unary function which applies pattern matching on its parameter (see my article on pattern matching for more information).

5- They are optimized for tail recursion in a lot of functional programming languages implementations including F#.

If you read my article on Recursion you probably understand how important recursion is in functional programming languages. Since recursion is omnipresent it better has to be optimized. This is the case in F#, the compiler translates tail recursion into loops, avoiding to pileup useless context information on the stack. So well written functional recursive code runs as fast as iterative imperative code without exhausting the stack memory.

Pure functions

If your functions  are pure (aka they don’t have side effects), you can reason following a simple substitution model: you can substitute a function application with its body if you replace parameters correctly with the arguments of the application. If you do that you can easily understand how functions act. It is a model all programmers use naturally, however this substitution model is only true when there is no side effect. It is one of the main cause of bugs in imperative code which encourages side effects, since you have to remember all the side effects  in your code and how they cascade  to reason about it!

Catamorphism and anamorphism

Don’t worry I am not cursing you with these two words. Do you remember I told you that map and filter are two very important functions to work with lists (and sequences in general). Actually there are functions more powerful than them.

Look at these definitions:

Do you see what they have in commons?

They browse lists from start to end while performing an action on the car and the cdr. This is a pattern, and in programming we like to capture and abstract patterns to reuse them. The function under this pattern is fold which types is (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a). This type tells us that fold takes a function with an arity of two whose parameters are of types ‘a and ‘b and which returns an ‘a as well as an ‘a and a list of ‘b and then returns an ‘a.

This is how this functions works, we give it an action as first argument, this action is applied on an accumulator value and the first element of the list , we also provides fold a starting value for the accumulator and finally the list we want to fold.

This is how fold is implemented:

This how fold is used:

The 21 lines of code you wrote earlier are now 9 lines of code and you got two new functions for free! that the power of fold and partial application! xcons is a flipped version of the cons operator and reverse a function to reverse a list.

Ok you could say, I specific examples on purpose, so let’s add new functions you would code in  about 10 lines of code in imperative languages that you can now write in one:

In these examples we fold from left to right so when we build list results, the list are reversed and we need to reverse them back. If you want to fold a list from right to left you can use another function traditionally called fold right or (foldBack in F#):

So what are the differences between fold left (fold) and fold right (foldBack), which one should I choose?

As you can see from its definition fold left is a tail recursive function, so you are sure that it will be optimized and that it will not make your stack overflow, however when working on lists fold left generates the elements in reverse, forcing you to reverse them back if you want to keep the ordering. Fold right is not tail recursive, however it generates elements in the right order when building lists, so using fold right for small lists and fold left for medium or long list is a good compromise, if you don’t know opt for the left version. As you will see in my article on Sequences, choosing fold right is meaningful when working on infinite lists.

Guess what? fold and foldBack are catamorphisms! You don’t need to re-implement these functions since they are available in the List module.  What about anamorphisms? Anamorphisms represent the opposite process, we are now talking about unfolding not folding. The unfold function helps you build a list from a base element, and a generator function applied until a predicate is satisfied.

Here the unfold implementation:

This function is really powerful when you want to build list, you can for example extract an entire stream of values from a file into a list in one line of code! Below two example functions:

Not completely the end…

All these possible features in a simple function concept, and there would be a lot more to say!  I hope that thanks to this article you have started to understand how expressive and powerful functions are in functional programming languages. And with these functions, as a consequence to be concise, highly reusable and modular, statically typed, without side effect, your code is likely to be bug free!