- Programming with functions*, meaning...

* of the mathematical type

- Functions == Data

- Enabling a wide range of expressive abstractions

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)

- Learn the basics of FP in Haskell
- Higher order functions
- Higher kinded types

- Use those techniques to do cool stuff with
- FRP: Reactive Extensions for JavaScript
- Concurrency: Scala Actors, Akka library

`::`

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`

`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
```

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`

A mathematical definition of data using concepts from set theory.

Enables

*pattern matching*on the type constructorSum (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`

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)
```

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`

...

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
```

d/dx at a point

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

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 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 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
```

```
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
```

```
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);
```

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]
```

Map is a structure preserving transformation over a collection

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

Map is a structure preserving transformation over a **collection**

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

Map is a structure preserving transformation over a **collection**

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

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 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 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
```

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`

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

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

`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**.

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

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!

**Functions as Data**

**Functions as Data**

**Functions as Data** + **Data as Computations**

A hierarchy of *computational contexts*

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]
```

**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.

**Monad**

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

**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.

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."

A nice way of writing monadic code

```
printChar :: IO ()
printChar = getChar >>= putChar
printChar1 = do
c <- getChar
putChar c
```

```
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.

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

```
-- 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)
```

```
-- 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).

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 `fmap`

ped 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*

A **Monoid** is a category that has

- an identity element (
`mempty`

) and - 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
```

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

The core abstraction behind Reactive Programming is the *Stream*

The core abstraction behind Reactive Programming is the *Stream*

`data Stream a = SCons a (Stream a)`

This looks suspicious...

`data Stream a = SCons a (Stream a)`

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!!

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...

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);
```

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);
```

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 ....`

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)
....
```

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.*

In `Rx`

, a `Stream`

is instead known as an `Observable`

.

`Rx`

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

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.

Ways to build streams (all in `Rx.Observable`

unless otherwise noted):

`empty()`

`from(), fromArray(), fromCallback(), fromEvent(),`

`fromPromise(),`

`Rx.DOM.getJSON(), Rx.DOM.fromEventSource()`

**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?

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)`

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

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

```
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.

Recall the Stream type

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

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.

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 `JVal`s recursively
```

What we really want is a stream of

`SCons`

es,`SCons jval1 (SCons jval2 (SCons jval3 (...)))`

From `Single (JArr jvals)`

=> `SCons jval1 (SCons jval2 (SCons jval3 (...)))`

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?

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)`

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 (...)))`

```
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`

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

`concatMap`

ping`toStream`

over the`Single`

streamBut 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.)

```
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.

Let's calculate what happens by substitution

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

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

```
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!

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