Functional programming

Functional programming is based on the notion of pure functions, i.e. the result of a function depends only on its inputs. This means in particular, that one can freely replace a value with a function for computing this value in any context without changing the semantics of a program11 This property is also known as referential transparency.. As an example consider the following program:

f x y = x + y
g x   = 2 * x

h x = f (g x) (g x)

or its equivalent version

f x y = x + y
g x   = 2 * x

h x = let y = g x
      in f y y

As soon as functions have side-effects, i.e. they do additional stuff such as writing to the terminal, this property is lost and it matters when and in which order their effects are evaluated. As an example, just compare the corresponding program in Common Lisp where now both functions f, g have side effects.

⊕If Lisp doesn’t suite you, feel free to pick Python, Julia, C, Java or other language that you like or use.

(defun f (x y)
  (format t "Calling (f ~a ~a)~%" x y)
  (+ x y))

(defun g (x)
  (format t "Calling (g ~a)~%" x)
  (* 2 x))

(defun h-1 (x)
  (let ((y (g x)))
    (f y y)))

(defun h-2 (x)
  (f (g x) (g x)))

Now, both versions of h differ in their handling of side-effects. In particular, (h-1 1) and (h-2 1) will return the same result, but exhibit visually distinguishable side-effects, i.e., the first call evaluates g once and prints

Calling (g 1)
Calling (f 2 2)

while the latter shows

Calling (g 1)
Calling (g 1)
Calling (f 2 2)

evaluating g twice.

And then came do

Using the IO monad the above programs – with side-effects – can be written in Haskell as

f x y = do
  putStrLn $ "Calling f " ++ show x ++ " " ++ show y
  return $ x + y

g x = do
  putStrLn $ "Calling g " ++ show x
  return $ 2 * x

were the do-notation was used to stress the sequential nature of side-effects. Accordingly, also the two versions of h have to be changed to accomodate the effects within f and g.

h x = do
  y <- g x
  f y y

h' x = do
  y  <- g x
  y' <- g x
  f y y'

⊕At least that’s what we have been told … and indeed, the do–notation forces us to rewrite functional code into a rather different structure resembling imperative programs.

Note that with monadic effects the second version can no longer be written as f (g x) (g x) as we cannot apply monadic functions. Desugaring the do–notation allows to better understand the relation to the functional versions:

hNoDo x = g x >>= \y ->
          f y y

hNoDo' x = g x >>= \y ->
           g x >>= \y' ->
           f y y' 

In the end, this is just continuation passing style22 In this blog post the continuation monad has been called the “mother of all monads”. Indeed, continuations can be used to represent any monad which illustrates the two aspects underlying monadic effects: First, computations are explicitly chained in continuation-passing style and secondly, only certain effects are allowed in each monad. The second aspect is ensured by the type system which restricts the use of continuations suitable for each particular monad. (CPS) … but I don’t want to be forced writing programs in this way, i.e., explicitly chaining all steps. In my opinion the do-notation does little to help here, being invasive, ugly and misleading.

Interlude

Compared to CPS the do-notation does offer some improvements and a similar notation has indeed been used in On Lisp by Paul Graham for implementing continuations in Common Lisp. Interestingly, their use has to obey certain restrictions (Box 20.5) which are akin to the rules of when the do-notation can be used – the main difference being that the type system of Haskell enforces proper use. Still programming in the do-notation looks and feels rather different than functional programming.

In this regard, applicative functors have gained popularity which admit a more applicative style of programming. Yet, they only provide a weaker, i.e., more general, abstraction than monads and unfortunately, the side-effects within f and g – which depend on their function arguments – cannot be modeled in this fashion and require monads.

Applicative functors

Let’s investigate the difference between the functional and imperative style of pure and monadic programs in more detail. In particular, we focus on the types in each case and explicitly express function application.

Pure functions

