Functional JavaScript

“The problem with object-oriented languages is they’ve got all this implicit environment that they carry around with them. You wanted a banana but what you got was a gorilla holding the banana… and the entire jungle.” quote from Erlang creator, Joe Armstrong

Programming is thinking and Functional Programming will teach you to think very differently. So much so, that you’ll probably never go back to the old way of thinking.

Basic

“Functional programming is the use of functions that transform values into units of abstraction, subsequently used to build software systems.” —— 摘录来自: Michael Fogus. “[Functional.JavaScript(2013.6)]

FP produces abstraction through clever ways of combining functions.

函数式编程意在尽可能使用严格的 PURE（数学式）函数，将视函数为变量，在函数层面上进行抽象，以构建出更复杂的函数来解决具体的问题；整个程序更像是由函数组成的一条条管道，给定数据集输出对应的确定输出集，数据在每个函数之间有序传递。

Immutable and Stateless are core conceptions of FP.

Lambda Calculus

Lambda演算可以被称为最小的通用程序设计语言。它包括一条变换规则（变量替换）和一条函数定义方式，Lambda演算之通用在于，任何一个可计算函数都能用这种形式来表达和求值。因而，它是等价于图灵机的。

Object-Oriented V.S. Functional

Uncertainty always makes problem.

• nones(object) V.S. verbs(functions)
• extends & implements V.S. composite & curry
• object states V.S. data flow and pipeline

Object-Oriented

• Data and the operations upon it are tightly coupled
• Objects hide their implementation of operations from other objects via their interfaces
• The central model for abstraction is the data itself
• The central activity is composing new objects and extending existing objects by adding new methods to them

Functional

• Data is only loosely coupled to functions
• Functions hide their implementation, and the language’s abstractions speak to functions and the way they are combined or expressed
• The central model for abstraction is the function, not the data structure.
• The central activity is writing new functions

顺便提一下：Imperative 也就是过程解释型的编程模式，这是程序最基本的模式，但是写出来的代码不便于复用，因而不适合构筑大型的复杂系统。

So the second piece of code has hidden inputs and outputs. It requires things, and causes things, but you could never guess what just by looking at the API. Without API, it’s hard to know the hiding face of a specific code. These hidden inputs and outputs have an official name: “side-effects“.

Side-effects are the complexity iceberg. You look at the function signature, and the name, and think you’ve got a sense of what you’re looking at. But hidden beneath the surface of the function signature could be absolutely anything. Any hidden requirement, any hidden change. Without looking at the implementation, you’ve no way of knowing what’s really involved. Beneath the surface of the API is a potentially vast block of extra complexity. To grasp it, you’ll only have three options: dive down into the function definition, bring the complexity to the surface, or ignore it and hope for the best. And in the end, ignoring it is usually a titanic mistake.

• A function with side-causes has undocumented assumptions about what external factors it’s depending on.
• A function with side-effects has undocumented assumptions about what external factors it’s going to change.

SQL is very similar to functional languages, and it permeates business. It uses a consistent data structure (tables with records organized into columns) and a few basic functions that can be combined into arbitrary queries. And it shares one other important feature with functional languages: it is declarative.

SELECT orders.order_id, orders.order_date, suppliers.supplier_name
    FROM suppliers
    RIGHT OUTER JOIN orders
    ON suppliers.supplier_id = orders.supplier_id
    WHERE orders.order_status = 'INCOMPLETE'
    ORDER BY orders.order_date DESC;

Core ideas

函数式编程，就是对函数级别的抽象。

• Identifying an abstraction and building a function for it.
• Using existing functions to build more complex abstractions.
• Passing existing functions to other functions to build even more complex abstractions.

Features

• Imperative V.S. Declarative:

// imperative
var sumOfSquares = function(list) {
    var result = 0;
    for (var i = 0; i < list.length; i++) {
        result += square(list[i]);
    }
    return result;
};

console.log(sumOfSquares([2, 3, 5]));

