JS ФП тезисы

Источники

• Functional JavaScript (блог)
• Что такое монады? (форум)

Парадигмы (стили) программирования

Языки программирования состоят из операторов, условных операторов, операторов цикла и функций. Наличие условных операторов и операторов циклов являются отличительными чертами "императивных языков программирования". Функциональные языки, как правило, поддерживают только операторы и функции.

Интересно, что ни один из трех языков, Java, C ++ и C, не являются функциональными языками программирования.Язык C - императивный язык программирования, C ++ и Java, императивный / объектно- ориентированные языки программирования. Т.е. существуют три парадигмы (стиля) программирования: императив, объектно-ориентированный и функциональный. Существует еще один, декларативный стиль.

Различия между этими парадигмами заложены в основе. Императив и объектно-ориентированное программирование основано на «машине Тьюринга». Функциональное программирование на базе "лямбда-исчисления", а декларативное программирование основано на «логике первого порядка". Будут рассмотрены различия между, императивным, объектно-ориентированным и функциональном программировании на практическом уровне.

В императивном языке программирования изменение состояния программы достигается путем выполнения серии операторов, и выполняет контроль потока, прежде всего, с помощью условных операторов, операторов цикла и вызовов функций. Программа, приведенная ниже простая реализация метода JavaScript Array.join в императивном стиле.

function simpleJoin(stringArray) {
    var accumulator = '';
    for (var i=0, l=stringArray.length; i < l; i++) {
        accumulator = accumulator + stringArray[i];
    }
    return accumulator;
}

Код выше - последовательный. Мы перебераем массив и добавить каждый элемент в строку-аккумулятор и возвращаем аккумулятор. Сейчас мы перепишем эту функцию в объектно-ориентированном способом. Так как JavaScript имеет класс Array, мы добавим этот метод для класса Array, так что каждый экземпляр этого класса получит доступ к этой функции. JavaScript использует наследование через прототипы и поэтому мы добавляем эту функцию, в прототип массива.

Array.prototype.simpleJoin = function() {
    var accumulator = "";
    for (var i=0, l=this.length; i < l; i++) {
        accumulator = accumulator + this[i];
    }
    return accumulator;
}

Объектно-ориентированный вариант похож на императивную версию, кроме того, что функция (метод) теперь метод класса. Объектно-ориентированные языки, как правило, императивные также.

Теперь запишем функциональную версию этой функции.

function simpleJoin(stringArray, i, accumulator) {
    if (i === stringArray.length) {
     return accumulator;
    } else {
     return simpleJoin(stringArray, i+1, accumulator+stringArray[i])
    }
}

Первое, что нужно отметить, это то, что мы не используем здесь цикл для итерации. Вместо этого для итерации используется рекурсия. Действительно, это одна из характеристик функционального языка программирования.

Функция называется впервые для данного массива в StringArray, i установлено в 0, и аккумулятор установлен в "". Второй раз функции вызывается из себя с той же StringArray, я установлен на i + 1, и аккумулятор установлен в аккумуляторе + StringArray [i]. И мы продолжаем так же, пока i === stringArray.length, когда мы возвращаемся аккумулятор. Мы будем обсуждать рекурсию подробно позже в более поздней почте. Просто помните, мы использовали рекурсию для этого итерации здесь.

Но осталось кое-что еще от императивного стиля - условный оператор. Functional languages tend to use expressions that evaluate to some value, instead of statements that don't evaluate to anything. Итак, давайте перепишем функцию, чтобы сделать его как функциональные, как можно в JavaScript.

function simpleJoin(stringArray, i, accumulator) {
    return (i === stringArray.length) ? accumulator :
        simpleJoin(stringArray, i + 1, accumulator + stringArray[i])
}

Теперь это функциональный стиль, как его можно написать с помощью JavaScript. Вместо того, чтобы, возвращать значение на основе вычислений условного оператора, мы возвращаем значение вычисляемое условным оператором. Значение первого выражения возвращается, если верно и второе, если ложно.

Мы видим, что функциональная версия короче. Действительно, одним из преимуществ функционального программирования является то, что необходимо меньшей кода для того что бы сделать то же самое, что приводит к лучшей читаемости и ремонтопригодности.

