Functional Reactive Programming

a warp speed introduction to Haskell, RxJS, and Akka

Functional programming

What is functional programming?




What is functional programming?

The sum of many things

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

More notation

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

add1 :: Int -> Int
add1 = add 1

> add1 2
3

Lambda calculus

Algebraic Data Types

Tuples

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

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!

Functor, Applicative, Monad...

But first,

The essence of Functional Programming

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?

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

While we're at it...

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

Functional Programming

Functional Reactive Programming

What is Functional Reactive Programming?

What is Functional Reactive Programming?

Functional Programming

What is Functional Reactive Programming?

Functional Programming + Time

What does all that type stuff have to do with this?

...

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

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

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

Stream combinators

Using streams

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.

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?

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)

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

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

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

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

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

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

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?

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

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

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

Hot and Cold

Backpressure

Async and Concurrent Programming

Async

Actor Model

!!!

Thank you!