Функциональный Javascript. Пишем свои линзы, часть 1

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

Зачем нужны линзы

Начнем, пожалуй, с ответа на вопрос, зачем же нужны линзы.

В функциональном программировании широко используются неизменяемые структуры данных. Работа с ними значительно отличается по сравнению с изменяемыми данными.

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

Пример:

Пусть у нас есть структура данных:

var user = {
	name: 'Имя пользователя',
	address: {
		city: 'Город',
		street: 'Улица',
		house: 'Дом'
	}
};

У нас стоит задача поменять значение имени.

Если мы работаем с этой структурой как с изменяемой, то достаточно просто изменить значение в объекте user:

function setName(value, user) {
	user.name = value;
	return user;
} 

Но если мы работаем с этой структурой как с неизменяемой, то мы не имеем право менять данные в исходном объекте. Нам нужно создать новый объект user2 в который поместить все значения из user за исключением нового name.

Вариант с полным копированием:

function setName(value, user) {
	return {
		name: value,
		address: {
			city: user.address.city,
			street: user.address.street,
			house: user.address.house
		}
	};
}

PS: Пример передает только суть. По хорошему тут должны быть проверки на то, что user != null, user.adress != null.

Вариант с частичным копированием:

function setName(value, user) {
	return {
		name: value,
		address: user.address
	};
}

Думаю схема понятна, поэтому напишем общие функции для работы со свойствами структуры:

//генерация гетеров
function get(prop) {
	return function(item) {
		return item[prop];
	};
}
//генерация сетеров изменяемых структур
function setMutable(prop) {
	return function(value, item) {
		item[prop] = value;
		return item;
	}
}
//генерация сетеров для неизменяемых структур
function setImmutable(prop) {
	return function(value, item) {
		var props = properties(item), //получаем список всех свойств объекта
			copy = props.reduce(function(lst, next) {
				lst[next] = item[next];
				return lst;
			}, {}); 
		copy[prop] = value; //меняем на новое значение
		return copy;
	};
}

//возвращает список свойств объекта obj
function properties(obj) {
	var key, lst = [];
	for (key in obj) {
	 	if (obj.hasOwnProperty(key)) {
		   lst.push(key);
	  	}
	}
	return lst;
}

Теперь мы можем использовать эти функции для генерации гетеров и сетеров.

Исходный пример может быть переписан так:

setName = setMutable('name') //Для изменяемой структуры
setName = setImmutable('name') //Для неизменяемой
getName = get('name') //Для получения имени в обоих случаях

Теперь предположим, что нам нужно поменять значение city у user.

Поставим задачу более обще и напишем гетеры и сетеры позволяющие работать с city через объект user.

Для изменямой структуры реализация может выглядеть так:

function getUserCity(user) {
	return user.address.city;
}

function setUserCity(value, user) {
	user.address.city = value;
	return user;
}

Или тоже самое, но в более функциональном стиле, используя уже определенные функции get, setMutable:

var getAddress = get('address'),
	getCity = get('city'),
	getUserCity = compose(getCity, getAddress), // функция compose строит новую функцию которая по очереди (справа на лево) применяет к входящему значения функции переданные ей в качестве аргументов. Т.е. это тоже что
	getUserCity = function(item) {
		return getCity(getAddress(item));
	},
	setCity = setMutable('city'),
	setUserCity = function (value, item) {
		setCity(value, getAddress(item))
		return item;
	}

var newUser = setUserCity('новый city', user);

getUserCity(newUser) == 'новый city' // true

//P.S.
function compose(func1, func2) {
  return function() {
    return func1(func2.apply(null, arguments));
  };
}

Давайте попробуем реализовать тоже для неизменямой структуры:

var getAddress = get('address'),
	getCity = get('city'),
	getUserCity = compose(getCity, getAddress),
	setCity = setImmutable('city'),
	setUserCity = function (value, item) {
		setCity(value, getAddress(item))
		return item;
	};

var newUser = setUserCity('новый city', user);

getUserCity(newUser) == 'новый city' // true

На первый взгляд все нормально. Но обратите внимание на функцию setUserCity. В ней мы получаем на вход новое значение для city value и пользователя item, изменяем значение city и… возвращаем исходный объект item. Но это противоречит определению неизменямых структур данных. При изменении любой его части мы должны создать новый объект.

Применение функции setUserCity превращает наш неизменяемый объект обратно в изменяемый. Чтобы это проверить давайте выполним следующий код:

var newUser1 = setUserCity('city1', user),
	newUser2 = setUserCity('city2', user);
	newUser1 == newUser2 //true

Чтобы исправить это, нужно переписать значение address у пользователя item, и вернуть нового пользователя

var setAddress = setImmutable('address'),
	setUserCity = function (value, item) {
		var address = setCity(value, getAddress(item));
		return setAddress(address, user);
	},
	newUser1 = setUserCity('city1', user),
	newUser2 = setUserCity('city2', user);
	newUser1 == newUser2 //false 

Теперь все работает как надо.

Выводы:

Композиция гетеров осуществляется одинаково как для изменяемых так и для неизменяемых структур, но построение сетеров отличается значительно.

