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

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

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

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]

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!

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

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

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

What is Functional Reactive Programming?

What is Functional Reactive Programming?

Functional Programming

What is Functional Reactive Programming?

Functional Programming + Time

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

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

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.

• 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 `JVal`s 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?

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

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

Hot and Cold

Backpressure