What is FP?

Before diving into practical Haskell programming, we give a brief overview of FP, its history, and its applications. If you are eager to get your hands dirty, you may want to forge ahead to the next section, then return here at a later occasion when you are ready to put Haskell into context.

Programming with functions

Functional programming (FP) is one of the main programming paradigms next to imperative programming and object-oriented programming.

Declarative programming

What sets FP apart from the other two is that it is a member of the declarative programming family. Sometimes, the principle of declarative programming is summarized by saying that declarative programs state what should happen, not how it should happen. This means that its programs do not explicitly determine the order in which computation steps are executed; it is up to the language implementation. Haskell particularly stands out among other FP languages because it embraces the declarative programming principle with its lazy evaluation semantics, which Chapter 7, Lazy Evaluation, explains in detail.

Function-based programming

Most members of the declarative programming family use mathematical logic as their basis; programming in the language closely corresponds to writing statements and/or theories in a particular logical framework. Fp distinguishes itself from other declarative paradigms in that it uses mathematical functions as its core concept. Functions are a good formalism for expressing computation as a unit of data processing that turns inputs into outputs. Also, as the concept of functions is widely taught in schools, FP can be more approachable for those without a prior programming background than other programming paradigms. This is one of the reasons it is often taught as the first programming language in academic computer science curricula.

FP aims to replicate the mathematical concept of functions. Yet, there are practical reasons why this is not possible in general. Hence, it is important to be aware of the differences between mathematical functions and functions in FP languages. In mathematics, we can define a function without saying how it can be computed; it may even be impossible to compute certain mathematical functions because they rely on unknowable information such as what will happen in the future. This generality is, of course, not useful as the basis of a programming language. Hence, functional programs restrict themselves to functions that are given in a form that makes it clear how they should be computed.

Referential transparency

One of the key properties of mathematical functions that Haskell has adopted (but that many other FP languages violate) is referential transparency. The concept of referential transparency means that if an f(x) function call yields the result y, then it does not matter whether we write f(x) or y anywhere in our program. The two should be indistinguishable and not affect the outcome of the program.

Referential transparency is a valuable property as it guarantees that functions are in some sense easy to reason about. Indeed, it implies that no matter how often the function is called and in what context, if it is given the same input, it will produce the same output. Hence, we do not have to take into account any prior history or any aspects of the calling context. In contrast, functions or procedures in imperative and object-oriented languages can have implicit side channels or side effects. For example, they can access and modify global variables that are not explicitly passed in as parameters. As a consequence, repeated calls with the same parameters can have different results, and these functions are much harder to disentangle from their context.

Referential transparency also allows the compiler to carry out much more aggressive optimizations. Here are just a few possibilities:

• When the compiler sees a repeated function call, they are allowed to replace the second call with the result of the first. This is known as common subexpression elimination.
• When the result of a function call is not used, the compiler can drop the call entirely.
• When there are two independent function calls, the compiler can choose the order in which to execute them. In fact, the calls can even be executed in parallel without causing any interference.

Referential transparency also poses a challenge for programming as many common programming tasks involve side effects. Think of interacting with a user, another process, the filesystem, the operating system, a remote server, and so on. None of these are naturally modeled by means of referentially transparent functions. Nevertheless, Haskell has managed to come up with an unusual but elegant approach to reconciling side effects with referential transparency. Chapter 8, Input/Output, will cover this approach in detail.

First-class functions

While many languages of other paradigms also offer functions in some form, they typically do not embrace them to the same extent as functional languages. Indeed, FP languages give functions a first-class status; they have the same rights as other datatypes in the language.

This means that functions blur the line between computation and data; they are both. They not only process data but they can also be treated as data and constructed during program execution. Indeed, functions can be ferried around by other functions. Such functions, which take other functions as input or produce functions as output, are known as higher-order functions (see Chapter 4, Higher-Order Functions).

Just like programs dynamically assemble complex data structures, they can also assemble complex functions out of simpler functions by gluing them together in various ways. Finally, functions can also be stored as elements in data structures (e.g., in a list of functions), or themselves be viewed as containers of data. Chapter 5, First-Class Functions, explains all these use cases.

Static typing

The origins of FP in mathematical logic have set the paradigm on the path for developing powerful static type systems. A static type system means that the programs are checked for particular kinds of mistakes (known as type errors) before they are run. This is an effective way of quickly reducing the number of bugs in programs before they are in use.

While not all functional languages have gone down this path, Haskell and many other influential languages have spearheaded the development of such type systems. They have explored various aspects:

• How a process known as type inference can unburden programmers from supplying excessive amounts of type information to make type checking work
• How to reuse code that does not just work with one type of input but that can uniformly work on different types
• How to capture all kinds of relevant properties and program invariants in the type system in order for violations to be caught during type checking
• How to automatically generate boilerplate code based on the structure of types

This means that, often, the focus in Haskell programs is more on the types than on the actual code.

Abstraction

