Let's create a very small fragment of a programming language:

`data Expr = Num Int -- atom`

| Str String -- atom

| Op BinOp Expr Expr -- compound

deriving (Show)

data BinOp = Add | Concat

deriving (Show)

And an interpreter for it:

`interp x@(Num _) = x`

interp x@(Str _) = x

interp (Op Add a b) = Num (i a + i b)

where i x = case interp x of Num a -> a

interp (Op Concat (Str a) (Str b)) = Str (a ++ b)

Our very quick round of prototyping gave us a tiny interpreter that actually seems to work:

`>> interp (Op Add (Num 2) (Num 3))`

Num 5

Please help me to spot some problems with my interpreter!

We can construct ill-formed expressions ("add a

`Num`

to a`Str`

").Our interpreter crashes on these expressions, because we (quite reasonably) didn't take their possible existence into account.

Here's a slightly modified version of our language:

`data Expr a = Num Int`

| Str String

| Op BinOp (Expr a) (Expr a)

deriving (Show)

-- This is unchanged.

data BinOp = Add | Concat

deriving (Show)

We've introduced a type parameter here...

...But we never actually use it to represent a *value* of whatever type `a`

is.

Let's see where that takes us.

Here is our modified interpreter.

`interp x@(Num _) = x`

interp x@(Str _) = x

interp (Op Add a b) = Num (i a + i b)

where i x = case interp x of Num a -> a

interp (Op Concat a b) = Str (i a ++ i b)

where i x = case interp x of Str y -> y

Our only change is to apply `interp`

recursively if we're asked to perform a `Concat`

.

We could have done this in our original interpreter, so that can't be the real fix. But what *is*?

What's the type of the rewritten `interp`

?

The interpreter function now has this type:

`interp :: Expr a -> Expr a`

But we know from the definitions of `Expr`

and `BinOp`

that we never use a value of type `a`

. Then what purpose does this type parameter serve?

Recall the type of `Expr`

:

`data Expr a = ...`

| Op BinOp (Expr a) (Expr a)

Let's think of that `a`

parameter as expressing our *intent* that:

The operands of an

`Op`

expression should have the same types.The resulting

`Expr`

value should*also*have this type.

`data Expr a = ...`

| Op BinOp (Expr a) (Expr a)

In fact, the type system will enforce these constraints for us.

The first step in making all of this machinery work is to define some functions with the right types.

These two functions will construct atoms (values that can't be reduced any further) in our language:

`num :: Int -> Expr Int`

num = Num

str :: String -> Expr String

str = Str

These two functions construct compound expressions:

`add :: Expr Int -> Expr Int -> Expr Int`

add = Op Add

cat :: Expr String -> Expr String -> Expr String

cat = Op Concat

Notice that each one enforces the restriction that its parameters must be compatible.

One we have our functions defined, the last step is to lock our world down.

Here's what the beginning of my module looks like:

`module Interp`

(

Expr, -- type constructor

interp, -- interpreter

num, str, -- atom constructors

add, cat, -- expression constructors

) where

Notice that we've exercised *careful control* over what we're exporting.

We export the

`Expr`

type constructor, but*none*of its value constructors.Users of our module don't need

`BinOp`

, so we don't export that at all.

Consequences of exporting only the type constructor for `Expr`

:

Clients cannot use the value constructors to create new values.

The

*only*way for a client to construct expressions is using our handwritten "smart constructor" functions with their carefully chosen types.Clients cannot pattern-match on an

`Expr`

value. Our internals are opaque; we could change our implementation without clients being able to tell.

These are in fact the completely standard techniques for creating abstract data types in Haskell. So where does the type parameter come in?

Due to our judicious use of both abstraction and that type parameter:

- Clients cannot construct ill-formed expressions. Any attempts will be rejected by the type checker.

This additional safety comes "for free":

We don't need runtime checks for ill-formed expressions, because they cannot occur.

Our added type parameter never represents data at runtime, so it has zero cost when the program runs.

When we refer to a type parameter on the left of a type definition, without ever using *values* of that type on the right, we call it a *phantom type*.

We're essentially encoding *compile-time data* using types, and the compiler computes with this data before our program is ever run.

We've already seen the very handy `MVar`

type, which represents a "blocking mutable box": we can put a value in or take one out, but we'll block if we put when full or take when empty.

Even though `MVar`

s are the fastest blocking concurrent structure in the industry (they made the the Kessel Run in less than twelve parsecs!), we don't always want blocking semantics.

For cases where we want *non-*blocking updates, there's the `IORef`

type, which gives us mutable references.

`import Data.IORef`

newIORef :: a -> IO (IORef a)

readIORef :: IORef a -> IO a

writeIORef :: IORef a -> a -> IO ()

modifyIORef :: IORef a -> (a -> a) -> IO ()

Application writers are often faced with a question like this:

- I have a big app, and parts of it need their behaviour tweaked by an administrator at runtime.

There are of course many ways to address this sort of problem.

Let's consider one where we use a reference to a piece of config data.

Any code that's executing in the `IO`

monad can, if it knows the name of the config reference, retrieve the current config:

`curCfg <- readIORef cfgRef`

The trouble is, ill-behaved code could clearly also *modify* the current configuration, and leave us with a debugging nightmare.

Let's create a new type of mutable reference.

We use a phantom type `t`

to statically track whether a piece of code is allowed to modify the reference or not.

`import Data.IORef`

newtype Ref t a = Ref (IORef a)

Remember, our use of `newtype`

here means that the `Ref`

type only exists at compile time: it imposes *no* runtime cost.

Since we are using a phantom type, we don't even need values of our access control types:

`data ReadOnly`

data ReadWrite

We're already in a good spot! Not only are we creating compiler-enforced access control, but it will have *zero* runtime cost.

To create a new reference, we just have to ensure that it has the right type.

`newRef :: a -> IO (Ref ReadWrite a)`

newRef a = Ref `fmap` newIORef a

Since we want to be able to read both read-only and read-write references, we don't need to mention the access mode when writing a type signature for `readRef`

.

`readRef :: Ref t a -> IO a`

readRef (Ref ref) = readIORef ref

Of course, code can only write to a reference if the compiler can statically prove (via the type system) that it has write access.

`writeRef :: Ref ReadWrite a -> a -> IO ()`

writeRef (Ref ref) v = writeIORef ref v

This function allows us to convert any kind of reference into a read-only reference:

`readOnly :: Ref t a -> Ref ReadOnly a`

readOnly (Ref ref) = Ref ref

In order to prevent clients from promoting a reference from read-only to read-write, we do *not* provide a function that goes in the opposite direction.

We also use the familiar technique of constructor hiding at the top of our source file:

`module Ref`

(

Ref, -- export type ctor, but not value ctor

newRef, readOnly,

readRef, writeRef

) where

What does this type signature mean?

`something :: a -> a`

What are all of the possible behaviours of a code with this type?

What about this signature?

`another :: [a]`

What does this type signature mean?

`something :: a -> a`

We know that for *all possible types* `a`

, this function accepts a value of that type, and returns a value of that type.

We *clearly* cannot enumerate all possible types, so we equally clearly cannot create all (or indeed *any*) values of these types.

Therefore, if we exclude crashes and infinite loops, the only possible behaviour for this function is to return its input.

In fact, Haskell provides a keyword, `forall`

, to make this quantification over type parameters more explicit:

`something :: forall a. a -> a`

The same "universal quantification" syntax works with typeclass constraints:

`something :: forall a. (Show a) -> String`

Here, our quantifier is "for all types `a`

, where the *only thing we know about* `a`

is what the `Show`

typeclass tells us we can do".

These `forall`

keywords are implied if they're not explicitly written.

Love 'em or hate 'em, everybody has to deal with databases.

Here are some typical functions that a low-level database library will provide, for clients that have to modify data concurrently:

`begin :: Connection -> IO Transaction`

commit :: Transaction -> IO ()

rollback :: Transaction -> IO ()

We can create a new transaction with `begin`

, finish an existing one with `commit`

, or cancel one with `rollback`

.

Typically, once a transaction has been committed or rolled back, accessing it afterwards will result in an exception.

Clearly, these constructs make it easy to inadvertantly write bad code.

`oops conn = do`

txn <- begin conn

throwIO (AssertionFailed "forgot to roll back!")

-- also forgot to commit!

We can avoid `rollback`

and `commit`

forgetfulness with a suitable combinator:

`withTxn :: Connection -> IO a -> IO a`

withTxn conn act = do

txn <- begin conn

r <- act `onException` rollback txn

commit txn

return r

All right! The code running in `act`

never sees a `Transaction`

value, so it can't leak a committed or rolled back transaction.

We're not out of the woods yet!

High-performance web apps typically use a dynamically managed pool of database connections.

`getConn :: Pool -> IO Connection`

returnConn :: Pool -> Connection -> IO ()

It's a major bug if a database connection is not returned to the pool at the end of a handler.

So we write a combinator to handle this for us:

`withConn :: Pool -> (Connection -> IO a) -> IO a`

withConn pool act =

bracket (getConn pool) (returnConn pool) act

Nice and elegant. But correct? Read on!

In a typical database API, once we enter a transaction, we don't need to refer to the handle we got until we either commit or roll back the transaction.

So it was fine for us to write a transaction wrapper like this:

`withTxn :: Connection -> IO a -> IO a`

On other other hand, if we're talking to a database, we definitely need a connection handle.

`query :: Connection -> String -> IO [String]`

So we have to pass that handle into our combinator:

`withConn :: Pool -> (Connection -> IO a) -> IO a`

Unfortunately, since `withConn`

gives us a connection handle, we can defeat the intention of the combinator (sometimes accidentally).

What is the type of this function?

`evil pool = withConn pool return`

Here, we are using the `newtype`

keyword to associate a phantom type with the `IO`

monad.

`newtype DB c a = DB {`

fromDB :: IO a

}

We're going to run some code in the `IO`

monad, and pass around a little extra bit of type information at compile time.

Let's create a phantom-typed wrapper for our earlier `Connection`

type:

`newtype SafeConn c = Safe Connection`

Where are these phantom types taking us?

The easiest place to start to understand with a little use of our new code, in the form of a function we'll export to clients.

This is just a wrapper around the `query`

function we saw earlier, making sure that our `newtype`

machinery is in the right places to keep the type checker happy.

`safeQuery :: SafeConn c -> String -> DB c [String]`

safeQuery (Safe conn) str = DB (query conn str)

Notice that our phantom type `c`

is mentioned in both our uses of `SafeConn c`

and `DB c`

: we're treating it as a token that we have to pass around.

Our library will *not* be exporting the value constructors for `SafeConn`

or `DB`

to clients. Once again, this `newtype`

machinery is internal to us!

Here, we'll use our earlier exception-safe `withConn`

combinator. Recall its type:

`withConn :: Pool -> (Connection -> IO a) -> IO a`

To make it useful in our new setting, we have to wrap the `Connection`

, and unwrap the `DB c`

that is our `act`

to get an action in the `IO`

monad.

`withSafeConn pool act =`

withConn pool $ \conn ->

fromDB (act (Safe conn))

It's not at all obvious what this is doing for us until we see the type of `withSafeConn`

.

Here's a burly type for you:

`{-# LANGUAGE Rank2Types #-}`

withConnection :: Pool

-> (forall c. SafeConn c -> DB c a)

-> IO a

We've introduced a universal quantifier (that `forall`

) into our type signature. And we've added a `LANGUAGE`