Для построения сетера глубиной n изменяемой структуры данных достаточно использования n — 1 гетеров и одного сетера с последнего уровня.

Для получения сетера неизменяемой структуры глубиной n необходимо n — 1 гетеров и n сетеров, т.к. необходимо обновлять все уровни начиная с 0 (исходный объект).

Для упрощения построения (компоновки) сетеров (и гетеров) неизменяемых структур данных удобно использовать инструмент линзы.

Линзы

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

Но давайте введем абстракцию называемую линзой, которая есть не что иное как пара гетера и сетера:

var lens = Lens(getter, setter) //конструктор линзы.

Так же введем тривиальные операции get, set которые будут просто дублировать функционал переданных линзе гетера и сетера:

function Lens(getter, setter) {
    return {
        get: getter,
        set: setter
    };
}

А теперь давайте еще разок глянем на функцию setUserCity. При погружении с уровня A на уровень B нам нужны гетеры и сетеры A и B. Но мы ведь только что ввели новую абстракцию Lens. Почему бы композицию сетеров и гетеров по отдельности не заменить композицией их линз?

Давайте введем новую операцию на линзах compose, которая строит композицию двух линз:

function Lens(getter, setter) {
    return {
        compose: function (lens) {
            return Lens(get2, set2);

            function get2(item) {
                return lens.get(getter(item));
            }

            function set2 (value, item) {
                var innerValue = lens.set(value, getter(item));
                return setter(innerValue, item);
            }
        },
        get: getter,
        set: setter
    };
}

Давайте попробуем решить нашу задачу с использованием линз:

var addressLens = Lens(getAddress, setAddress), //строим линзу для адреса
    cityLens = Lens(getCity, setCity), //строим линзу для города
    addressCityLens = addressLens.compose(cityLens); //компонуем две линзы вместе

    addressCityLens.set('новый city', user); //изменяем значение city через user, используя линзу

Обратите внимание на композицию линз. Она очень похожа на композицию через точку user.address.city. Добавление новой линзы как бы погружает нас на уровень ниже.

На практике довольно часто будет встречаться потребность к изменению значения с учетом его текущего значения, поэтому давайте расширим нашу абстракцию еще одной операцией modify:

function Lens(getter, setter) {
    return {
		modify: function (func, item) {
			var value = getter(item);

			return setter(func(value), item);
		}, 
        compose: function (lens) {
            return Lens(get2, set2);

            function get2(item) {
                return lens.get(getter(item));
            }

            function set2 (value, item) {
                var innerValue = lens.set(value, getter(item));
                return setter(innerValue, item);
            }
        },
        get: getter,
        set: setter
    };
}

Синтаксический сахар

Мы узнали что такое линзы, для чего они нужны и как ими пользоваться. Но давайте подумаем, как можно сделать работу с линзами проще.
Во первых, мало вероятно, что нам понадобится создавать линзу с гетером и сетером на разные поля (хотя это теоретически можно сделать). Поэтому давайте перегрузим конструктор линз. Он будет принимать имя свойства и автоматически генерировать для него линзу.

function Lens(getter, setter) {
	//Если передан 1 параметр, то это название свойства
	if (arguments.length == 1) {
		var property = arguments[0];
		getter = get(property);
		setter = setImmutable(property);
	}
    return {
		modify: function (func, item) {
			var value = getter(item);

			return setter(func(value), item);
		},
        compose: function (lens) {
            return Lens(get2, set2);

            function get2(item) {
                return lens.get(getter(item));
            }

            function set2 (value, item) {
                var innerValue = lens.set(value, getter(item));
                return setter(innerValue, item);
            }
        },
        get: getter,
        set: setter
    };
}

Теперь исходный пример может быть записан как:

Lens('address').compose(Lens('city')).set('новый city', user);

Создание линз облегчилось, но вот композиция выглядит довольно громоздко. Давайте напишем небольшой интерпретатор, который будет создавать линзы и строить их композицию. На вход он будет принимать список из названий свойств для которых нужно создать линзы. А операция композиции будет задаваться точкой (в лучших традициях Haskell, но в отличие от него осуществляться она будет слева направо).
Врезультате наш пример должен преобразоваться в нечто такое:

lens('address.city').set('новый city', user);

Что же, довольно близко к user.address.city. Давайте реализуем функцию lens

function lens(cmd) {
	var lenses = cmd.split('.')
					.map(pass1(Lens));

	return lenses.reduce(function(lst, next) {
		return lst.compose(next);
	});
}
//функция которая из переданной ей на вход функции делает такую,
//которая игнорирует все переданные ей аргументы, кроме первого
function pass1(func) {
	return function(x) {
		return func(x);
	};
}

Обратите внимание на функцию pass1. Дело в том, что map передает в callbaсk больше чем 1 параметр, поэтому если мы напишем map(Lense) то будет использоваться версия Lense принимающая на вход гетер и сетер. Поэтому мы оборачиваем нашу функцию pass1, которая гарантирует, что в Lense попадет только первый переданный ей параметр.

Во второй части мы рассмотрим, как можно подружить линзы и монаду Nothing.