Getting a better understand of Haskell has always been on my list. My typical toolbox¹ for learning another programming language is not so effective with Haskell, because in contrast to say - Ruby² - learning Haskell requires me to learn new concepts. On the other hand, Haskell offers some unique features, which make learning it surprisingly easy again. Of these tools, type signatures have quickly become invaluable. Embrace them or perish, I might say, for if you don’t learn to utilize them, everything people typically criticize about the Haskell ecosystem (sparse documentation, obscure love for operators, being completely lost in abstraction) will hit you hard. On the other hand, if you learn to read the Haskell type (signatures), you often know things from quick, formal considerations early on, without having even started to think about the semantics of that piece of code.

Much can be written about type signatures but in this blog post, I try to focus on type signatures of Haskell’s most common abstractions, and point out some patterns and parallels in them (and as it turns out, these are not only parallels in the type signatures, but in semantics too.)

With all the talk about Monads, a lot of introductory material kind of leaves out Functors, Applicative Functors und the merrits of Applicative Functor style. If you have so far diligently learned some Haskell, but were put off by Haskell’s liberal use of weird operators, applicative Functor style will show you how operators can be used for great benefit.

The following compilation is of things I rather understood recently, so bear in mind, that I might have missed one or the other connection.

Overview

The purpose of this blog post is to explain some properties of typical Haskell type classes by looking at the type signatures³ of their member functions. So first of all, the objective is to have these signatures ready for reading. The following signatures were infered by looking for the type signatures interactively in ghc’s ghci prompt. One can also look into the source, though, they should tell you the same.

Normal Functions

We’ll start having a look at normal function applications.

($) :: (a -> b) -> a -> b
(.) :: (b -> c) -> (a -> b) -> a -> c

The . operator for function composition allows us in Haskell to write (f . g) x instead of f (g x).

$ is a low-priority operator which represents the function application, so instead of f x, we can also write f $ x. It is mostly used to avoid parentheses in code (to write f . g $ x for the above example), but in this blog post, I will use it to represent function application in general.

Functor

In a functional, statically typed programming language without the mathematical obsession of the haskell community, a Functor might have been named “Mappable”. Haskell took the name Functor⁴ from a mathematical concept in category theory

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

Depending on personal preference and style, there is also fmap, which is just another name for (<$>).

Applicative

An Applicative is a special kind of Functor, that extends Functors. It features the operator <*> for sequencing computations (combining their results), and pure, a function to bring values into an applicative context.

pure  :: Applicative f =>          a -> f a
(<*>) :: Applicative f => f (a -> b) -> f a -> f b -- sequential application

While pure and <*> constitute a minimal implementation, typically the operators <* and *> are also used, which discard some computation results instead of combining them like <*>, this is very handy when writing megaparsec parsers. My mnemonic to not confuse them: the angle bracket points to values the value not discarded:

(*>)  :: Applicative f =>        f a -> f b -> f b -- discard the first value
(<*)  :: Applicative f =>        f a -> f b -> f a -- discard the second value

Just by looking at the type signature, you can infer that (*>) keeps its right-hand-side value and discards the one to the left, because f a -> f b -> f b

Monad

Monads are characterized by the bind operator >>= and the return operator. >>= passes a “monadic” value m a to a monadic function (a -> m b), return puts a value into a monadic container.

Monads are also Applicatives and Functors, i.e. they also implement <$>, <*>, etc.

-- Sequentially compose two actions, passing any value produced
-- by the first as an argument to the second
(>>=)  :: Monad m =>        m a -> (a -> m b) -> m b
return :: Monad m =>   a -> m a
(>>)   :: Monad m =>        m a ->        m b -> m b        -- discards value of first monad
(<=<)  :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c) -- kleisli composition

Note: Trying to explain a Monad by allegories and metaphors is in my experience often futile (and a common pitfall for Haskell learners). Way more effective is to gain some basic understanding on the type level and imitate Monad usage with various examples.

Operations that Apply

If you think about it, the <*> operation of the Applicative (sequential application) and the function application operator $ have a pretty similar signature, this is also true for <$>, the map operation

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

The first operand of those operators all map from one type a to the other b (in the case of <*> that a -> b is hidden in an applicative). The second operand is the argument to the application. In the case of normal function application this is plainly the function argument, with the Functor (“Mappable”) it is a Functor, in the case of the applicative it is an applicative.

The result of the operation is either of type b, Functor of b or applicative of b.

One instance of Functor and Applicative (an Applicative is always a Functor) is the list [] type. The following ghci interactive session will demonstrate the three applying operators:

> (+10) $ 1
11
> (+10) <$> [1,2,3]
[11,12,13]
> (+) <$> [1,2,3] <*> [10, 20, 30]
[11,21,31,12,22,32,13,23,33]

In Haskell, the list type implements Monad, which means it also is an Applicative and a Functor. Treating the list as a Functor, we can apply the function that increments by 10 to each element, and treating the list as an applicative, we can sequentially join two lists by adding their elements (building the sum of the cartesian product of their combinations).

Let’s investigate the type properties of that last statement that used the f <$> arg1 <*> arg2 pattern (we call this “applicative style”):

> let mapAndApply f arg1 arg2 = f <$> arg1 <*> arg2
> :t mapAndApply
mapAndApply :: Applicative f => (a1 -> a -> b) -> f a1 -> f a -> f b

Thus, Haskell infers types for f :: (a1 -> a -> b), for the second argument arg1 :: f a1 and arg2 :: f b.

Lifting

This combination is a common function, called liftA2

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

We can read liftA2 (+) as “lift the addition to an applicative action”. After lifting, he have an addition for all applicatives.

> let addApplicative = liftA2 (+)
addApplicative :: (Num c, Applicative f) => f c -> f c -> f c

To prove the point, we can experiment with this using various applicatives in the Haskell’s std. library

> addApplicative (Just 1) Nothing
Nothing
> addApplicative (Just 1) (Just 2)
Just 3
> addApplicative Nothing (Just 2)
Nothing
> addApplicative Nothing Nothing
Nothing
> addApplicative Nothing Nothing
Nothing
> addApplicative (Right 5) (Right 6)
Right 11
> addApplicative (Right 5) (Left "a")
Left "a"
> addApplicative [1,2,3] [10,20,30]
[11,21,31,12,22,32,13,23,33]
> addApplicative [1,2,3] []
[]

Using a lifted function gives you the impression of working with ordinary functions, the symmetry between (f $ x) y and f <$> x <*> y makes this possible.

Applicative Style

The same evaluations can also be written in applicative style.

> (+) <$> Just 1 <*> Nothing
Nothing
> (+) <$> Just 1 <*> Just 2
Just 3
> (+) <$> Nothing <*> Just 2
Nothing
> (+) <$> Nothing <*> Nothing
Nothing

Using applicative style emphasizes the resemblance of function application with arguments f $ x y and applicative f <$> x <*> y, without requiring pre-registered liftAx functions (x representing the arity).

Example: Generating a stream of unique labels

This will be a “more real-world” example that applicative style. Suppose we need to generate labels in code, for example while performing operations on an abstract syntax tree. Each label needs to be unique, and we need labels in various functions. Since we use Haskell and pure-functions, we cannot just mutate some counter-variable.

import Control.Applicative
import Control.Monad.State

type LabelM = State Int

increment :: LabelM String
increment = state $ \i ->
  let j = i + 1
   in ("$" ++ show j, j)

labels :: Bool -> LabelM [(String, String)]
labels discard =
  f
    <$> twoLabels
    <*> twoLabels
    <*> twoLabels
  where
    f a b c =
      if discard
        then [a, c]
        else [a, b, c]
    -- (,) <- is an operator creating a tuple
    twoLabels :: LabelM (String, String)
    twoLabels = (,) <$> increment <*> increment

main :: IO ()
main = do
  putStrLn "Enter `True`, or `False`"
  discard <- getLine
  print (evalState (labels . read $ discard) 0)

When executed, this program will prompt you to enter either True or False, and then it will print out results, depending on the input. Either [("$1","$2"), ("$5","$6")] or [("$1","$2"),("$3","$4"),("$5","$6")]. Notice how even if the second label-pair is discarded after all, the counter is still incremented. The entry point is the evaluation of evalState in main. Here, we initialize the state monad’s state with 0 and evaluate the monadic test function. The state is managed by the state monad LabelM = State Int, which directly tells us that our state consists of an integer variable. Finally we have increment, which increments, that internal state and returns a label, as well as twoLabels, which generates a pair of such labels (by lifting increment). Note that both increment and twoLabels are of type LabelM _, once LabelM String and LabelM (String, String).

We use twoLabels in the labels function, where we use applicative style to obtain the unique labels and either return them all, or throw away some⁵. I condensed this use case from abstract syntax tree (AST) rewriting code, and if it wouldn’t blow up the example code, I would show code here, that introduced labels depending on the AST input to the program.

Solving this issue with label has some benfits. First of all, it makes the state explicit in the type signatures, which gives you the guarantee that if you are not using the LabelM type, you are not touching that state. Then, the state is handled just like any other value in Haskell – immutable. evalState is the bottleneck (in a good sense), that allows us to evaluate our “stateful” code and fetch it over in the LabelM-free world.

