Functional Programming

intro

Oleh Makarov

github.com/lgmkr

gstancox@gmail.com

"JavaScript has more in common with functional languages like Lisp or Scheme than with C or Java". — Douglas Crockford in JavaScript: the World’s Most Misunderstood Language

Functional Programming is all about programming with functions.

Functional programming is a programming paradigm that follows a more mathematical computation model.

Wiki: Functional programming is a programming paradigm - a style of building the structure and elements of computer programs- that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions or declarations instead of statements.

Imperative

Declarative

 

    const list = [ 1, 2, 3 ];
    
    // imperative style
    const imperative = list[0];
    
    // declarative style
    const declarative = firstElement(list);

what you want instead of how you want it

    // imperative
    let makes = [];
    for (let i = 0; i < cars.length; i++) {
      makes.push(cars[i].make);
    }
    
    
    // declarative
    let makes = cars.map(function(car) { return car.make; });

 we will write expressions, as opposed to step by step instructions

Concepts

  • Pure Functions
  • First-class/Higher Order Functions
  • Function Composition
  • Closure
  • Currying and Partial Application
  • Data Immutability
  • Recursive Functions
  • Lazy evaluation
  • Memoization
  • Algebraic Data Types
  • etc

What is a Function ?

Math: f(x) = 2x

JS, please: const double = x => x * 2

A function maps input values to output values

Ok, a Pure Function ?

  • Given the same input, will always return the same value 
double(2) //=> 4
double(2) //=> 4
double(2) //=> 4
...
double(5) //=> 10
double(5) //=> 10
double(5) //=> 10
...
  • No Side Effects

which means that it can’t alter any external state

modify a global variable

raise an exception 

write/read data to/from file

ajax

localStorage

Why Pure Functions ?

  • Composability, ​one function can be connected to another.
  • Can run in parallel, multi-threading, multi-core, GPU and distributed systems.
  • Better debugging and testing.
  • Predictability (referential transparency )

First-class functions

You can pass them into other functions as parameters:

You can assign a function as a value to a variable:

You can return a function:

function runFunction(fn, data) {
  return fn(data);
}
var myFunc = function() {
  // do something
};
const myNewGenFunc = someParam => someParam;
function takeFirst(f, g) {
   return f;
}

Higher Order Functions

A function is a higher order function if it takes a function as a parameter, or returns a function as its result.

Array#map

Array#filter

Array#reduce

Examples

map

filter

reduce

const arr = [1, 2, 3];
const square = x => x * x;
const squared = arr.map(square); //=>[1, 4, 9]

const arr = [1, 2, 3, 4];
const isEven = num => num % 2 === 0;
const result = arr.filter(isEven); //=> [2, 4]
const numbers = [1, 2, 5];
const sum = numbers.reduce((prev, curr) => prev + curr, 0); //=> 8

Function Composition

Composition: “The act of combining parts or elements to form a whole.” ~ Dictionary.com

const increment = (x) => x+1;
const double = (x) => x*2;
const half = (x) => x/2;

const calculate = half(double(increment(3))); //=> 4

Function Composition (helpers)

// helpers

const compose = (...functions) => data =>
  functions.reduceRight((value, func) => func(value), data)

const pipe = (...functions) => data =>
  functions.reduce((value, func) => func(value), data)

// computations

const increment = (x) => x+1;
const double = (x) => x*2;
const half = (x) => x/2;

const calculate = half(double(increment(3))); // 4

const calculateWithCompose = compose(half, double, increment)(3); // 4

const calculateWithPipe = pipe(increment, double, half)(3); // 4

Function Composition (helpers)

half(double(increment(3)));

compose(half, double, increment)(3)

pipe(increment, double, half)(3)

RIGHT-TO-LEFT

LEFT-TO-RIGHT

example

Closure(scope)

A language implements static scope, if only by looking at the source code one can determine in which environment a binding is resolved.

Is the accessibility of variables, functions, and objects in some particular part of your code during runtime.

function sum() {
    var a = 1; 
    var b = 2;
    function logSum() { 
        console.log(a+b); 
    }
    logSum();    
}
sum(); // 3
let x = 1;
 
function foo() {
  console.log(x);
}
 
function bar(fn) {
  let x = 2;
  fn(); 
}
 
bar(foo); // 1, not 2!

And that is the scope of the creation time

Closure(scope)

Closure

//es5
function foo(a, b) {
  return function () {
    return a + b;
  }
} 

var sum = foo(4,5);
sum();  //=> 9
sum();  //=> 9



//es6
const foo = (a, b) => () => a + b;
const sum = foo(4, 5);
sum(); //=> 9
sum(); //=> 9

A closure is the combination of a function and the lexical environment within which that function was declared.

Currying

Сurrying is the process of breaking down a function into a series of functions that each take a single argument.

const sum = (x, y, z) => x + y + z;
sum(1, 2, 3); //=> 6

// es5
const sum = function(x) {
   return function(y) {
     return function(z) {
       return x + y +z;
     }
   }
}

sum(1)(2)(3) //=> 6

// es6
const sum = x => y => z => x + y + z;
sum(1)(2)(3) //=> 6
sum(1);
//=> [ Function ]

sum(1)(2);
//=> [ Function ]

sum(1)(2)(3);
//=> 6
// lodash, baby

_.curry(sum)

