Haskell Design Patterns

Haskell functions are first-class citizens of the language. This means that:

This places Haskell functions on an equal footing with primitive types.

Let's compose these three functions, f, g, and h, in a few different ways:

f, g, h :: String -> String

The most rudimentary way of combining them is through nesting:

z x = f (g (h x))

Function composition gives us a more idiomatic way of combining functions:

z' x = (f . g . h) x

Finally, we can abandon any reference to arguments:

z'' = f . g . h

This leaves us with an expression consisting of only functions. This is the "point-free" form.

Programming with functions in this style, free of arguments, is called tacit programming.

It is hard to argue against the elegance of this style, but in practice, point-free style can be more fun to write than to read: it can become difficult to infer types (and, therefore, meaning). Use this style when ease of reading is not overly compromised.

Consider a function that returns a few pieces of data, which we choose to express as a tuple:

g n = (n^2, n^3)

Then suppose we want to find the maximum value in that tuple:

max (g 11)

This would not work because the max function is curried, but we can easily align the types by uncurrying:

uncurry max (g 11)

Whenever we have a function returning a tuple and we want to consume that tuple from a curried function, we need to uncurry that function. Alternatively, if we are writing a function to consume an output tuple from another function, we might choose to write our function in uncurried (tuple arguments) form so that we don't have to later uncurry our function or unpack the tuple.

It is idiomatic in Haskell to curry by default. There is a very important reason for this. Thanks to currying, we can do this:

map (map square) [[1], [2,2], [3,3,3]]

We cannot, however, do this:

let map' = uncurry map
map' (map' square) [[1], [2,2], [3,3,3]]

We need to explicitly curry map' in order to compose it with other functions:

(curry map') (curry map' square) [[1], [2,2], [3,3,3]]

Curried functions are composable, whereas uncurried functions are not.

If we can apply one function argument at a time, nothing stops us from doing so at entirely different places in our codebase. For instance, we might "wire in" some authentication-related information into our function at one end of the codebase and use the specialized function in another part of the codebase that has no cognizance of the authentication argument and its related types.

This can be a powerful tool for decoupling, the site of decoupling being the function argument list!

Recursion can be viewed as a pattern for avoiding mutable state:

sumNonTail [] = 0
sumNonTail (x:xs) = x + (sumNonTail xs)

Without recursion, we would need to iterate through the list and keep adding to an intermediary sum until the list is exhausted, consider the example:

sumNonTail [2, 3, 5, 7]

This first expands into a nested chain of deferred operations, and when there are only primitives left in the expression, the computation starts folding back on itself:

-- 2 + sumNonTail [3, 5, 7]
-- 2 + (3 + sumNonTail [5, 7])
-- 2 + (3 + (5 + sumNonTail [7]))
-- 2 + (3 + (5 + (7 + sumNonTail [])))
-- 2 + (3 + (5 + (7 + 0)))
-- 2 + (3 + (5 + 7))
-- 2 + (3 + 12)
-- 2 + 15
-- 17

The sumNonTail function is non-tail-recursive. Because the recursion is "trapped" by the + operator, we need to hold the entire list in memory to perform the sum.

Tail recursion addresses the exorbitant use of space we have with non-tail-recursive processes:

sumTail' acc [] = acc
sumTail' acc (x:xs) = sumTail' (acc + x) xs
sumTail xs = sumTail' 0 xs

This form of recursion looks less like mathematical induction than the sumNonTail function did, and it also requires a helper function sumTail' to get the same ease of use that we had with sumNonTail. The advantage is clear when we look at the use of "constant space" in this process:

-- sumTail [2, 3, 5, 7]
-- sumTail' 0 [2, 3, 5, 7]
-- sumTail' 2 [3, 5, 7]
-- sumTail' 5 [5, 7]
-- sumTail' 10 [7]
-- sumTail' 17 []
-- 17

Even though sumTail is a recursive function, it expresses an iterative process. sumNonTail is a recursive function that expresses a recursive process.

Tail recursion is captured by the foldl function:

  foldlSum = foldl (+) 0

The foldl function expands in exactly the same way as sumTail'. In contrast, foldrSum expands in the same way as sumNonTail:

foldrSum = foldr (+) 0

One can clearly see the tail recursion in the definition of foldl, whereas in the definition of foldr, recursion is "trapped" by f:

foldr _ v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldl _ v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

Algebraic data types can express a combination of types, for example:

type Name = String
type Age = Int
data Person = P String Int -- combination

They can also express a composite of alternatives:

data MaybeInt = NoInt | JustInt Int

Here, each alternative represents a valid constructor of the algebraic type:

maybeInts = [JustInt 2, JustInt 3, JustInt 5, NoInt]

Type combination is also known as "product of types" and type alternation as "sum of types". In this way, we can create an "algebra of types", with sum and product as operators, hence the name Algebraic data types.

By parameterizing algebraic types, we create generic types:

data Maybe' a = Nothing' | Just' a

Algebraic data type constructors also serve as "deconstructors" in pattern matching:

fMaybe f (Just' x) = Just' (f x)
fMaybe f Nothing' = Nothing'

fMaybes = map (fMaybe (* 2)) [Just' 2, Just' 3, Nothing']

On the left of the = sign we deconstruct; on the right, we construct. In this sense, pattern matching is the complement of algebraic data types.

data Tree a = Leaf a | Branch (Tree a) (Tree a)

size :: Tree a -> Int
size (Leaf x) = 1
size (Branch t u) = size t + size u + 1

Polymorphism refers to the phenomenon of something taking many forms. In Haskell, there are two kinds of polymorphism: parametric and ad-hoc (first described by Strachey in Fundamental Concepts in Programming Languages, 1967).

length' :: [a] -> Int
length' [] = 0
length' (x:xs) = 1 + length xs

length' [1,2,3,5,7]
length' ['1','2','3','5','7']

class Num a where
   (+) :: a -> a -> a

instance Int Num where
   (+) :: Int → Int → Int
   x + y = intPlus x y

instance Float Num where
   (+) :: Float → Float → Float
   x + y = floatPlus x y

let x_int = 1 + 1        -- dispatch to 'intPlus'
let x_float = 1.0 + 2.5  -- dispatch to 'floatPlus'
let x  = 1 + 3.14        –- dispatch to 'floatPlus'

ghci> :t 1 -- Num a => a

data Maybe' a = Nothing' | Just' a
fMaybe f (Just' x) = Just' (f x)
fMaybe f Nothing' = Nothing'

data Shape = Circle Float | Rect Float Float

area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect length width) = length * width

data Circle = Circle Float
data Rect = Rect Float Float

class Shape a where
  area :: a -> Float

instance Shape Circle where
  area (Circle r) = pi * r^2
instance Shape Rect where
  area (Rect length' width') = length' * width'

area (Circle 10)

f v = case (type v) of
  Int -> "Int: " ++ (show v)
  Bool -> "Bool" ++ (show v)

data CustomerEvent = InvoicePaid Float | InvoiceNonPayment
data Customer = Individual Int | Organisation Int

payment_handler :: CustomerEvent -> Customer -> String

payment_handler (InvoicePaid amt) (Individual custId)
  = "SendReceipt for " ++ (show amt)
payment_handler (InvoicePaid amount) (Organisation custId)
  = "SendReceipt for " ++ (show amt)

payment_handler InvoiceNonPayment (Individual custId)
  = "CancelService for " ++ (show custId)
payment_handler InvoiceNonPayment (Organisation custId)
  = "SendWarning for " ++ (show custId)

class Eq a where
  (==), (/=) :: a -> a -> Bool
  x == y = not (x /= y)
  x /= y = not (x == y)

Functions and types intersect in several ways. Functions have a type, they can act on types, they can belong to type classes, and they can be specific or generic in type. With these capabilities, we can express several more Gang of Four patterns.

strategy fSetup fTeardown
  = do
      setup
      -– fullfil this function's purpose
      teardown

class TemplateAlgorithm where
  setup :: IO a → a
  teardown :: IO a → a
  doWork :: a → a
  fulfillPurpose
    = do
       setup
       doWork
       teardown

map square [2, 3, 5, 7]

The simple idea of laziness has the profound effect of enabling self-reference:

infinite42s = 42 : infinite42s

Streams (lazy lists) simulate infinity through "the promise of potential infinity" [Why Functional Programming Matters, Hughes]:

potentialBoom = (take 5 infinite42s)

A stream is always just one element cons'ed to a tail of whatever size. A function such as take consumes its input stream but is decoupled from the producer of the stream to such an extent that it doesn't matter whether the stream is finite or infinite (unbounded). Let's see this in action with a somewhat richer example:

generate :: StdGen -> (Int, StdGen)
generate g = random g :: (Int, StdGen)

-- import System.Random
main = do
  gen0 <- getStdGen
  let (int1, gen1) = (generate g)
  let (int2, gen2) = (generate gen1)

Here we are generating a random int value and returning a new generator, which we could use to generate a subsequent random int value (passing in the same generator would yield the same random number).

Carrying along the generator from one call to the next pollutes our code and makes our intent less clear. Let's instead create a producer of random integers as a stream:

randInts' g = (randInt, g) : (randInts' nextGen)
       where (randInt, nextGen) = (generate g)

Next, we suppress the generator part of the stream by simply selecting the first part of the tuple:

randInts g = map fst (randInts' g)
main = do
  g <- getStdGen
  print (take 3 (randInts g))

We still pass in the initial generator to the stream, but now we can consume independently from producing the numbers. We could just as easily now derive a stream of random numbers between 0 and 100:

randAmounts g = map (\x -> x `mod` 100) (randInts g)

This is why it is said that lazy lists decouple consumers from producers. From another perspective, we have a decoupling between iteration and termination. Either way, we have decoupling, which means we have a new way to modularize and structure our code.

bankAccount openingB (amt:amts)
  = openingB : bankAccount (openingB + amt) amts

(take 4 (bankAccount 0 [-100, 50, 50, 1]))

(take 4 (bankAccount 0 (randAmounts g)))

As useful as monads are for capturing effects, we also need to compose them, for example, how do we use monads for failure, I/O, and logging together?

In the same way that functional composition allows us to write more focused functions that can be combined together, monad composition allows us to create more focused monads, to be recombined in different ways. In Chapter 3: Patterns for Composition, we will explore monad transformers and how to create "monad stacks" of transformers to achieve monad composition.