Composition Patterns

Another interesting pair of operations with a similar signature are the operators (.) and (<=<).

(.)   ::            (b ->   c) -> (a ->   b) -> (a -> c)
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)

The correspondence here is between functions of type (b -> c) and monadic functions of signature Monad m => (b -> m c). I.e. the signatures of (.) and (<=<) have almost the same pattern.

We know this Monad m => (b -> m c) signatures from the bind-operator’s second operand:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

By joining two M a >>= \x -> M b operations, I aim to infer (<=<), we’ll use the Maybe monad and I’ll write the signatures of the lambda functions to the right.

printLengthPrint :: Int -> Maybe Double
printLengthPrint = \w -> Just (show w)    -- :: Int -> Maybe String
               >>= \x -> Just (length x)  -- :: String -> Maybe Int
               >>= \y -> Just (2.0 ^^ y)  -- :: Int -> Maybe Double

We can kind of identify the signature of (<=<) just by looking at this. Now spell out the lambda functions in point-free style (I called them f,g,h) and we can implement the printLengthPrint function by Kleisli’s composition

f :: Int -> Maybe String
f = Just . show

g :: String -> Maybe Int
g = Just . length

h :: Int -> Maybe Double
h = Just . (2.0 ^^)

plp1 = h <=< g <=< f

plp2 = f >=> g >=> h

To sum it up: Functional programming is often defined as programming by function composition and application. Monads are a functional concepts and we can see that monads compose in a very similar way. This underlines the fact that Monads are indeed a functional concept (and not – like sometimes stated – imperative programming in sheep’s clothing).

Example

So far this blog post was a bit abstract, looking at type signatures and type signatures. So now we’ll see an example: A parser for simple arithmetic expressions and see when we can use the applicative style shown above, and when not.

The first parser is parsing Reverse Polish Notation style expressions, in RPN, the infix expression we are used to 1 + 2 * 3 would be written as + 1 * 2 3, it is especially simple to parse in contrast to the more common infix notation. We use megaparsec here.

First of all we need to import our parser library and the Identity Functor.

import qualified Text.Megaparsec.Lexer as L
import Text.Megaparsec
import Text.Megaparsec.String

Now we define an algebraic datatype representing our computation: Term. A term can either be an addition, a subtraction, a multiplication, a division, or an integer value here.

data Term
  = Add Term Term
  | Sub Term Term
  | Mul Term Term
  | Div Term Term
  | Val Integer
  deriving (Show, Eq)

Our parsing strategy is to always consume trailing whitespaces with every parsed term.

trimTrailing = L.lexeme space

op :: String -> Parser String
op = trimTrailing . string

Define multiplication, division, addition and subtraction expressions in applicative style (the next 5 expressions all have the type Parser Term)

mult = Add <$> (op "+" *> term) <*> term
divi = Div <$> (op "/" *> term) <*> term
addi = Mul <$> (op "*" *> term) <*> term
subt = Sub <$> (op "-" *> term) <*> term
intval = Val <$> trimTrailing L.integer

Now all left to do is define a parser for our expression as an alternative of all arithmetic operations:

term :: Parser Term
term =
  mult
    <|> divi
    <|> addi
    <|> subt
    <|> intval

Infix Parsing

If you are interested in infix parsing: it is algorithmically more complex. I.e. in infix parsing when the parser arrives at a number, it cannot easily know whether this number can stand alone, or whether it belongs to a binary operation with the operator to the right (in 3 * 4 + 5 the parser would have to find out that 3 is part of a multiplication expression, and then find out that the multiplication is part of an addition expression later on).

Luckily the megaparsec library has utilities to make parsing infix notation easier. I included a snippet for completeness.

parens = between (symbol "(") (symbol ")")
  where
    symbol = L.symbol space

infixExpr = makeExprParser infixTerm table

infixTerm =
  parens infixExpr
    <|> intval

table =
  [ [ InfixL (op "*" >> return Mul),
      InfixL (op "/" >> return Div)
    ],
    [ InfixL (op "+" >> return Add),
      InfixL (op "-" >> return Sub)
    ]
  ]

We can see at least here, that for this kind of a problem applicatives are not enough and we need Monads.

Resources

For more detail on Haskell’s types see the Typeclassopedia.

To familiarize yourself with Functors and Applicatives, it is really great to write parsers with Megaparsec.

What I wish I knew when learning Haskell by Stephen Diehl is also a great source.

Footnotes