# Functional programming

## What is functional programming?

• Programming with functions*, meaning...
* of the mathematical type
• Functions == Data
• Enabling a wide range of expressive abstractions

## What is functional programming?

The sum of many things

• A focus on reducing and constraining mutable state
• An informal mathematical reasoning framework for code
• A set of techniques to compose programs from abstract, highly recyclable little pieces
• A fluid style of programming, where programs are expressed as a composition of transformations on data structures
• A style of programming, not a rigid "paradigm"
• Functional capabilities often complimentary (or as we like to say, orthogonal)

## Plan

1. Learn the basics of FP in Haskell
• Higher order functions
• Higher kinded types

1. Use those techniques to do cool stuff with

## Some notation

• :: denotes "type of"
• -> denotes a function
• a,b,c... denote polymorphic type variables;
concrete types are capitalized: Double, MVar
• foo :: a -> a
A function that takes an argument from type a to type a
• There is only one function of this type! Can you guess what it is?
•   id :: a -> a
id x = x

## More notation

• abc :: a -> b -> c
A function abc that takes two arguments, first of type a, second of type b, and produces a result of type c

• Function application is just f arg1 arg2 ...

• Functions are curried, which means you can "partially fill it in", and get back another function

add :: Int -> Int -> Int
add a b = a + b

add1 :: Int -> Int
add1 = add 1

> add1 2
3

## Lambda calculus

• The essence of computation (Church-Turing thesis, 1936)

• \ is lambda ($$\lambda$$), which makes an anonymous function. Function definitions are just sugar for explicit lambdas.

• These are all equivalent:

constP     :: Char -> f -> Parser f
constP c f =         symbol c >> return f
constP c   = \f   -> symbol c >> return f
constP     = \c f -> symbol c >> return f

## Algebraic Data Types

• A mathematical definition of data using concepts from set theory.

• Enables pattern matching on the type constructor

• Sum (disjoint union): $$A \cup B$$

data Number = I Int
| D Double
• Product (Cartesian product): $$A \times B$$ aka tuples, records

data Point = P Int Int

## Tuples

• Syntactic sugar for a product type

• Constrained multiple return values (with optionally different types)

-- Pair of Ints
-- _ :: (Int, Int)
(1,2)

-- Triple of a Maybe, an IO action, and an Int
-- _ :: (Maybe Animal, IO (), Int)
(Just Cat, print "Hello World!", 42)

## Lists

The workhorse data structure in FP is the singly linked list

data List a = Nil | Cons a (List a)

-- syntactic sugar
-- Nil       = []
-- Cons x xs = x : xs

-- accessor functions
head (x:xs) = x      -- car
tail (x:xs) = xs     -- cdr

Naming conventions

• If a single object is x, a list of them is xs.
• Further lists are ys, zs...
• A list of lists is xss, a list of lists of lists is xsss...

## Obligatory examples

All of Haskell in one function

quicksort :: (Ord a) => [a] -> [a]
quicksort []     = []
quicksort (x:xs) =
let (sm, gt) = partition (\e -> e <= x)
in  quicksort sm ++ [x] ++ quicksort gt

## Obligatory examples

d/dx at a point

diff :: (Fractional a) => a -> (a -> a) -> (a -> a)
diff h f = \x -> (f (x+h) - f x) / h

# Higher Order Functions

## Filter

Filter gets rid of things in a collection

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = case xs of
[]     -> []
(x:xs) -> if (p x) then x : filter p xs
else              filter p xs

> let xs = [1..20]
> filter (> 10) xs
[11,12,13,14,15,16,17,18,19,20]

## Map

Map is a structure preserving transformation over a collection

map :: (a -> b) -> [a] -> [b]
map f xs = case xs of
[]     -> []
(x:xs) -> f x : map f xs

> let xs = [1..20]
> map (*2) xs
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40]

## Reduce

Reduce is a non-structure preserving transformation over a collection. It is the most general of the three ubiquitous HOFs.

Usually used for aggregation. (Also called fold, collect...)

-- Right associative
reduceR :: (a -> b -> b) -> b -> [a] -> b
reduceR f acc xs = case xs of
[]     -> acc
(x:xs) -> f x (reduceR f acc xs)

-- Left associative (and tail recursive)
reduceL :: (a -> b -> b) -> b -> [a] -> b
reduceL f acc xs = case xs of
[]     -> acc
(x:xs) -> reduceL f (f x acc) xs

> let sum1 = reduceL (\x acc -> x + acc) 0
> sum1 [1,2,3,4]
10

## The other two in terms of reduce

map f xs = let f' y ys = (f y) : ys
in reduce f' [] xs