Однако в случае JavaScript, как сейчас вы не можете использовать рекурсию для этого итерации. Вы должны продолжать использовать императивный или объектно-ориентированного метода для итерации. Это потому, что JavaScript (пока) не поддерживает "оптимизацию хвостового вызова". Мы будем обсуждать хвостовую рекурсию, и хвостовую оптимизацию, и как обойти эту проблему позже. JavaScript - мультипарадигмальный язык программирования:императивный, объектно-ориентированный и функциональный язык.

Хорошим примером мультипарадигмальной природы JavaScript является метод Array.forEach. Обратите внимание, что все современные браузеры уже реализовали это. Вот простая реализация.

Array.prototype.forEach = function(callback) {
    for (var i = 0, len = this.length; i < len; ++i) {
        callback(this[i], i, this);
    }
}

В этом коде цикл for императивный код. Добавление в прототип объектно-ориентированное. Передача функции в качестве аргумента другой функции (callback) - функциональный код и эта возможность функционального программирования известна как “higher order function” (функции высшего порядка). В JavaScript, мы принимаем это как должное - передача функции в качестве аргумента. Удивительно этой возможности не было в самых популярных языках, до недавнего времени. например, вы не можете передавать функции в качестве аргументов в Java, хотя вы можете сделать это косвенно, через интерфейсы. То же самое в случае с C, хотя вы можете сделать это косвенно, используя указатели.

Абстракции

What if JavaScript did not have the “passing functions as arguments feature”? The answer to this question is crucial to understanding what functional programming brings to the table. For one, we would not be able to write the Array.forEach function above. And even worse, every time we had to iterate over an array, we would have to write the same for-loop again and again. If we had Array.foreach we need to think only about writing the callback. We need to think only of what to do with each element of the array, and need not concern ourselves with iterating over the array. In other words we have “abstracted” away the iteration part of the problem, and freed ourselves to concentrate on each element of the array.

Abstractions are about hiding away implementation details, thereby reducing and factoring out details, so that programmers can focus on the problem at a higher level. Abstractions can be code abstractions, as we saw in the example above, and data abstractions. Objected oriented programming is about combining code and data abstractions into one abstraction called the class. In functional programming we use functional features like first class functions, nested functions, anonymous functions and closures to abstract away code and sometimes even data. Monads are an esoteric feature of functional programming that can even abstract away program structure!

Macro's are another feature that allows code abstraction. However macros are not a feature of functional programming. But they are found in all Lisp like functional languages like Lisp, Scheme, Clojure etc. There are attempts to bring Macro's to JavaScript and at the moment it is very much early days.

A good example of the power of functional abstractions is jQuery. jQuery is the mother of all functional abstractions. It has abstracted away the JavaScript language itself! So much so that you wouldn't be surprised, if you found a jQuery programmer who knows very little or no JavaScript. As of Feb 2013 there was one publisher who had 32 jQuery books listed, and not a single JavaScript book! And jQuery has achieved so much mostly using only two functional features, functions as arguments and closures.

Функции первого класса и замыкания

Возможность функционального программирования, реализованые Бренданом Эйчом в JavaScript были first class functions или first class citizens. Это означает что функции рассматриваются как и все другие переменные. Т.е. можно передать их в качестве аргументов функций, вы можете вернуть их в качестве значений от других функций, или вы можете назначить им переменные или структуры данных. Мы видели ранее передачу функции в качестве аргумента. Вот пример присвоения функцию переменной.

function greet(name) {
    console.log("Hello " + name);
}

greet("John"); // "Hello John"

var sayHello = greet;
sayHello("Alex"); // "Hello Alex"

Некоторые теоретики языка программирования рассматривают "анонимные функции" как функции первого класса. Чтобы не отстать, Брендан Эйч выбросил анонимные функции в миксе. Вот анонимная функция в JavaScript.

function(name) {
    console.log(“Hello “ + name);
}

Если Вы заметили, мы не давали этой функции имя. Ведь это анонимная функция. Если вы попытаетесь запустить код, указанный выше, вы получите сообщение об ошибке. Что-то на подобие "вы не можете запустить код в этом контексте". И это правильно. Они могут быть назначены только на что-то, или передаться в качестве аргументов функции.