// declartive
var sumOfSquares = pipe(map(square), reduce(add, 0));
console.log(sumOfSquares([2, 3, 5]));

• Do it in Mathematical Way：摒弃面向对象编程来解决问题的思维，利用数学的函数式编程思维替代之。
• FIRST-CLASS Functions：函数将会成为主要客体，成为 第一公民。以 函数 为复杂过程的抽象基础。
• Expressions First, no Statements. “表达式”（expression）是一个单纯的运算过程，总是有返回值；”语句”（statement）是执行某种操作，没有返回值。函数式编程要求，只使用表达式，不使用语句。也就是说，每一步都是单纯的运算，而且都有返回值。
• Immutable and Stateless：函数式编程只是返回新的值，不修改系统变量，无状态量的存在。
• PURE Functions 是指严格的数学函数定义：f(x) = y 对于给定的 x 总会有肯定的 y 输出，那么这个函数就是 PURE 的。这意味着在对函式编程进行测试的时候，会轻松很多，更容易找到问题所在。
  • 同时，PURE Function 具备如下特性：Cacheable, Self-Documentation, Testable, Reasonable, Parallel
  • Pure functions are easy to refactor.
  • No Side Effects：函数式编程强调没有”副作用”，意味着函数要保持独立，所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。
  • Reference Transparency：函数内只会依赖传入参数，在任何时候对函数输入相同的参数时，总能输出相同的结果。
• POINT-FREE 是指函数都是 PIPE，是一个管道流，作为函数的参数并不需要显示声明。这意味着：每一个函数都是可以复用的函数，并遵从函式编程的范式，不依赖于传递变量的参数名。自然具有更好的可扩展性、可维护性。
  • There is a style of writing functions without having to specify the parameters called Point-Free Notation.
• FUNCTOR 是一个类型和数据的容器，能够适应于处理多种如：异步任务、I/O、类型检测、空值等情况。
  • 技术：Monads 是一种能够被 Flatten 的 Functor。
  • 在 Functor 的基础上定义了：of, map, chain, ap 等一系列操作
  • Functor 也是保证 Purity 的关键容器模型

Advantages

Paul Graham在《黑客与画家》一书中写道：同样功能的程序，极端情况下，Lisp代码的长度可能是C代码的二十分之一。

The special characteristics and advantages of functional programming are often summed up more or less as follows. Functional programs contain no assignment statements, so variables, once given a value, never change. More generally, functional programs contain no side-effects at all. A function call can have no effect other than to compute its result. This eliminates a major source of bugs, and also makes the order of execution irrelevant — since no side- effect can change an expression’s value, it can be evaluated at any time. This relieves the programmer of the burden of prescribing the flow of control. Since expressions can be evaluated at any time, one can freely replace variables by their values and vice versa — that is, programs are “referentially transparent”. This freedom helps make functional programs more tractable mathematically than their conventional counterparts.

• Clarity and Fast Developing Speed: 函数式编程大量使用函数，减少了代码的重复，因此程序比较短，开发速度较快。
  • 重视基于行为结构的抽象。
• 优雅的函数命名接近于自然语言的表达，易于理解。

　const res = merge([1,2],[3,4]).sort().search("2")

• 易于并发和并行编程，提高多核 CPU 的利用率。主要因为：stateless 的特性。
• 支持数学的严格证明、推理和变化进行结构优化。
• 支持代码的「热升级」。函数式编程没有副作用，只要保证接口不变，内部实现是外部无关的。所以，可以在运行状态下直接升级代码，不需要重启，也不需要停机。Erlang)语言早就证明了这一点，它是瑞典爱立信公司为了管理电话系统而开发的，电话系统的升级当然是不能停机的。
• 容易编写测试用例，也容易诊断错误根源。

Another benefit of using pure functions and function composition is its much easier to trace errors. Whenever you get an error, you should be able to see a stack trace through every function down to the source of the bug. In object oriented programming, its often quite confusing because you don’t always know the state of the rest of the object which led to the bug.