Taking all the previously mentioned aspects of FP together, there is a common theme: abstraction. Abstraction is an important tool in computer science. It compels us to extract the common patterns and focus on the high-level behavior while putting aside differences and irrelevant details. It gives names to these patterns so that we can replace lengthy descriptions with a single word that can be easily reused and does not inadvertently introduce variations in meaning. We reason about or develop intuition for an abstraction, and reuse that for the many instances of that abstraction. Hence, abstraction will be a common theme in this book.

While abstraction has many good properties, it can also be quite challenging. Indeed, when learning a new abstraction, there may not be an immediate foothold to grasp what the abstraction is about. It may seem pointless or inscrutable at first. This problem is one of the main challenges for newcomers to functional programmers, especially if they do not follow a carefully laid out didactic approach and are overwhelmed by many commonly used abstractions. To overcome this hurdle of unfamiliar abstractions, we should seek out specific instances of a new abstraction that are meaningful to us in their own right. By comparing such different examples, a common pattern may merge, namely the abstraction we are trying to grasp. Only at that point may we start to develop appreciation and intuition for the abstraction itself, and even discover new instances of the abstraction on our own. Then, with experience and practice, it will become easier to pick up new abstractions.

Now that we have a general idea of the key ingredients of FP, let us briefly consider where FP comes from and how it has led up to Haskell.

Brief history of FP

We will give a brief overview of the three key evolutionary steps that preceded the creation of Haskell and have been highly influential for FP in general. Along with name-dropping several key language features that we will learn about in this book, this brief history conveys two other important distinguishing aspects of FP. Firstly, as one of the oldest programming paradigms, FP pioneered and adopted language features many decades before they became mainstream. Secondly, it is steeped in a long tradition of scientific research that has poured more mathematical rigor and scientific scrutiny into the paradigm than in any other. In short, even though FP may be new to you and most mainstream programmers, it is not nerw. On the contrary, its maturity and solidity are two of its underappreciated selling points.

The lambda calculus

The history of FP started in the 1930s when mathematician Alonzo Church developed the lambda calculus to study the foundations of mathematics. This lambda calculus was, in a way, the first FP language, and sits at the core of all functional (and even many non-functional) programming languages today; Chapter 5, First-Class Functions, will show this for Haskell. Mind, we do need to be somewhat forgiving to see lambda calculus as a programming language. There was no computer to execute it on, nor was that its intended purpose. It only existed as a concept to reason about and to write about on paper. Moreover, it would not have been convenient to program with, as the lambda calculus is a highly primitive, stripped-down version of a programming language. It would take a lot of effort to use it to write what we consider today simple programs. Nevertheless, in 1937, Alan Turing showed that lambda calculus is as expressive as any other possible programming formalism. Indeed, there is nothing we can compute with any contemporary programming language that we cannot also compute with lambda calculus (provided we have enough patience to encode it and wait for the result). While the initial version of lambda calculus did not feature any types, Church came up with this notion in the 1940s.

Lisp

Lisp was the first practical FP language, developed by John McCarthy in the 1950s. Lisp was inspired by the lambda calculus and pioneered many practical programming language features that are taken for granted today, including recursion, conditional expressions, and automated garbage collection. The name Lisp itself is a contraction of the words LISt Processing, as lists were a prominent data structure of the language; as Chapter 3, Recursion, and Chapter 7, Lazy Evaluation, show, lists are still quite important in Haskell. Notably missing from Lisp is a static type system. Due to its high level of abstraction, Lisp became popular among artificial intelligence researchers. Lisp has had many descendants (including Scheme, Racket, and Clojure) and is still used today in various flavors.

ML

After Lisp, many other smaller, experimental, and less long-lived functional languages were developed. Another major milestone, the ML language, was developed by Robin Milner in the 1970s. It consolidated many earlier good ideas for FP language design, notably algebraic datatypes and pattern matching. These made ML (short for Meta Language) suitable for processing other formal languages (e.g., for compilers that process programming languages or for automated theorem provers that process logical formulas). A key contribution of ML is the work on a static type system that features parametric polymorphism, the Hindley-(Damas)-Milner type system, and a powerful type inference algorithm to go along with it. Haskell has inherited this type system, which we will use throughout this book, as well as algebraic datatypes and pattern matching, which are covered in Chapter 2, Algebraic Datatypes.

Now that we know of these key moments in the history of FP, let us move on to the next big evolutionary step: Haskell.

Haskell

Let us briefly consider the history of Haskell itself and identify the three main characteristics of the language that set it apart from other FP languages.

Abridged history

The Haskell language was created by a committee of researchers. Following the earlier popularity of the lazy FP language Miranda, which was proprietary, the committee wanted to pool their resources in defining an open standard.

Haskell 1.0 came out in 1990 and subsequently went through several further versions before reaching a stable milestone in 1997 with what is called Haskell 98, and was later published in the Haskell 90 Language Report. During this phase, many different implementations of Haskell were developed to carry out various experiments in language design. Yet, after Haskell 98, most of these projects gradually ended and one main implementation emerged, the GHC.