var sayHello = function(name) {
    console.log(“Hello “ + name);
}
sayHello("Jane"); // "Hello Jane"

Что делать, если мы хотим изменить приветствие? Иногда мы хотели бы сказать, "Hi", а не "Hello". Мы могли бы создать обобщенную функцию "createGreeting", которая, в свою очередь "сочинит" еще одну функцию для вас, и вернет новую комбинированную функцию. Так что, если мы бы хотели сказать "Hi" мы вернули функцию, а если мы хотели сказать "Hello" мы бы вернули другую функцию, которая говорит "Hello". Мы можем делать все это потому что JavaScript поддерживает функции первого класса, и мы можем вернуть функцию из другой функций. Вот код.

function createGreeting(greeting) {
    return function(name) {
        console.log(greeting + " " + name);
    }
}
var sayHi = createGreeting("Hi");
sayHi("Jack"); // "Hi Jack"
var sayHello = createGreeting("Hello");
sayHello("Jack"); // "Hello Jack"

Функция createGreeting принимает greeting в качестве аргумента. Функция возвращает новую анонимную функцию. Однако созданная анонимная функция была создана внутри другой функции createGreeting. Таким образом она является вложенной функцией. Теперь, поскольку наш язык поддерживает анонимные функции, он также будет поддерживать вложенные функции. И когда мы возвращаемся вложенные функции из нашей функции мы столкнуться с другой проблемой.

Анонимная функция принимает аргумент name и печатает в консоли greeting+name.Переменная name является аргументом анонимной функции, и ведет себя так же, как и любой другой переменной, определенной в функции. Другими словами name "локальна" для анонимной функции. Но это не относится к переменной greeting. Она определен в другой функции - createGreeting и, следовательно, "не локальна" для анонимной функции. Однако анонимные функции могут получить доступ к переменной greeting и это называется Лексическая область видимости.

“Scope” (контекст, граница) переменной является её "видимостью" в пределах программы. "Лексическая область" означает, что видимость распространяется для всего текста (кода). Поэтому можно сказать “локальная переменная лексически ограничена” внутри функции, это значит, что локальные переменные функции видны для всего текста внутри функции, даже для кода внутри другой вложенной функции. Это также означает, что когда вы запускаете вложенную функцию вне окружения лексического контекста, the nested functions non local variable will not be visible. И в этом проблема возвращения вложенных функций из другой функции. И в самом деле вот что мы здесь делаем.

var sayHi = createGreeting("Hi");

В строке выше мы присваиваем возвращенную анонимную функцию переменной SayHi. И вызываем функцию в следующей строке.

sayHi(“Jack”)

Функция sayHi вызывается вне createGreeting. И переменная greeting недоступна вне createGreeting. Переменные доступные в контексте в котором они были определены, могут быть недоступны в контексте в котором они действительно вызываются. Вот почему языки, такие как C не поддерживает вложенные функции. Для того, чтобы так работать, язык должен поддерживать другой возможность функционального программирования - функцию под названием замыкание. JavaScript поддерживает замыкания. Любой язык, который поддерживает функции первого класса и вложенные функции должен поддерживать замыкания.

Функция замыкание является ссылкой на все свои не локальные переменные. В предыдущем примере greeting была не локальная переменная, а name локальная переменная. Замыкание-это таблица ссылок на все используемые в функции не локальные переменные. Это позволяет функция по-прежнему обращаться к нелокальным переменным, даже если функция выходит из контекста переменных. A function's closure is a reference to all its non local variables. In the previous example greeting was the non local variable and name was the local variable. A closure is a table of references to all of a functions non local variables. This allows the function to continue to refer to the non local variable even when the function is out of the scope of the variables.

Функторы

Рассмотрим функцию.

function plus1(value) {  
    return value + 1  
}  

Это просто функция, которая принимает целое число и добавляет единицу к нему. Аналогично создадим другую функция Plus2. Мы будем использовать эти функции позже.

function plus2(value) {  
    return value + 2  
}  

И мы могли бы написать обобщенную функцию, чтобы использовать любую из этих функций, как и когда это требуется.

function F(value, fn) {  
    return fn(value)  
}