First Class Functions

• Q：What is the First Class Functions, why we choose those first class functions?
• 所谓“第一等公民”（first class），指的是函数与其他数据类型一样，处于平等地位，可以赋值给其他变量，也可以作为参数，传入另一个函数，或者作为别的函数的返回值。
• A: FirstClass Function 是认为函数也是变量，也可以被操作、传递和修改。
  • 追求一种去冗余的形式，让函数尽量不要叠合不必要的函数，内嵌的函数参数如果写死的话（数据显示声明）也不利于一个程序的扩展性和维护性。而在设置函数的时候，我们也应该考虑到部分函数的可复用性，而不是将内函数体写死。Imperative 范式的写法降低了函数的复用性，在函式编程中是不推荐的。
  • func.bind(Obj) 是一种明智的绑定函数执行上下文的形式便于支持函数在不同的上下文中执行。

// For example
// Bad Case
weicheCode.hover(
    function(e) { bigCode.show(e); },
    function(e) { bigCode.hide(e); }
);
// Good Case
weicheCode.hover(
    bigCode.show.bind(weicheCode), 
    bigCode.hide.bind(weicheCode)
);
// Make full use of first-class function
httpGet('/post/2', function(json, err){
  return renderPost(json, err);
});
httpGet('/post/2', renderPost);
// declarative way to avoid imperative programming like for(;;)
var makes = cars.map(function(car){ return car.make; });

Applicative Programming

Applicative programming is defined as the calling by function B of a function A, supplied as an argument to function B originally.

It is better to have 100 functions operate on one data structure than 10 functions on 10 data structures.

High-Order Function

Higher-order Functions either take functions as parameters, return functions or both.

function makeRegexParser(regex) {
    return regex.exec;
}
var parseSsn = makeRegexParser(/^\d{3}-\d{2}-\d{4}$/);
var parsePhone = makeRegexParser(/^\(\d{3}\)\d{3}-\d{4}$/);
validateValueWithFunc('123-45-6789', parseSsn, 'SSN');
validateValueWithFunc('(123)456-7890', parsePhone, 'Phone');
validateValueWithFunc('123 Main St.', parseAddress, 'Address');
validateValueWithFunc('Joe Mama', parseName, 'Name');

Recursive

Functional programming prefer recursion, but one very simple one is that recursive functions are often much more elegant than their iterative cousins. It’s easier to reason about them.

Tail-call formulations

var odds = (function(){
    var odds1 = function(n, p, acc) {
        return (n == 0) ? acc : odds1(n - 1, p - 1, (n / p) * acc);
    }
    return function(n, p) {
        return odds1(n, p, 1)
    }
})();

Note that the recursive call in odds1 is the last statement in its branch of the function. If this is true for all recursive calls, then the function is tail-recursive, and the compiler can replace the entire set of nested calls with simple JUMP operations.

Pure Functions

Strive for purity.

• Q: What is the Pure Function, Why Pure Functions?
• A: A pure function is a function that, given the same input, will always return the same output and does not have any observable side effect. Any interaction with the world outside of a function is a side effect. The philosophy of functional programming postulates that side effects are a primary cause of incorrect behavior.

严格的 Pure Function 定义如下：

• Its result is calculated only from the values of its arguments.
• It cannot rely on data that changes external to its control.
• It cannot change the state of something external to its body.

如同数学函数的观念一样，函数就是两个集合之间的映射关系，而 f 正是描述这种关系的运算方法。所以，对直接小数量的映射关系，我们可以直接使用 Hash 列表作为函数的替代，使用 [] 而非 () 获取值。

介绍 Pure Functions 的一些特性：

• Cacheable: memorization to cache function results no matter what kind of type it is even another function.
• Portable / Self-Documenting: pure function must be honest about its dependencies, pure functions can be run anywhere our hearts desire.
• Testable: We simply give the function input and assert output.
• Reasonable: referential transparency, A spot of code is referentially transparent when it can be substituted for its evaluated value without changing the behavior of the program.
• Parallel: we can run any pure function in parallel.