pragma! Whoa. Duuude.

Relax! Let's not worry about those details just yet. What does our signature seem to want to tell us?

We accept a

`Pool`

.And an "I have a connection, so I can talk to the database now" action that accepts a

`SafeConn c`

, returning a value`a`

embedded in the type`DB c`

.

Not so scary after all. Well, except for the details we're ignoring.

Let's start with the obviously bothersome part of the type signature.

`(forall c. SafeConn c -> DB c a)`

This is the same universal quantification we've seen before, meaning:

Our "I can haz connection" action must work

*over all types*`c`

.The

*scope*of`c`

extends only to the rightmost parenthesis here.

Putting it back into context:

`withConnection :: Pool`

-> (forall c. SafeConn c -> DB c a)

-> IO a

The type variable `c`

can't escape from its scope, so `a`

*cannot be related* to `c`

.

`withConnection :: Pool`

-> (forall c. SafeConn c -> DB c a)

-> IO a

Because `SafeConn c`

shares the same phantom type as `DB c`

, and the quantified `c`

type cannot escape to the outer `IO`

, there is no way for a `SafeConn c`

*value* to escape, either!

In other words, we have ensured that a user of `withConnection`

cannot either accidentally allow or force a connection to escape from the place where we've deemed them legal to use.

Standard Haskell types and functions have just one scope for universal quantification.