filter p xs = let f' y ys = if (p y) then y : ys
else              ys
in reduce f' [] xs

## Javascript examples

var xs = _.range(20);

// use map to build a new list
var by2 = xs.map(function (x) {
return x * 2;
});

// use forEach for side effects
xs.forEach(function (x) {
console.log('Value is: ' + x);
});

var evens = xs.filter(function (x) {
return x % 2 == 0;
});

var sum = xs.reduce(function (acc, x) {
return acc + x;
}, 0);

## Zip

Useful for collapsing multiple lists into one, even more useful for composing streams.

zip :: [a] -> [b] -> [(a,b)]
zip _      []     = []
zip []      _     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f  _      []    = []
zipWith f  []     _     = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

> let fs    = [(+1), (+2), (+3), (+4)]
> let nums  = [1,2,3,4]
> let apply = zipWith (\$)
> fs apply nums
[2,4,6,8]

# Typeclasses and Higher Kinded Types

## Map, again

Map is a structure preserving transformation over a collection

map :: (a -> b) -> [a] -> [b]

## Map, again

Map is a structure preserving transformation over a collection

map :: (a -> b) -> List a -> List b

## Map, again

Map is a structure preserving transformation over a collection

map     :: (a -> b) -> List a -> List b
treeMap :: (a -> b) -> Tree a -> Tree b

## Map, again

Map is a structure preserving transformation over a collection

map       :: (a -> b) -> List a   -> List b
treeMap   :: (a -> b) -> Tree a   -> Tree b
vectorMap :: (a -> b) -> Vector a -> Vector b

## Map, again

Map is a structure preserving transformation over a container

map       :: (a -> b) -> List a   -> List b
treeMap   :: (a -> b) -> Tree a   -> Tree b
vectorMap :: (a -> b) -> Vector a -> Vector b
maybeMap  :: (a -> b) -> Maybe a  -> Maybe b

## Map, again

Map is a structure preserving transformation over a container

map        :: (a -> b) -> List a    -> List b
treeMap    :: (a -> b) -> Tree a    -> Tree b
vectorMap  :: (a -> b) -> Vector a  -> Vector b
maybeMap   :: (a -> b) -> Maybe a   -> Maybe b
promiseMap :: (a -> b) -> Promise a -> Promise b

## Generalizing map

Map is a structure preserving transformation over a container

map        :: (a -> b) -> List a    -> List b
treeMap    :: (a -> b) -> Tree a    -> Tree b
vectorMap  :: (a -> b) -> Vector a  -> Vector b
maybeMap   :: (a -> b) -> Maybe a   -> Maybe b
promiseMap :: (a -> b) -> Promise a -> Promise b

boxedMap :: (Box z) => (a -> b) -> z a -> z b

## Generalizing map

boxedMap :: (Box z) => (a -> b) -> z a -> z b

## Generalizing map

fmap :: (Functor f) => (a -> b) -> f a -> f b

## Generalizing map

fmap :: (Functor f) => (a -> b) -> f a -> f b

Such a container is known as a Functor, and the map operation is called Functor map.

## Functor

A (higher kinded) type is a functor if it can be "mapped over".

Indeed, the definition of the Functor typeclass* is

class Functor f where
fmap :: (a -> b) -> f a -> f b

instance Functor List where
fmap = map

* Think interfaces

## Functor

A (higher kinded) type is a functor if it can be "mapped over".

Indeed, the definition of the Functor typeclass is

class Functor f where
fmap :: (a -> b) -> f a -> f b

instance Functor List where
fmap = map       -- map :: (a -> b) -> [a] -> [b]

All commonly used types are functors

List a, Tree a, Hashmap k v,...   -- Collections
Maybe a, Either e a,...           -- Error containers
Promise a, Actor a, Stream a,...  -- Concurrency, Reactive

Get rid of your for loops!

# But first,

## The essence of Functional Programming

Functions as Data

## The essence of Pure Functional Programming

Functions as Data

## The essence of Pure Functional Programming

Functions as Data + Data as Computations

# Functor, Applicative, Monad...

## Functor, Applicative, Monad

A hierarchy of computational contexts

## Functor, Applicative, Monad

A hierarchy of computational contexts

Functor: a data context to which functions can be applied, i.e. just a container type.

class Functor f where
fmap :: (a -> b) -> f a -> f b   -- apply to lifted

instance Functor List where
fmap = map

> fmap (+1) [1,2,3,4]
[2,3,4,5]

## Functor, Applicative, Monad

Applicative Functor: a Functor that you can apply, i.e. a function lifted to the same context