F(1, plus1) ==>> 2

Эта функция будет работать хорошо, пока значение передается целое. Попробуем массив.

F([1, 2, 3], plus1)   ==>> '1,2,31'

Ой. Мы взяли массив целых чисел, добавили целое и получили строку! Не только он это сделал неправильную вещь, мы получили строку передав массив. Другими словами наша программа "испачкала" структуру ввода. Мы хотим чтобы F работала "правильно". Правильно, это "сохранить структуру" на выходе.

Что значит "сохранить структуру"? Наша функция должна "развернуть" исходный массива и получить свои элементы. Затем вызвать переданную функцию для каждого элемента. Затем обернуть возвращаемые значения в новый массив и вернуть его. К счастью JavaScript имеет встроенную такую функцию - map.

So what do we mean by "maintain structure"? Our function must "unwrap" the given array and get its elements. Then call the given function with every element. Then wrap the returned values in a new Array and return it. Fortunately JavaScript just has that function. Its called map.

[1, 2, 3].map(plus1) ==>> [2, 3, 4] And map is a functor!

A functor is a function, given a value and a function, does the right thing.

To be more specific. A functor is a function, given a value and a function, unwraps the values to get to its inner value(s), calls the given function with the inner value(s), wraps the returned values in a new structure, and returns the new structure.

Thing to note here is that depending on the "Type" of the value, the unwrapping may lead to a value or a set of values.

Also the returned structure need not be of the same type as the original value. In the case of map both the value and the returned value have the same structure (Array). The returned structure can be any type as long as you can get to the individual elements. So if you had a function that takes and Array and returns value of type Object with all the array indexes as keys, and corresponding values, that will also be a functor.

In the case of JavaScript, filter is a functor because it returns an Array, however forEach is not a functor because it returns undefined. ie. forEach does not maintain structure.

Functors come from category theory in mathematics, where functors are defined as "homomorphisms between categories". Let's draw some meaning out of those words.

homo = same morphisms = functions that maintain structure category = type According to the theory, function F is a functor when for two composable ordinary functions f and g

F(f . g) = F(f) . F(g) where . indicates composition. ie. functors must preserve composition.

So given this equation we can prove wether a given function is indeed a functor or not.

Array Functor We saw that map is a functor that acts on type Array. Let us prove that the JavaScript Array.map function is a functor.

function compose(f, g) {

   return function(x) {return f(g(x))}

} Composing functions is about calling a set of functions, by calling the next function, with results of the previous function. Note that our compose function above works from right to left. g is called first then f.

[1, 2, 3].map(compose(plus1, plus2)) ==>> [ 4, 5, 6 ]

[1, 2, 3].map(plus2).map(plus1) ==>> [ 4, 5, 6 ] Yes! map is indeed a functor.

Lets try some functors. You can write functors for values of any type, as long as you can unwrap the value and return a structure.

String Functor So can we write a functor for type string? Can you unwrap a string? Actually you can, if you think of a string as an array of chars. So it is really about how you look at the value. We also know that chars have char codes which are integers. So we run plus1 on every char charcode, wrap them back to a string and return it.

function stringFunctor(value, fn) {

   var chars = value.split("")  
   return chars.map(function(char) {  
       return String.fromCharCode(fn(char.charCodeAt(0)))  
   }).join("")  

}

stringFunctor("ABCD", plus1) ==>> "BCDE" You can begin to see how awesome functors are. You can actually write a parser using the string functor as the basis.

Function Functor In JavaScript functions are first class citizens. That means you can treat functions like any other value. So can we write a functor for value of type function? We should be able to! But how do we unwrap a function? You can unwrap a function by calling it and getting its return value. But we straight away run into a problem. To call the function we need its arguments. Remember that the functor only has the function that came in as the value. We can solve this by having the functor return a new function. This function is called with the arguments, and we will in turn call the value function with the argument, and call the original functors function with the value returned!

function functionFunctor(value, fn) {

   return function(initial) {  
       return function() {  
           return fn(value(initial))  
       }  
   }  

}