sum(1, 2, 3) //=> 6
sum(1, 2)(3) //=> 6
sum(1)(2, 3) //=> 6
sum(1)(2)(3) //=> 6

Partial (Function) Application

In computer science, partial application refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.

let add = x => y => x+y;

let increment = add(1);
let incrementBy2 = add(2);

increment(3);    //=> 4
incrementBy2(3); //=> 5
// lodash partial
function greet(greeting, name) {
  return greeting + ' ' + name;
}
 
var sayHelloTo = _.partial(greet, 'hello');
sayHelloTo('fred');
// => 'hello fred'
 
// Partially applied with placeholders.
var greetFred = _.partial(greet, _, 'fred');
greetFred('hi');
// => 'hi fred'

Currying and Partial Application(Ex1, Ex2)

Immutability (principles)

  • Data is immutable. It is never mutated in-place.
  • Changes to data are encapsulated into operations that take a previous version and return a new one.
  • History is represented as a list of states,
  • Modifying data causes any future states to be thrown away.

Immutability (pros)

  • Safer code (No invalid state)
  • Comparing state difference is as easy as comparing their references
  • Easier to Debug
  • Undo / Redo (Back-tracking made easy with persistent data)

  • Thread safety

Immutability (cons)

Performance

Copying wastes time and space

Immutability (javascript)

// Assignment immutability

const z = [1, 2, 3]
z = [4, 5, 6] // not allowed
// TypeError:Assignment to constant variable

z[0] = 4 // allowed [4, 2 ,3]

// Value immutability (shallow)

const f = Object.freeze([1, 2, 3]);
f[0] = 4 // not allowed 
console.log(f) // [1, 2, 3]


const fs = Object.freeze([1, 2, 3, [4, 5, 6]]);
fs[0] = 4 // not allowed
fs[3][0] = 1 // allowed
console.log(fs) // [1, 2, 3, [1, 5, 6]]

Immutability (libs)

seamless-immutable

Immutable JS data structures which are backwards-compatible with normal Arrays and Objects.

var array = Immutable(["totally", "immutable", {hammer: "Can’t Touch This"}]);

array[1] = "I'm going to mutate you!"
array[1] // "immutable"

array[2].hammer = "hm, surely I can mutate this nested object..."
array[2].hammer // "Can’t Touch This"

for (var index in array) { console.log(array[index]); }
// "totally"
// "immutable"
// { hammer: 'Can’t Touch This' }

JSON.stringify(array) 
// '["totally","immutable",{"hammer":"Can’t Touch This"}]'


// Uses Object.freeze

Immutable([3, 1, 4]).sort()
// This will throw an ImmutableError, because sort() is a mutating method.

Immutability (libs)

Immutable.js

Provides many Persistent Immutable data structures including: List, Stack, Map, OrderedMap, Set, OrderedSet and Record.

var list = Immutable.List([1, 3, 2, 4, 5]);

popedList = list.pop().pop(); // [1, 3, 2];  
// popedList === list => false

updatedList = list.push(6); // [1, 3, 2, 4, 5, 6] 
// updatedList === list => false

console.log(updatedList.get(0)) // 1
updatedList.set(0, 4) 
console.log(updatedList.get(0)); // 1

const array = updatedList.toJS(); // [1, 3 , 2, 4, 5, 6]

Immutability (libs)

Mori

ClojureScript's persistent data structures and supporting API from the comfort of vanilla JavaScript

var inc = function(n) {
  return n+1;
};

mori.intoArray(mori.map(inc, mori.vector(1,2,3,4,5)));
// => [2,3,4,5,6]

//Efficient non-destructive updates!

var v1 = mori.vector(1,2,3);
var v2 = mori.conj(v1, 4);
v1.toString(); // => '[1 2 3]'
v2.toString(); // => '[1 2 3 4]'
var sum = function(a, b) {
  return a + b;
};
mori.reduce(sum, mori.vector(1, 2, 3, 4)); // => 10

//Lazy sequences!

var _ = mori;
_.intoArray(_.interpose("foo", _.vector(1, 2, 3, 4)));
// => [1, "foo", 2, "foo", 3, "foo", 4]

Recursive Function

function sumIter(sum, ...nums) {
  for(var i = 0; i < nums.length; i++) {
    sum = sum + nums[i] 
  }
  return sum;
}

sumIter(1, 2, 3) // => 6

function sumRecur(sum, ...nums) {
   if (nums.length == 0) return sum;
   return sum + sumRecur(...nums);
}

sumRecur(1, 2, 3) // => 6

Recursive Function(proper tail calls)

'use strict'

function sumRecurPTC(sum, num, ...nums) {
  sum += num
  if (nums.length == 0) return sum;
  return sumRecur(sum, ...nums);
}

sumRecurPTC(1, 2, 3) //=> 6

OOP

FP

In all programs, there are two primary components: the data (the stuff a program knows) and the operators (the stuff a program can do to/with that data)

When FP? And when OOP?

"In a fight between a bear and an alligator, the terrain determines the outcome."

Functional programming

Object-Oriented programming 

  • Objects (understandable)
  • Imperative style
  • Shareable state
  • Reliable (pure) functions (no side effects)
  • Declarative style
    (refactoring)
  • A "newer" paradigm
  • Readability

Material(Books)

Mostly adequate guide to FP

Pragmatic, balanced FP

Q&A