-- Applicative is an extension of Functor
class (Functor f) => Applicative f where
pure  :: a -> f a                   -- lift
(<*>) :: f (a -> b) -> f a -> f b   -- apply in lifted

instance Applicative List where
pure x     = [x]
fs <*> xs  = concatMap (flip map xs) fs

> pure (+1) <*> [1,2,3,4]
[2,3,4,5]

> [(+1), (+2)] <*> [1,2,3,4]
[2,3,4,5,3,4,5,6]

This is a computation inside the context.

## Functor, Applicative, Monad

Monad

class (Functor f) => Applicative f where
pure  :: a -> f a                   -- lift
(<*>) :: f (a -> b) -> f a -> f b   -- apply in lifted

## Functor, Applicative, Monad

Monad

class (Functor f) => Applicative f where
pure  :: a -> f a                   -- lift
(<*>) :: f (a -> b) -> f a -> f b   -- apply in lifted

class Monad m where
return :: a -> m a                  -- lift
(>>=)  :: m a -> (a -> m b) -> m b  -- "bind"

Looks very similar! The only difference is in the asymmetry of the function argument in <*> and >>=. In general,

Applicative's <*> runs computations in a lifted context.

Monad's >>= chain computations together.

## "Running" a monad

In addition to data, Monads capture actions in Haskell. A monad m a can either be viewed as a container for a, or an action that returns an a.

The >>= function is as a combinator for sequencing actions.

-- when evaluated, will perform an IO action
getChar :: IO Char
putChar :: Char -> IO ()

printChar :: IO ()
printChar = getChar >>= \c -> putChar c

This says: "Run the getChar action, and when it succeeds with input from the user, send the char to putChar to print it to the screen."

## do Notation

A nice way of writing monadic code

printChar :: IO ()
printChar = getChar >>= putChar

printChar1 = do
c <- getChar
putChar c

## List monad

class Monad m where
return :: a -> m a                  -- lift
(>>=)  :: m a -> (a -> m b) -> m b  -- "bind"

instance Monad List where
return x = [x]
(>>=)    = flip concatMap

cartesianProd :: [a] -> [b] -> [(a,b)]
cartesianProd xs ys = do
x <- xs                 -- for every x in xs
y <- ys                 -- for every y in ys
return (x,y)            -- produce a pair (x,y)

What does cartesianProd remind you of?

• That's right, loops are a special case: an iteration through a Traversable Monad.

## Scala's for-loop

-- Haskell
cartesianProd :: [a] -> [b] -> [(a,b)]
cartesianProd xs ys =
do { x <- xs
; y <- ys
; return (x,y) }

## Scala's for-loop

-- Haskell
cartesianProd :: [a] -> [b] -> [(a,b)]
cartesianProd xs ys =
do { x <- xs
; y <- ys
; return (x,y) }

/* Scala */
cartesianProd(xs: List[A], ys: List[B]): List[(A,B)] =
for { x <- xs
; y <- ys
} yield (x,y)

## Scala's for-loop

-- Haskell
cartesianProd :: [a] -> [b] -> [(a,b)]
cartesianProd xs ys =
do { x <- xs
; y <- ys
; return (x,y) }

/* Scala */
cartesianProd(xs: List[A], ys: List[B]): List[(A,B)] =
for { x <- xs
; y <- ys
} yield (x,y)

ta-dah! Scala's looping constructs are actually syntactic sugar over higher order functions (defined in terms of monadic operations).

## Scala's monadic bind

In Scala, bind is known as flatMap: because the result of binding a function to a monad flattens the otherwise nested structure.