Purity Principles

• 以 xs.slice(); xs.splice() 为例，可以看到其不同之处。我们不能够修改引用类型中的值，同时不能够对外界的变量做出改变。
  • Math.random(), Date.now() 以及对 window 对象操作等行为都是 Impure 的操作。在实践中应该将它们独立为 Impure Function，并用容器 Pure 化操作。
  • changing the file system
  • inserting a record into a database
  • making an http call
  • mutations
  • printing to the screen / logging
  • obtaining user input
  • querying the DOM
  • accessing system state
  • …
• 严格分离：Pure 以及 Impure 的函数，组合 Pure 函数得到的依旧是 Pure 的函数，但是一旦组合 Impure 的函数，就不尽宜然了。
• “f a pure function mutates some local data in order to produce an immutable return value, is that ok?”, that’s OK ~
• Object.freeze() 提供一种针对对象 Immutability 操作。
• Functor 能够提供 Pipeline 中的 Purity 保证。

Transform impure functions to pure ones

• Delay the evolution of impure functions.

// you can transform some impure functions into pure ones by delaying evaluation
var pureHttpCall = memoize(function(url, params){
  return function() { return $.getJSON(url, params); }
});

Currying and Composing

Composition is fractal!

首先理解高阶函数 (High-Order Function) 的概念：A first-class function take functions as arguments or then return a new function.

记住：Functions, not Values!!!

Currying

“ A curried function is one that returns a new function for every logical argument it takes.”

Currying is the process of converting functions that take multiple arguments into ones that, when supplied fewer arguments, return new functions that accept the remaining ones.

You can call a function with fewer arguments than it expects. What is returned is a function that takes the remaining arguments once all arguments are ready, it fired. The functions created between the first and the final one are so called partial function.

Composing

Composing is Pointfree which means functions that never mention the data upon which they operate. Pointfree is a good litmus test for functional code as it let’s us know we’ve got small functions that take input to output.

// It's like the chaining call
var compose = function (f, g) {
    return function (x) {
        return f(g(x));
    }
}
// associativity
var associative = compose(f, compose(g, h)) == compose(compose(f, g), h);
var last = compose(head, reverse);
var angry = compose(exclaim, toUpperCase);
var loudLastUpper = compose(angry, last);

Category Theory

In category theory, we have something called… a category. It is defined as a collection with the following components:

• A collection of objects
• A collection of morphisms
• A notion of composition on the morphisms
• A distinguished morphism called identity

Category theory is abstract enough to model many things, but let’s apply this to types and functions, which is what we care about at the moment.

A collection of objects The objects will be data types. For instance, String, Boolean, Number, Object, etc. We often view data types as sets of all the possible values. One could look at Boolean as the set of [true, false] and Number as the set of all possible numeric values. Treating types as sets is useful because we can use set theory to work with them.

A collection of morphisms The morphisms will be our standard every day pure functions.

A notion of composition on the morphisms This, as you may have guessed, is our brand new toy - compose. We’ve discussed that our compose function is associative which is no coincidence as it is a property that must hold for any composition in category theory.

Type Signature

//  match :: Regex -> (String -> [String])
var match = curry(function(reg, s){
  return s.match(reg);
});

//  replace :: Regex -> (String -> (String -> String))
var replace = curry(function(reg, sub, s){
  return s.replace(reg, sub);
});

Lazy Evaluation

But there are many reasons to like lazy evaluation. It allows you to operate on theoretically infinite data structures, calculating only those parts you need. And it allows you to define your own efficient control structures inside the language instead of only at the level of the language syntax.

Tupperware as Functor

A Functor is a type that implements map and obeys some laws. Container also offers a immutable environment for data-set.

Write programs which pipe data through a series of pure functions. They are declarative specifications of behavior. But what about control flow, error handling, asynchronous actions, state and, dare I say, effects?!