var init = functionFunctor(function(x) {return x * x}, plus1) var final = init(2) final() ==> 5 Our function functor really does nothing much, to say the least. But there a couple things of note here. Nothing happens until you call final. Every thing is in a state of suspended animation until you call final. The function functor forms the basis for more awesome functional stuff like maintaining state, continuation calling and even promises. You can write your own function functors to do these things!

MayBe Functor function mayBe(value, fn) {

   return value === null || value === undefined ? value : fn(value)

} Yes, this is a valid functor.

mayBe(undefined, compose(plus1, plus2)) ==>> undefined mayBe(mayBe(undefined, plus2), plus1) ==>> undefined mayBe(1, compose(plus1, plus2)) ==>> 4 mayBe(mayBe(1, plus2), plus1) ==>> 4 So mayBe passes our functor test. There is no need for unrapping or wrapping here. It just returns nothing for nothing. Maybe is useful as a short circuiting function, which you can use as a substitute for code like

if (result === null) {

   return null

} else {

   doSomething(result)

} Identity Function function id(x) {

   return x

} The function above is known as the identity function. It is just a function that returns the value passed to it. It is called so, because it is the identity in composition of functions in mathematics.

We learned earlier that functors must preserve composition. However something I did not mention then, is that functors must also preserve identity. ie.

F(value, id) = value Lets try this for map.

[1, 2, 3].map(id) ==>> [ 1, 2, 3 ] Type Signature The type signature of a function is the type of its argument and return value. So the type signature of our plus1 function is

f: int -> int The type signature of the functor map depends on the type signature of the function argument. So if map is called with plus1 then its type signature is

map: [int] -> [int] However the type signature of the given function need not be the same as above. We could have a function like

f: int -> string in which the type signature of map would be

map: [int] -> [string] The only restriction being that the type change does not affect the composability of the functor. So in general a functor's type signature can

F: A -> B In other words map can take an array of integers and return an array of strings and would still be a functor.

Monads are a special case of Functors whos type signature is

M: A -> A More about monads in the next chapter.

М

С точки зрения программиста монада - это абстрактный контейнер с тремя функциями.

• map — заменяет содержимое контейнера без изменения самого контейнера. Заменяем каждый гвоздь в коробке шурупом, каждый int в массиве float-ом — так map и работает.
• unit — берет элемент и возвращает контейнер с одним этим элементом. Делаем из гвоздя коробку с одним гвоздем. Делаем из int массив из одного int.
• join — уменьшает вложенность контейнеров — из коробки коробок гвоздей делает коробку с гвоздями (из массива массивов int-ов — массив int-ов). Ну или из коробки коробок коробок гвоздей делаем коробку коробок гвоздей. Это уже сложная концепция, доступная только программистам и более абстрактно развитым товарищам; обычный человек будет обескуражен тем, как в одну коробку могли поместиться несколько точно таких-же коробок. Впрочем, простая замена коробок коробок на мешки мешков или пакеты пакетов позволяет совершить абстрактно-теоретико-категориальный прорыв.

Монада - это интерфейс с двумя методами:

• "поднять в монаду". Давайте называть этот метод 'pure'. Функция от одного аргумента. На входе какое-то значение, на выходе это же значение, но помеченое другим типом.
• "применить функцию к значению в монаде" или "совершить действие". В энергичном языке, думаю, уместо было бы название 'apply'. Функция от двух аргументов. На входе монадическое значение (полученное из первой функции) и собственно функция-действие, которое нужно применить к первому аргументу. На выходе новое монадическое значение, то есть изменённое функцией-действитем. Ну, эта особенность с "на выходе новое", она в общем-то нужна в языках с одним присваиванием, в остальных можно передать монадическое значение по ссылке и поменять его.

Всё остальное относится к конкретным монадам и рассматривать их нужно отдельно.

Собственно, весь смысл в двух вещах:

1. новый тип даёт инкапсуляцию
2. явная передача функции-действия развязывает (decoupling) их от собственно процесса применения действия. И основная фишка в том, что этот, своего рода, late binding может происходить не в рантайме (как в технологии COM, если знаете), а во время компиляции. С хорошей поддержкой полиморфизма в системе типов можно:

• гибко определять как будут выполняться одинаковые действия в разных монадах
• повторно использовать однажды определённые действия в новых монадах.