Types, pattern matching, and polymorphism

We capture the "composite pattern" very succinctly by creating recursive algebraic types, for example:

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

This pattern describes the need to sometimes unify a composite structure with individual members of that structure. In this case, we're unifying Leaf (a leaf being a part of a tree) and Tree (the composite structure). Now we can write functions that act on trees and leaves:

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

Functions over recursive types are typically recursive themselves.

In the following code, we have a function defined on a list of any type. The function is defined at such a high level of abstraction that the precise input type simply never comes into play, yet the result is of a particular type:

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

The length object exhibits parametric polymorphism because it acts uniformly on a range of types that share a common structure, in this case, lists:

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

In this sense, length is a generic function. Functions defined on parametric data types tend to be generic.

The canonical example of ad-hoc polymorphism (also known as "overloading") is that of the polymorphic + operator, defined for all Num variables:

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

In fact, the introduction of type classes into Haskell was driven by the need to solve the problem of overloading numerical operators and equality.

When we call (+) on two numbers, the compiler will dispatch evaluation to the concrete implementation, based on the types of numbers being added:

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'

In the last line, we are adding what looks like an int to a float variable. In many languages, we'd have to resort to explicit coercion (of int to float, say) to resolve this type of "mismatch". In Haskell, this is resolved by treating the value of 1 as a type-class polymorphic value:

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

1 is a generic value (a Num variable); whether 1 is an int variable or a float variable (or a fractional, say) depends on the context in which it will appear.

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 TypeIntBool = Int' Int | Bool' Bool

  f :: TypeIntBool -> String
  f (Int' v) = "Int: " ++ (show v)
  f (Bool' v) = "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)

Thanks to higher-order functions (HOF), we can easily inject behavior:

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

Here, we are defining an abstract algorithm by letting the caller pass in functions as arguments, functions that complete the detail of our algorithm. This corresponds to the strategy pattern, also concerned with decoupling an algorithm from the parts that may change.

In "OOP speak", the strategy pattern uses delegation to vary an algorithm, while the template pattern uses inheritance to vary parts of an algorithm. In Haskell, we don't have OOP inheritance, but we have something far more powerful: type classes. We might easily abstract an algorithm with this type class that acts as an abstract class:

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

The map function takes care of navigating the structure of the list, while the square function only deals with each element of the list:

map square [2, 3, 5, 7]

We have decoupled flow control from function application, which is akin to the iterator pattern.

Whenever we pass one function into another, we are decoupling two parts of code. Besides allowing us to vary the different parts at different rates, we can also put the different parts in different modules, libraries, or whatever we like.