• Container: This container must hold any type of value. Our value in the Container is handed to the map function so we can fuss with it and afterward, returned to its Container for safe keeping.
• Maybe: This container will return null and stop the chaining calls while pass the null or undefined. Notice our app doesn’t explode with errors as we map functions over our null values. This is because Maybe will take care to check for a value each and every time it applies a function.
• Either: For Error Handling by defining two subclasses: Right and Left.
• IO: Handle the impure behaviors with function value inside a container, for synchronous behaviors.
• Task: for the Asynchronous Series, offering fork method to handle success or fail conditions.

Demo：Maybe and Task

var Maybe = function(x) { this.__value = x; }
Maybe.of = function(x) { return new Maybe(x); }
Maybe.prototype.isNothing = function() {
  return (this.__value === null || this.__value === undefined);
}
Maybe.prototype.map = function(f) {
  return this.isNothing() ? Maybe.of(null) : Maybe.of(f(this.__value));
}

// Pure application
//=====================
// blogTemplate :: String

//  blogPage :: Posts -> HTML
var blogPage = Handlebars.compile(blogTemplate);

//  renderPage :: Posts -> HTML
var renderPage = compose(blogPage, sortBy('date'));

//  blog :: Params -> Task Error HTML
var blog = compose(map(renderPage), getJSON('/posts'));


// Impure calling code
//=====================
blog({}).fork(
  function(error){ $("#error").html(error.message); },
  function(page){ $("#main").html(page); }
);

$('#spinner').show();

Monadic Onions

Handling the nested calls. Monads are pointed functors that can flatten.

Monads can be thought of as a container for a value, and to open up the container and do something to the value, you need to map over it.

The important thing about monads and functors is that mathematicians have been researching these ideas in category theory. This provides us not only a framework for understanding programs, but algebraic theorems and proofs we can use to statically analyze and optimize our code when it’s compiled. This is one of the main benefits of Haskell — the Glasgow Haskell Compiler is a feat of human ingenuity.

• Functor.join() or helper function join() to work with pipe-line. In this way, we have not thrown out purity, but merely removed one layer of excess shrink wrap.
• chain combine the join and map together.

Maybe.prototype.join = function() {
  return this.isNothing() ? Maybe.of(null) : this.__value;
}

IO.prototype.join = function() {
  return this.unsafePerformIO();
}

//  chain :: Monad m => (a -> m b) -> m a -> m b
var chain = curry(function(f, m){
  return m.map(f).join(); // or compose(join, map(f))(m)
});

// functional way V.S. normal way
//  upload :: String -> Either String (Future Error JSON)
var upload = compose(map(chain(httpPost('/uploads'))), readFile);

//  upload :: String -> (String -> a) -> Void
var upload = function(filename, callback) {
  if(!filename) {
    throw "You need a filename!";
  } else {
    readFile(filename, function(err, contents) {
      if(err) throw err;
      httpPost(contents, function(err, json) {
        if(err) throw err;
        callback(json);
      });
    });
  }
}

Applicative Functors

Applies the function inside the structure to another Applicative type.

A good use case for applicatives is when one has multiple functor arguments. They give us the ability to apply functions to arguments all within the functor world. Though we could already do so with monads, we should prefer applicative functors when we aren’t in need of monadic specific functionality.

F.of(x).map(f) == F.of(f).ap(F.of(x))

Container.prototype.ap = function(other_container) {
  return other_container.map(this.__value);
}

Container.of(add(2)).ap(Container.of(3));
// Container(5)

// map derived from chain
X.prototype.map = function(f) {
  var m = this;
  return m.chain(function(a) {
    return m.constructor.of(f(a));
  });
}

// ap derived from chain/map
X.prototype.ap = function(other) {
  return this.chain(function(f) {
    return other.map(f);
  });
};

More specific demo

// Http.get :: String -> Task Error HTML