This is also seen in the definition of >>= in the List monad with concatMap (Haskell's version of flatMap).

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

If we treated the monad as a functor and just fmapped over it, the return type would be

-- (flip fmap) :: (Functor f) => f a -> (a -> b) -> f b

-- reified type
nonFlatMap :: (Functor m, Monad m)
=> m a -> (a -> m b) -> m (m b)
nonFlatMap =  flip fmap

Which introduces a layer of nesting

## Monoid and MonadPlus

A Monoid is a category that has

1. an identity element (mempty) and
2. a closed binary operation (mappend).
class Monoid m where
mempty  :: m
mappend :: m -> m -> m

instance Monoid List where
mempty  = []
mappend = (++)

A MonadPlus is a Monad that is also a Monoid. These represent datum and computations that are closed under concatenation.

mconcat :: (Monoid m) => [m] -> m
mconcat = foldl mappend mempty

## Foldable*

We can then use Monoid to generalize reduce (just as Functor generalizes map).

class Foldable t where
foldMap :: Monoid m => (a -> m) -> t a -> m

This says:

"A collection of type t is reducible if the type m of the things stored in it is closed under concatenation (is a Monoid).

Furthermore, if you can provide a transformation from an a to an m, then a collection of type t a can also be reduced."

The foldMap function does both the map and reduce steps at once!

* reduce is known as fold in Haskell

# ...

## Reactive Streams

The core abstraction behind Reactive Programming is the Stream

## Reactive Streams

The core abstraction behind Reactive Programming is the Stream

data Stream a = SCons a (Stream a)

## Reactive Streams

This looks suspicious...

data Stream a = SCons a (Stream a)

## Reactive Streams

This looks suspicious...

data Stream a = SCons a (Stream a)
data List   a =  Cons a (List a  ) | Nil
• *drumroll*
• A stream is just a lazy infinite list!!

## Reactive Streams

Actually, more like this

data Stream a = Empty
| Single a
| SCons  a (Stream a)
| Frozen   (Stream a)

data List   a =  Cons a (List a) | Nil

but still...

## A taste of FRP

Remember this?

// all of these are *Lists*
var xs = _.range(20);

var by2 = xs.map(function (x) {
return x * 2;
});

var evens = xs.filter(function (x) {
return x % 2 == 0;
});

var sum = xs.reduce(function (acc, x) {
return acc + x;
}, 0);

## A taste of FRP

Here it is on Streams

// all of these are *Streams*
var xs = Rx.Observable.range(0,20);

var by2 = xs.map(function (x) {
return x * 2;
});

var evens = xs.filter(function (x) {
return x % 2 == 0;
});

var sum = xs.reduce(function (acc, x) {
return acc + x;
}, 0);

## List -> Stream

Streams have the same properties and operations as the lists that you've come to know and love

• It is a Functor

instance Functor Stream where
fmap f  Nil         = Nil
fmap f (Single x  ) = Single (f x)
fmap f (SCons x xs) = SCons (f x) (fmap f xs)
....
• It is Applicative

instance Applicative Stream where
pure x          = Single x
Nil <*> _       = Nil
Single f <*> xs = fmap a xs
....

## List -> Stream

Streams have the same properties and operations as the lists that you've come to know and love

It is a Monad and also MonadPlus

instance Monad Stream where
return    = pure

Nil       >>= _ = Nil
Single x  >>= f = f x
Cons x xs >>= f = f x mplus Frozen (xs >>= f)
....

instance MonadPlus Stream where
mzero = Nil

mplus Nil          ys = Frozen ys
mplus (Single x)   ys = SCons x ys
mplus (SCons x xs) ys = SCons x (mplus ys xs)
....

# Reactive Extensions

Now that we know what the type of a Stream is, let us examine the implementation of Reactive Streams for front-end web programming as embodied in the excellent RxJS library.

Actual Rx code examples will be in Javascript, but I'll keep the Haskell for exposition.

## Rx Types

In Rx, a Stream is instead known as an Observable.

Rx uses a publish/subscribe model, aka the Observer pattern.

## Stream combinators

A combinator is a reusable, generic building block.

We've seen the usual suspects: map, fold, filter, ....

Let's look at more ways to build and work with streams.

## Stream combinators

Ways to build streams (all in Rx.Observable unless otherwise noted):

• empty()
• from(), fromArray(), fromCallback(), fromEvent(),
fromPromise(),
• Rx.DOM.getJSON(), Rx.DOM.fromEventSource()

## Example

Problem: A GET request will produce a massive JSON array, which we then have to parse and display. The parsing and rendering takes forever, during which it will block the main thread.

jQuery.get('/getMassiveArray', function (data) {
var pData = JSON.parse(data);
var fData = pData.map(formatData); // this is really slow
updateChart(fData)                 // also really slow
updateTable(fData)                 // also really slow
});

How can reactive programming help?

## Example

First, let's not get a block of data, but instead a stream.

var massiveArrayStream = Rx.DOM
.getJSON('/getMassiveArray');

the getJSON method parses things for us automatically.

• Remember that the stream is not evaluated until we say so! Rx streams are always created with type constructor Frozen (Stream a)

## Example

Problem This stream won't actually stream the array like we want it to. Why?

var massiveArrayStream = Rx.DOM
.getJSON('/getMassiveArray');

## Types to the rescue

var massiveArrayStream = Rx.DOM
.getJSON('/getMassiveArray');

What is the type of this stream?

• The sharp reader will realize that because the original GET returns ONE thing, this stream version will also contain only ONE thing.

## Types to the rescue

Recall the Stream type

data Stream a = Empty
| Single a
| SCons  a (Stream a)
| Frozen   (Stream a)


## Types to the rescue

Recall the Stream type

data Stream a = Empty
| Single a
| SCons  a (Stream a)
| Frozen   (Stream a)


The corresponding type constructor pattern for massiveArrayStream is Frozen (Single xs)

• When evaluated, it will just dump out the whole of xs at once.
• Because Frozen is implicit in Rx, we'll drop it going forwards.

## Extending the Stream

Let's look at the stream (and the JSON data type) through pattern matching in Haskell

data JVal = JStr String
| JNum Double
| JBln Bool
| JObj [(String, JVal)]
| JArr [JVal]

datas :: Stream JVal
datas = Frozen (Single array)
where array = JArr jvals
-- and jvals is a list of JVals recursively
• What we really want is a stream of SConses,

SCons jval1 (SCons jval2 (SCons jval3 (...)))

## Extending the Stream

From Single (JArr jvals) => SCons jval1 (SCons jval2 (SCons jval3 (...)))

## Extending the Stream

From Single (JArr jvals) => SCons jval1 (SCons jval2 (SCons jval3 (...)))

Attempt 1:

var datas = Rx.DOM
.getJSON('/getMassiveArray')
// the from method makes a new Stream from an array
.map(Rx.Observable.from);
• Why is this wrong?

## Extending the Stream

For convenience, let's say that JArrs are native (as they are in Javascript)

datas :: Stream [JVal]
datas = Single jvals    -- a list of JVals

-- Rx.Observable.from
toStream :: [a] -> Stream a
toStream []     = Nil
toStream (x:xs) = SCons x (toStream xs)

datas' = fmap toStream datas

What is the type of datas'?

• datas' :: Stream (Stream JVal)

## Extending the Stream

In Haskell

datas :: Stream [JVal]
datas = Single jvals

-- Rx.Observable.from
toStream :: [a] -> Stream a
toStream []     = Nil
toStream (x:xs) = SCons x (toStream xs)

datas' :: Stream (Stream [JVal])
datas' = fmap toStream datas

What is the structure of datas'?

• datas' ==> Single (SCons jval1 (SCons jval2 (...)))

## Reasoning with types

toStream :: [a] -> Stream a
-- reify for streams
fmap     :: (a -> b) -> Stream a -> Stream b

datas   :: Stream [JVal]
datas'  :: Stream (Stream JVal)
datas'' :: Stream JVal            -- want this
• We instead want to peel off the outer stream layer in the process
• Remember a function that does that?
• (>>=)     :: m a -> (a -> m b) -> m b
concatMap :: (a -> [b]) -> [a] -> [b]
flatMap   :: (a -> m b) -> m a -> m b
(=<<)     :: (a -> m b) -> m a -> m b

## concatMap, flatMap, and bind: a duality of interpretation

(>>=)     :: m a -> (a -> m b) -> m b
concatMap :: (a -> [b]) -> [a] -> [b]
flatMap   :: (a -> m b) -> m a -> m b
(=<<)     :: (a -> m b) -> m a -> m b
• In spirit, what we are doing is concatMapping toStream over the Single stream

• But our stream operations are more general than that

• concatMap / flatMap feel like data operations, whereas bind feels more like an action operation.

• Lesson: Monads are data, so actions are data!

• (Which is why bind and concatMap are one and the same in Scala.)

## flatMapping streams

datas'' = datas >>= toStream

-- or if you prefer,
datas'' = do
d <- datas
toStream d

if you examine the definition of >>= for the Stream monad

instance Monad Stream where
return    = pure

Nil       >>= _ = Nil
Single x  >>= f = f x
Cons x xs >>= f = f x mplus Frozen (xs >>= f)

you'll see that it is concatMap for streams.

## Not convinced?

   datas >>= toStream
=> Single jvals >>= toStream
=> toStream jvals
=> toStream (j1 : js)  -- match
=> SCons j1 (toStream js)
=> ...
=> SCons j1 (SCons j2 (... (SCons jn_1 SNil)))

## Example

It turns out that we do have a flatMap for streams

var datas = Rx.DOM
.getJSON('/getMassiveArray')
// the from method makes a new Stream from an array
.flatMap(Rx.Observable.from);
• Now let's format each data point coming in

## Example

var datas = Rx.DOM
.getJSON('/getMassiveArray')
// the from method makes a new Stream from an array
.flatMap(Rx.Observable.from);
.map(formatOnePoint);

The stream is ready for use!

## Example

var datas = Rx.DOM
.getJSON('/getMassiveArray')
// the from method makes a new Stream from an array
.flatMap(Rx.Observable.from);
.map(formatOnePoint);