While minor changes have been made to the official Haskell standard since 1998, GHC has effectively taken over the de facto role of defining the language. Today, it provides more than 100 language extensions on top of Haskell 98.

Apart from laziness as the main rallying point of Haskell, we will next discuss the three main characteristics of the language.

Main characteristics

GHC’s lead developer, Simon Peyton Jones, characterizes Haskell as pure, principled, and nimble:

• Pure: Haskell is one of the few purely FP languages. Most other functional languages are, in fact, hybrids that also incorporate imperative elements, and sometimes object-oriented ones. The idea is that the advantages of FP only come fully into their own when the language goes all in on the functional paradigm and enforces its core tenets. A consequence of this strict adherence to purity certainly poses challenges to the designers and users of Haskell. Because they could not rely on established approaches from imperative languages to deal with a range of common programming situations, they had to come up with original purely functional approaches.
• Principled: As purely FP has a notion of function that is quite close to that of mathematics, many design aspects of Haskell and its libraries can be (and have been) founded on mathematical principles. Indeed, notably, the subareas of abstract algebra and category theory have turned out to offer useful abstract patterns that apply equally to mathematics and programming. As a consequence, Haskell programmers do not use the typical design pattern terminology that is common among many programming languages. Instead, they refer to abstract mathematical concepts such as monoids, functors, and monads. While these mathematically inspired concepts are more and more being picked up by other programming communities, it has for a long time branded Haskell as a language for theoretically-minded programmers.
• Nimble: The nimbleness refers to the relatively fast pace at which new language features are explored and adopted in Haskell, sometimes turning back on its steps to replace a suboptimal solution with a better one. This has cast Haskell in somewhat of a pioneering role, trailblazing the path for other programming languages that adopt its novel features after they have proven their worth. In this way, Haskell has become quite well-known among programming language designers and has influenced the design of many other languages.

Now that we have an idea of Haskell’s characteristics, let us compare it to other contemporary FP languages.

Other contemporary FP languages

There are several other prominent FP languages available today. What they have in common is that, unlike Haskell, they all make compromises with respect to purity. They allow destructive updates and other side effects (such as printing) anywhere in the program. Many also incorporate object-oriented features. We briefly mention a few.

F#

F# is Microsoft’s FP language for the .NET platform. It is a member of the ML family of languages with call-by-value semantics and strong static typing that was also partly influenced by Haskell. Because F# supports imperative and object-oriented programming, it is particularly convenient to interface F# with existing C# code and libraries.

OCaml

OCaml (Objective Caml) is another scion of the OCaml family that is particularly renowned for its emphasis on performance. As the name suggests, OCaml supports object-oriented programming, although this is perhaps not as commonly used as in the case of F#. One of the main contemporary users and backers (besides academic researchers) of OCaml is the trading firm Jane Street.

Scala

Scala is a hybrid functional/object-oriented language for the Java Virtual Machine (JVM) with static typing. Its design was heavily influenced by Haskell and contains many original ideas for reconciling the two paradigms, such as case classes as an object-oriented presentation of algebraic data types. While among the top five most popular JVM languages in industry, Scala is also increasingly being used in programming education as one of the first programming languages taught.

Others

There are many other contemporary programming languages that are either seen as functional (Clojure, Racket, Erlang, etc.) or that have been influenced to a larger or lesser extent by FP languages (Swift, Kotlin, Rust, and so on). Moreover, many languages contain libraries whose design has been heavily influenced by similar FP libraries, such as reactive programming libraries, parser combinators, and property-based testing frameworks.

Now that we know the common characteristics of a range of FP languages, let us see what they are good for.

Prominent application areas

While FP languages such as Haskell are fit for any purpose and have applications in many areas, there are a few that stand out in particular.

Perhaps the most well-developed application area of FP is that of implementing language processors such as compilers and interpreters. This is partly explained by the fact that for a long time, the main users of FP were the language developers themselves. Their main applications were the implementations of the languages they were developing. It is thus not surprising that functional languages and their libraries have been honed for this task. At the same time, many of the common FP language features are a perfect match for language processing. Language processors typically represent programs with tree-shaped data structures called abstract syntax trees. Such abstract syntax trees are easily represented with algebraic data types, taken apart with pattern matching, and processed recursively.

Moreover, the initial conversion of the program text to an abstract syntax tree proceeds via a parser. In the context of Haskell, in the 1990s, a novel approach called parser combinators was developed for defining such parsers in a compositional and library-based manner. This approach has now become immensely popular and has been ported far outside FP languages.

By lowering the threshold and cost for implementing new languages, FP has enabled a new problem-solving strategy: domain-specific languages (DSLs). DSLs are niche languages created to target a specific problem domain and solve problems more efficiently, ergonomically, or in a more accessible way than with general-purpose languages. Functional DSLs are particularly successful in the financial sector where they are used to model both financial and, in combination with blockchain technology, general-purpose contracts.

Now that we have put FP and Haskell in context, let us finally dive into writing our first code.