Functional computations

Headline

Abstraction mechanisms for functional computations

Applications of pure functions return the same result whenever provided with the same arguments; they do not have any side effects. This may be viewed as a limitation when we need to model more general computations in functional programming. For instance, it may be more difficult to define functions that essentially manipulate some state or process some input.

However, there is a functional programming abstraction, the monad, which comes to rescue. A monad is essentially an abstract data type to facilitate the composition of computations as opposed to functions. There are various monads to deal with all the computational effects that one may encounter, e.g., the State monad, the Maybe monad, the Reader monad, the Writer monad, and the IO monad.

The aforementioned monads all concern relatively general effects. However, monadic style (in the sense of abstract data types over computations) is also useful in more domain-specific contexts. This is illustrated for the domain of parsing, i.e., analysing text according to a given grammar (syntax definition) and mapping the text to an appropriate tree-like structure, i.e., a parse tree (or syntax tree).

In modern Haskell, monads "compete" with applicative functors. "In functional programming, an applicative functor, or an applicative for short, is an intermediate structure between functors and monads. Applicative functors allow for functorial computations to be sequenced (unlike plain functors), but don't allow using results from prior computations in the definition of subsequent ones (unlike monads)." Wikipedia (Applicative Functor), 2023-07-09 We will also introduce applicatives. In fact, applicatives are arguably easier to grasp than monads, especially if we assume an understanding of functors. So we might as well start the discussion with applicatives and then proceed to monads.