Functional programming

This article is part of a series of six articles:

Even though the history of functional programming (FP) can be traced back to 1936, when Church & Rosser came up with the lambda calculus, it has not gained as much traction in practice as object-oriented programming. In my view, and that of others as well, pure object-oriented programming is not the answer to everything and functional programming is an important tool not to be underestimated.

In FP programs are executed by evaluating expressions in contrast to imperative programming where programs are composed of statements which change global state when executed. This article should be an overview about the most important concepts and techniques of functional programming.

Functional programming builds on top of the declarative computation model and in this article we will have a look at common features of functional programming languages.

Anonymous functions

Anonymous functions are often called “lambda” functions, in a nod to their heritage in lambda calculus. We can use anonymous functions to avoid the need to give names to our functions and thus make our programs more succinct.

Algebraic data types

An algebraic data type is kind of a composite type — a type formed by combining other types. The two algebraic types are product types, i.e. tuples other types that include two or more types in a fixed order, and sum types that can take the form of different types.

  • “product” is combination (`A B`, meaning `A` and `B` together)
  • “sum” is alternation (`A | B`, meaning `A` or `B` but not both)

Higher-kinded types

Kinds are the types of types. For instance `Int` has kind `*` which means it’s a concrete type that can be instantiated by values. A simple type constructor has kind `* -> *` and is regarded as a higher-kinded type.

A type constructor is a type that you can apply type arguments to “construct” a concrete type. A function can be seen as a value constructor, where you apply arguments to “construct” a value and is therefore very similar.

A `List` is an example for a higher-kinded type — you have to supply a type argument to turn a `List` type constructor into a concrete type that can be instantiated by values, e.g. by applying `Int` to construct the concrete type `List Int`.

Higher-kinded types are not limited to one type argument. Functions can take shapes like `Int -> Int -> Int` or `(Int -> Int) -> Int`. A type constructor too can take shapes like `* -> * -> *` or `(* -> *) -> *`.

Pattern matching

We have seen how to construct values with algebraic data types and pattern matching is a tool to work with these values. There are two things we would like to be able to do:

  • If the type has more than one value constructor, we need to able to tell which constructor was used to create the value.
  • If the value constructor has data components, we need to be able to extract those values.

A pattern lets us look inside a value and binds variables to the data it contains.

Guards are a useful addition to patterns. Patterns let us perform fixed tests of a value’s shape while guards offer a more expressive check. Guards offer you a conditional evaluation based on the patterns matched.

Lazy evaluation

Lazy evaluation means that expressions are not evaluated when they are bound to variables, but their evaluation is deferred until their results are needed by other computations.

Folds, Maps and Filters

Languages that facilitate functional programming typically provide libraries that contain standard functions, i.e. for working with Lists. You often hear that functional programming is declarative and it it not only declarative in a formal sense but also declarative in an intuitive sense. Folds, Maps and Filters are a good example what this actually means. You don’t write how you loop through a list and do something with its values — you write exactly what you want to do with the list.

Mutually knowing the standard library functions is the vocabulary you are going to speak — talking imperatively again and you will feel like a caveman.

Currying and partial function application

Currying is a technique of translating the evaluation of a function with multiple arguments into a sequence of functions, each with a single argument.

Curried functions make partial application straightforward because they always return another function if they are not fully applied.

Function Composition

Composing functions is turning two function into a new function. Functions can always be composed as long as the return type of one function lines up with the input type of another function.

It is very common for functional programmers to write functions as a composition of other functions, never mentioning the actual arguments they will be applied to. Compare the following two functions.

The above functions perform exactly the same operation, however the latter is considered cleaner in the functional community. Performing this kind of optimisation (reducing unneeded arguments) is also called eta reduction. Extensive use of eta reduction can lead to functions never mentioning the arguments they are operating on, so called point-free functions.

Typeclasses

Programming languages typically need some kind of function overloading as there are operations that need to be available for a number of different types, just think of `==` or `+`.

The problem we are talking about is called ad-hoc polymorphism in contrast to parametric polymorphism where a function operates exactly the same no matter what type it is used with, e.g. `length` of a list. Ad-hoc polymorphism enables different behaviours with different types.

Typeclasses define a set of functions that can have different implementations depending on the type of arguments they are given.

As you can see above, typeclasses offer way to extend the types functions can handle by supplying a custom implementation later on without having to manipulate the typeclass. You could easily supply an `==` operation for your own custom types.

Beside extensibility a typeclass can also be seen as a way to restrict the types of arguments a function can take. You can thus create functions that are overloaded for every type you have defined for your typeclass.

There are a lot of typeclasses that abstract common functionality and they offer another way of increasing declarativeness.

Acquiring a common understanding of typeclasses will build up your vocabulary and help you tell other people what you want to implement, not how you want to implement it.

Conclusion

Functional programming is a very effective tool that helps you to create programs that are more declarative, easier to reason about and easier to test. Most of the time a functional solution should be the way to go if you truly respect the rule of least expressiveness.

Purists of functional programming tend to overuse function composition and therefore write code that is hard to comprehend. Furthermore neglecting the need for explicit state results in programs that thread state through the application with less explicit constructs that mimic imperative programming.

Resources: CTM