`foo :: forall a b. a -> b -> a`

When an extra level of scoping for universal quantification is introduced, this is called a rank-2 type.

`fnord :: forall b. (forall a. a -> a) -> b`

(Normal types are thus called rank-1 types.)

Although widely used, rank-2 types are not yet a part of the Haskell standard, hence our use of a pragma earlier:

`{-# LANGUAGE Rank2Types #-}`

What expressions can we write that have this type?

`[forall a. a]`

What about this one?

`[forall a. (Enum a) => a]`

Or this?

`[forall a. (Num a) => a]`

Do we have time to talk about how to write a `Monad`

instance for `DB`

?

We've now seen several cases where phantom types and rank-2 types let us use the compiler to automatically prevent ourselves from writing bad code.

We can also use them to introduce safe, controlled mutation into our programs.

A typical lament of a functional programmer:

- "Alas! Woe is me! Etc., etc.! There is no known purely functional algorithm for my problem that performs as well as this seductive imperative code!"

:-(

:-(

Of course, in the worst case, we can emulate a flat, mutable memory with a purely functional map, thus incurring only *O*(log *n*) of additional overhead.

Enter the `ST`

monad!

`import Control.Monad.ST`

This defines for us a function with a glorious rank-2 type:

`>> :t runST`

runST :: (forall s. ST s a) -> a

Since we've only just been introduced to rank-2 types, we know exactly what this implies:

What happens in the

`ST`

monad*stays*in the`ST`

monad.Nevertheles, we can obtain a pure result when we run an action in this monad. That's an exciting prospect!

The `STRef`

type gives us the same mutable references as `IORef`

, but in the `ST`

monad.

`import Control.Monad.ST`

import Data.STRef

whee :: ST s Int

whee z = do

r <- newSTRef z

modifySTRef r (+1)

readSTRef r

Let's try this in `ghci`

:

`>> runST (whee 1)`

2

Thanks to chaining of the universally quantified `s`

, there is no way for an `STRef`

to escape from the `ST`

monad, save by the approved route of reading its current value with `readSTRef`

.

`newSTRef :: a -> ST s (STRef s a)`

readSTRef :: STRef s a -> ST s a

For working with large collections of uniform data, the usual representation in most languages is an array.

The longtime standard for working with arrays in Haskell is the `Array`

type, from the `array`

package, but I don't like it: it has an API that is simultaneously bizarre, too general, and puny.

I much prefer its modern cousin, the `vector`

package:

`vector`

provides a*vastly*richer API than`array`

.A

`Vector`

is one-dimensional and indexed by`Int`

s counting from zero, so it's easy to reason about.An

`Array`

is indexed by an instance of the`Ix`

class, can have arbitrary bounds, and makes my brain hurt.

The `vector`

package provides two "flavours" of vector type:

`Vector`

types are immutable.`MVector`

types can be modified in either the`ST`

or`IO`

monad, and cannot be read by purely functional code.

Within these flavours, there are two "families" of vector type:

Unboxed vectors are tightly packed in contiguous memory. They are very fast, but it is only possible to create unboxed vectors of certain types, and an unboxed vector can't store thunks.

Normal vectors are boxed, just like ordinary Haskell values. Any value can be stored in a plain old vector, at the cost of an additional level of indirection.

We can thus have an immutable unboxed vector, a mutable boxed vector, and so on.

The classic Haskell implementation of a "quicksort":

`import Data.List (partition)`

qsort (p:xs) = qsort lt ++ [p] ++ qsort ge

where (lt,ge) = partition (<p) xs

qsort _ = []

This isn't *really* a quicksort, because it doesn't operate in-place.

We can apply our newfound knowledge to this problem:

`import qualified Data.Vector.Unboxed.Mutable as V`

import Control.Monad.ST (ST)

quicksort :: V.MVector s Int -> ST s ()

quicksort vec = go 0 (V.length vec)

where

{- ... -}

` recur left right`

| left >= right = return ()

| otherwise = do

idx <- partition left right

(left + (right-left) `div` 2)

recur left (idx-1)

recur (idx+1) right

(Remember, `vec`

is in scope here.)

` partition left right pivotIdx = do`

pivot <- V.read vec pivotIdx

V.swap vec pivotIdx right

let loop i k

| i == right = V.swap vec k right >>

return k

| otherwise = do

v <- V.read vec i

if v < pivot

then V.swap vec i k >>

loop (i+1) (k+1)

else loop (i+1) k

loop left left

We can even use this in-place sort to efficiently perform an in-place sort of an immutable array!

Our building blocks:

`thaw :: Vector a -> ST s (MVector s a)`

create :: (forall s. ST s (MVector s a)) -> Vector a

`thaw`

creates a new mutable vector, and copies the contents of the immutable vector into it.`create`

runs an`ST`

action that returns a mutable vector, and "freezes" its result to be immutable, and hence usable in pure code.

`import qualified Data.Vector.Unboxed as U`

vsort :: U.Vector Int -> U.Vector Int

vsort v = U.create $ do

vec <- U.thaw v

quicksort vec

return vec

The big advantage of the `ST`

monad is that it gives us the ability to efficiently run computations that require mutability, while both the inputs to and results of our computations remain pure.

In order to achieve this, we sacrifice some power:

We can't run arbitrary

`IO`

actions. No database accesses, no filesystem, etc.Other potential sources of nondeterminism (e.g. threads) are thus also off limits.

Originally, this lecture was supposed to be all about the joys of lazy evaluation, but we hijacked much of our time to serve other purposes.

I'm going to talk a little bit about it anyway.

In a minute.

How can we use random numbers to approximate the value of π?

How can we use random numbers to approximate the value of pi?

Take two random numbers,

*x*and*y*, on the interval [0, 1]Add their squares:

*r*=*x*^{2}+*y*^{2}We have a π / 4 probability of

*r*≤ 1

What can we do with this knowledge?

Haskell supplies a `random`

package that we can use in a purely functional setting.

`class Random a where`

random :: RandomGen g => g -> (a, g)

class RandomGen g where

next :: g -> (Int, g)

split :: g -> (g, g)

The `RandomGen`

class is a building block: it specifies an interface for a generator that can generate uniformly distributed pseudo-random `Int`

s.

There is one default instance of this class:

`data StdGen {- opaque -}`

instance RandomGen StdGen

The `Random`

class specifies how to generate a pseudo-random value of some type, given the random numbers generated by a `Gen`

instance.

Quite a few common types have `Random`

instances.

For

`Int`

, the instance will generate any representable value.For

`Double`

, the instance will generate a value in the range [0, 1].

Since we want to use a PRNG in pure code, we obviously can't modify the state of a PRNG when we generate a new value.

This is why `next`

and `random`

return a *new* state for the PRNG every time we generate a new pseudo-random value.

Here's how we can generate a guess at *x*^{2} + *y*^{2}:

`guess :: (RandomGen g) => (Double,g) -> (Double,g)`

guess (_,g) = (z, g'')

where z = x^2 + y^2

(x, g') = random g

(y, g'') = random g'

Note that we have to hand back the *final* state of the PRNG along with our result!

If we handed back `g`

or `g'`

instead, our numbers would either be all identical or disastrously correlated (every `x`

would just be a repeat of the previous `y`

).

We can use the `getStdGen`

function to get a handy global PRNG state:

`getStdGen :: IO StdGen`

This does *not* modify the state, though. If we use `getStdGen`

twice in succession, we'll get the same result each time.

To be safe, we should update the global PRNG state with the final PRNG state returned by our pure code:

`setStdGen :: StdGen -> IO ()`

Calling `getStdGen`

and `setStdGen`

from `ghci`

is a pain, so let's write a combinator to help us.

Remember that `split`

method from earlier?

`class RandomGen g where`

split :: g -> (g, g)

This "forks" the PRNG, creating two children with different states.

The hope is that the states will be different enough that pseudo-random values generated from each will not be obviously correlated.

`withGen :: (StdGen -> a) -> IO a`

withGen f = do

g <- getStdGen

let (g',g'') = split g

setStdGen g'

return (f g'')

Now we can use our `guess`

function reasonably easily.

`>> let f = fst `fmap` withGen (guess . ((,) 0))`

>> f

1.2397265526054513

>> f

0.9506331164887969

Here's a useful function from the `Prelude`

:

`iterate :: (a -> a) -> a -> [a]`

iterate f x = x : iterate f (f x)

Obviously that list is infinite.

Let's use `iterate`

and `guess`

, and as much other `Prelude`

machinery as we can think of, to write a function that can approximate π.

By the way, in case you don't recognize this technique, it's a famous example of the family of Monte Carlo methods.

What aspects of laziness were important in developing our solution?