Function application forms the basis of functional programming33 Arguably function composition could be considered equally fundamental as exemplified in the pointfree style.. Let us explicitly define an operator for function application44 In Haskell the operator $ plays this role, but has the wrong associativity. In particular, we cannot write f $ 1 $ 2 to express successive applications (f 1) 2. In this sense, $ is merely a shortcut to remove some brackets, but not a drop-in replacement for function application.

infixl 4 #

(#) :: (a -> b) -> a -> b
f # x = f x

and explicitly insert it whenever a function is applied, i.e.

f # 1 # 2 -- instead of f 1 2

Note in particular that partial application, i.e. currying, works as expected. Indeed, according to the type we have for some function f :: a1 -> ... -> an -> r and an argument x1 :: a1 that f # x1 :: a2 -> ... -> an -> r as required.

⊕This can be seen by instantiating the type variable b in the type of (#) with a2 -> … -> an -> r.

Applicative functors

Applicative functors provide a similar functionality. In particular the operator <*> corresponds to their application. In the following, we rename this operator to <#> for consistency.

infixl 4 <#>

(<#>) :: Applicative f => f (a -> b) -> f a -> f b
(<#>) = (<*>)

Compared to standard function application, i.e. #, its type is slightly different

(#)   ::                (a -> b) -> a -> b
(<#>) :: Functor f => f (a -> b) -> f a -> f b

and allows applicative effects on all arguments. In particular the effect on the function itself is rarely necessary. Accordingly, a convenience operator55 The name resembles $ and suggests that it acts like function application. Yet, in contrast to <*> it is asymmetric in its arguments and cannot play the role of general application. <$> is defined which simply puts a pure function into the applicative functor and then applies it66 Alternatively, <$> can be defined as f <$> x = fmap f x.

(<$>) :: Functor f => (a -> b) -> f a -> f b
f <$> x = pure f <#> x

where pure :: Functor f => a -> f a.

To understand why we need all arguments of <#> to be functorial consider the following situation. Suppose we have a pure function g :: a1 -> ... -> an -> b of \(n\) arguments and want to partially apply it as g x1. Furthermore, the argument could potentially require effects, i.e. x1 :: f a1. Assuming we had an operator, i.e. <#> for such an application, i.e. we should be able to write something like

g <#> x1 <#> ... <#> xn

⊕Note that this is just a suggestive hypothetical notation and does not have the correct types yet.

Then, what type could g <#> x1 possible have?

• In case of pure arguments, i.e. x1 :: a1, we just partially apply g and obtain

  g x1 :: a2 -> ... -> an -> r

• In case of an effectful argument, i.e. x1 :: f a1, we would need to apply the function via <$> and would end up with

  g <$> x1 :: f (a2 -> ... -> an -> r)

  Indeed, applying to an effectful argument requires that the effect is visible in the return value as well and therefore we end up with a functorial result type as of the definition of <$>.

Thus, by symmetry, successive application requires that the types compose and enforces functorial values on all arguments, i.e. <#> is the proper definition of function application when using applicative effects.

Monadic application

Most programming languages do not work with pure functions, but instead allow different side effects within functions. Thus, from a type perspective, functions are actually77 Assuming call-by-value semantics for the arguments.

f :: Monad m => a1 -> ... -> an -> m r

for some monad capturing the desired effects88 Which effects are available here is fixed by the language designer and usually includes mutable state, IO and exceptions. Furthermore, effects such as IO are usually not undone in case of non-local transfer of control, i.e., when raising exceptions.. Furthermore, such effectful functions can be applied to arguments which possibly contain additional effects as well.

Let’s again consider a suitable operator <<#>> for function application. Then a function f :: a -> m r of one argument could be applied to an effectful argument as

f <<#>> x1 :: m r

Now, what about a function f :: a1 -> a1 -> m r? Here, we would need that

f <<#>> x1 <<#>> x2 :: m r

whereas the only possible type for the partial application could be99 Retaining the effect from the first argument around the function – as in applicatives – and still allowing for an effect in the return value – from the monadic function.

f <<#>> x1 :: m (a2 -> m r)

Now even if we followed the example of applicative functors and considered the application of return f instead the types would not be symmetric and successive application would not work out

⊕Both return :: Monad m => a -> m a and pure :: Applicative f => a -> f a inject a value into the monad or applicative functor respectively.

return f <<#>> x1 <<#>> x2 :: Monad m => m r
return f <<#>> x1          :: Monad m => m (a2 -> m r)
return f                   :: Monad m => m (a1 -> a2 -> m r)

There are several options to make this work

1. Define different application operators suitable for functions with different number of arguments, i.e.

   appM1 :: Monad m => m (a1 -> m r) -> m a1 -> m r
   appM1 mf mx = mf >>= \f ->
                 mx >>= \x ->
                 f x
   
   
   appM2 :: Monad m => m (a1 -> a2 -> m r) -> m a1 -> m (a2 -> m r)
   appM2 mf mx = mf >>= \f ->
                 mx >>= \x ->
                 return (\y -> f x y)

   While this approach works, partial application is no longer automatic, i.e. we need to track the number of remaining arguments explicitly

   *Main> return f `appM2` (putStrLn "Argument 1" >> return 1) `appM1` return 2
   Argument 1
   Calling f 1 2
   3

2. Alternatively, we could just use the definitions for applicative functors and require the user to explicitly join the final result as it would be of type m (m r) then

   ⊕join :: Monad m => m (m r) -> m r can be defined for every monad via join mmx = mmx >>= id.

   *Main> join (return f <#> (putStrLn "Argument 1" >> return 1) <#> return 2)
   Argument 1
   Calling f 1 2
   3

   Again, the caller would be required to track how many function arguments have been provided in order to act accordingly when all arguments have been used up.

3. Finally, we could define

   infixl 4 <<#>>
   
   (<<#>>) :: Monad m => m (a -> m b) -> m a -> m b
   mf <<#>> mx = mf >>= \f ->
                 mx >>= \x ->
                 f x

   together with several functions1010 The name spice refers to the ability of these functions to “currify” their arguments.

   spice1 :: Monad m => (a1 -> m r) -> m (a1 -> m r)
   spice1 f = return f
   
   spice2 :: Monad m => (a1 -> a2 -> m r) -> m (a1 -> m (a2 -> m r))
   spice2 f = return (\x1 -> spice1 (f x1))
   
   spice3 :: Monad m => (a1 -> a2 -> a3 -> m r) -> m (a1 -> m (a2 -> m (a3 -> m r)))
   spice3 f = return (\x1 -> spice2 (f x1))

   and voila successive application works as desired

   *Main> spice2 f <<#>> (putStrLn "Argument 1" >> return 1) <<#>> return 2
   Argument 1
   Calling f 1 2
   3

The last approach seems more convenient to me, moving the burden of knowing the number of function arguments from the call side closer to its definition. Thus, we will use it below and investigate some examples of monadic programming in this style.

Apply your monads

With the above definitions, the second version of the simple example can be written as

h'' x = spice2 f <<#>> g x <<#>> g x

which resembles the original pure version. Yet, it handles effects within nested function calls as expected. Furthermore, it is still referentially transparent and in particular equivalent to

h''' x = let y = g x
         in spice2 f <<#>> y <<#>> y

which also executes the effect of g x twice.

Thus, comparing with the definition

h x = do
  y <- g x
  f y y

from above, we see that do resembles a let in standard programming languages, i.e. it executes an expressions effect and binds the variable to its value (without its effect).

Monads are sometimes called the programmable semicolon. This suggests that imperative statements are sequenced in this fashion. Yet, in Haskell – a purely functional language – there is no such thing as an imperative statement. Especially, the do–notation suggests the misleading interpretation that x <- acts like an assignment operation. It does not, as the following example using nested do–blocks illustrates:

statement = do
  x <- g 1
  putStrLn ("Before: " ++ show x)
  do
    x <- g 2
    putStrLn ("Inner: " ++ show x)
  putStrLn ("After: " ++ show x)

Instead it acts like a let statement as in e.g. Common Lisp1111 Or rather let* for the Lisp experts.

(defun statement-let ()
  (let ((x (g 1)))
    (format t "Before: ~d~%" x)
    (let ((x (g 2)))
      (format t "Inner: ~d~%" x))
    (format t "After: ~d~%" x)))

and not like an assignment1212 The reader might also want to try a corresponding example in Java, Python etc.:

(defun statement-assign ()
  (let (x)
    (setf x (g 1))
    (format t "Before: ~d~%" x)
    (progn
      (setf x (g 2))
      (format t "Inner: ~d~%" x))
    (format t "After: ~d~%" x)))

Further examples

To further illustrate the nature of the new operators, we consider the do–notation in yet more detail. In the most basic case

do
  x1 <- act1
  x2 <- act2
  -- ...
  actN

desugars as

act1 >>= \x1 ->
do
  x2 <- act2
  -- ...
  actN  

or – using the more applicative operators – as

spice1 (\x1 -> do
                 x2 <- act2
                   -- ...
                   actN)
<<#>> act1

This again illustrates the similarity to (non-recursive) let expressions

⊕Again, this is a hypothetical notation resembling other programming languages and not the way let works or is defined in Haskell.

let x1 = expr1
    x2 = expr2
in expr

which could be desugared as

(\x1 -> let x2 = expr2
        in expr)
# expr1

where the function application has been marked with # explicitly. Furthermore, the desugared version illustrates again that the do–notation is continuation–passing style in disguise, i.e. an explicit continuation is constructed and immediately applied.

As a slightly larger example, consider a program which calls several nested functions, i.e.

c :: Int
c      = 1

f1 :: Int -> Int
f1 x   = c * x

f2 :: Int -> Int -> Int
f2 x y = x + f1 y

prog :: Int
prog = f2 (f1 c) c

Now, suppose that the constant c is to be replaced with random numbers, i.e. we would want to define a random function which can be used instead

⊕For convenience we could define f1 = spice1 f1’ and f2 = spice2 f2’ explicitly and use f1 and f2 directly whenever an application is needed.

r :: R.MonadRandom m => m Int
r = R.fromList [(1, 0.1), (2, 0.2), (3, 0.3), (4, 0.4)]

f1' :: (Applicative m, R.MonadRandom m) => Int -> m Int
f1' x = pure (*) <#> r <#> pure x

f2' :: (Applicative m, R.MonadRandom m) => Int -> Int -> m Int
f2' x y = pure (+) <#> pure x <#> (spice1 f1' <<#>> return y)

prog' :: (Applicative m, R.MonadRandom m) => m Int
prog' = spice2 f2' <<#>> (spice1 f1' <<#>> r) <<#>> r

Instead of the larger change required in the translation into the do–notation1313 Try this at home!, i.e. naming all intermediate results and sequencing, we mechanically replaced each function application. Either using the operator <#> when applying pure functions (to possibly effectful arguments) or the operator <<#>> when applying monadic functions. In turn, further simplifications would be possible, e.g. f1' y instead of spice1 f1' <<#>> return y.

In the end, monads allow precise control over side-effects. In particular, the type system ensures that only the desired effects are possible. In turn, function application needs to explicitly distinguish between three cases captured by different operators:

1. #: A pure function is applied to pure arguments. No effects are executed.

2. <#>: A pure function is applied to effectful arguments. Effects are executed from left to right.

3. <<#>>: An effectful function is applied to effectful arguments. Its effects are executed after the arguments’ effects.

Most programming language only provide the last version, i.e. all functions can implicitly contain effects in the single monad that is provided by the language designer. Haskell allows much more flexibility in this regard and especially when applying our effects/monads we can indeed claim that:

In short, Haskell is the world’s finest imperative programming language.