var renderPage = curry(function(destinations, events) { /* render page */  });
Task.of(renderPage).ap(Http.get('/destinations')).ap(Http.get('/events'));
// Task("<div>some page with dest and events</div>")

// Point-free way

var liftA2 = curry(function(f, functor1, functor2) {
  return functor1.map(f).ap(functor2);
});

var liftA3 = curry(function(f, functor1, functor2, functor3) {
  return functor1.map(f).ap(functor2).ap(functor3);
});

//  createUser :: Email -> String -> IO User
var createUser = curry(function(email, name) { /* creating... */ });

Either.of(createUser).ap(checkEmail(user)).ap(checkName(user));
// Left("invalid email")

liftA2(createUser, checkEmail(user), checkName(user));
// Left("invalid email")

Functional JavaScript Lib - Ramda

The Documentation could be here: Ramda

Features:

• Ramda emphasizes a purer functional style. Immutability and side-effect free functions are at the heart of its design philosophy. This can help you get the job done with simple, elegant code.
• Ramda functions are automatically curried. This allows you to easily build up new functions from old ones simply by not supplying the final parameters.
• The parameters to Ramda functions are arranged to make it convenient for currying. The data to be operated on is generally supplied last.

Functional programming is in good part about immutable objects and side-effect free functions. While Ramda does not enforce this, it enables such style to be as frictionless as possible.

Functional JavaScript Framework Folktale

• Core: Provides the most basic and essential building blocks and compositional operations, which are likely to be used by most programs.
  • Core.arity : To fix the curry function error.
    • nullary(f) | unary(f) | binary(f) | ternary(f)
  • Core.check : Use for JavaScript type check.
    • Primitive Validations
    • Higher-order Validations
  • Core.inspect : Give an inspect to an object with Container def.
  • Core.lambda: Core combinators and high-order functions.
    • core.lambda.identity(a) a -> a
    • core.lambda.constant(a, b) a -> b -> a
    • core.lambda.apply(f, a) (a -> b) -> a -> b
    • core.lambda.flip(f) (a -> b -> c) -> (b -> a -> c)
    • core.lambda.compose(f, g) (b -> c) -> (a -> b) -> (a -> c)
    • core.lambda.curry(n, f) tranform function into a curried function.
    • core.lambda.uncurry(f) Transforms a curried function into a function on tuples.
    • core.lambda.spread(f, xs) Applies a list of arguments to a curried function.
    • core.lambda.upon(f, g) A binary function f with arguments transformed by g.
  • Core.operators: This module provides first-class, curried versions of these special operators that you can combine with the usual function composition operations.
• Data
  • Data.either: Right-biased disjunctions. Commonly used for modelling computations that may fail with additional information about the failure.
  • Data.maybe: Safe optional values. Commonly used for modelling computations that may fail, or values that might not be available.
  • Data.task: A structure for capturing the effects of time-dependent values (asynchronous computations, latency, etc.) with automatic resource management.
  • Data.validation: A disjunction for validating inputs and aggregating failures. Isomorphic to Data.Either.
• Control: Provides operations for control-flow.
  • Control.monads: Common monadic combinators and sequencing operations.
  • Control.async: Common operations for asynchronous control-flow with Data.Task.

Some Classic APIs

• curry()
• compose()

Optimization

尾递归优化：我们知道递归的害处，那就是如果递归很深的话，stack受不了，并会导致性能大幅度下降。所以，我们使用尾递归优化技术——每次递归时都会重用stack

Reference

• Functional Light JS
• O’Reilly 《Functional JavaScript》by Michael Fogus
• Functional V.S. OOP
• What is Functional Programming
• Functional Programming in JavaScript
• So You Want to be a Functional Programmer Series
• Functional JavaScript by DrBoolean
• Functional JavaScript Library
  • Ramda / Folktale / Underscore
• The Two Pillars of JavaScript on Medium
• Functional Programming for JavaScript People
• Presentation: About compose / chaining
• 函数式编程初探
• Video about the comoposable FP in JS