11 января 2013 г.

Перевод с Haskell на Javascript избранных частей лучшего введения в монады которое я когда-либо читал

English: Test logo for Haskell wikibook (for d...

Примечание переводчика 

Оригинал статьи расположен по адресу: http://blog.jcoglan.com/2011/03/05/translation-from-haskell-to-javascript-of-selected-portions-of-the-best-introduction-to-monads-ive-ever-read/


Перевод с Haskell на Javascript избранных частей лучшего введения в монады которое я когда-либо читал

Я знаю, знаю, миру не нужно еще одно введение в монады (или еще один пост, жалующийся на отсутствие еще одного введения в монады). Поэтому вас обрадует, что этот пост не один из подобных, в том смысле что он не нов. Я думаю я написал его потому что, во-первых, о монадах очень важно знать, а во-вторых, потому что я хочу разобраться как они связаны с асинхронным программированием и поэтому я использую Javascript чтобы помочь понять те вещи, о которых я возможно напишу позже. Также это полезное упражнение в мышлении в терминах типов. Если вы хотя бы немного знакомы с Haskell, я очень рекомендую вам прочитать исходную публикацию, Вы могли изобрести монады! (Или уже сделали это).
Для начала, небольшая предыстория. Монады наиболее используемы в языке Haskell, т.к. он разрешает только чистые функции, которые не имеют побочных эффектов. Чистые функции принимают аргументы на входе и возвращают результат, и это всё. Языки, которые я обычно использую (Ruby и Javascript) не имеют этого ограничения, но использование чистых функций часто становится полезным и развивает. Любое введение в монады расскажет вам, что монады это про сокрытие побочных эффектов функций в функциональной модели, благодаря которой вы можете делать I/O, но это не единственное приложение монад. Монады на самом деле про композирование функций, как мы увидем далее.
Рассмотрим пример. Предположим у вас есть функция нахождения синуса числа, которая в Javascript является просто оберткой вокруг библиотеки Math:
var sine = function(x) { return Math.sin(x) };
И у вас есть другая функция, возвращающая куб числа:
var cube = function(x) { return x * x * x };
Эти функции принимают один аргумент как вход и один аргумент возвращают, что позволяет сделать их композируемыми: вы можете использовать результат одной функции как параметр следующей:
var sineCubed = cube(sine(x));



Создадим функцию инкапсулирующую эту композицию. Она принимает две функции на вход f и g и возвращает другую функцию которая вычисляет f(g(x)).
var compose = function(f, g) {
  return function(x) {
    return f(g(x));
  };
};
var sineOfCube = compose(sine, cube);
var y = sineOfCube(x);
Далее предположим, нам необходимо отлаживать эти функции и мы хотим выводить на экран сообщение о том, что функция была вызвана. Мы можем сделать это так:
var cube = function(x) {
  console.log('cube was called.');
  return x * x * x;
};
Но нам нельзя использовать это в системе, которая разрешает только чистые функции: console.log() не является ни аргументом, ни возвращаемым значением функции, следовательно это побочный эффект. Если мы хотим получить отладочную информацию, она должна стать частью возвращаемого значения. Давайте изменим наши функции, чтобы возвращать пару значений: результат и некоторую отладочную информацию:
var sine = function(x) {
  return [Math.sin(x), 'sine was called.'];
};
var cube = function(x) {
  return [x * x * x, 'cube was called.'];
};
Но теперь мы обнаружим, к удивлению, что теперь функции не композируемы:
cube(3) // -> [27, 'cube was called.']
compose(sine, cube)(3) // -> [NaN, 'sine was called.']
Это перестало работать по двум причинам: sine пытается вычислить значение синуса от массива, что приводит к возвращению NaN, и мы теряем отладочную информацию вызова cube. Мы ожидаем, что композиция этих функций вернет синус x в кубе, и строку означающую что cube и sine были вызваны:
compose(sine, cube)(3)
// -> [0.956, 'cube was called.sine was called.']
Простая композиция не будет работать потому что тип возвращаемого значения cube (массив) не соответствует типу аргумента sine (число). Нужна еще одна небольшая связка. Мы можем написать функцию, чтобы композировать две эти ‘отлаживаемые’ функции: она будет разбивать возвращаемые значения каждой функции и объединять их обратно понятным способом:
var composeDebuggable = function(f, g) {
  return function(x) {
    var gx = g(x),      // e.g. cube(3) -> [27, 'cube was called.']
        y  = gx[0],     //                 27
        s  = gx[1],     //                 'cube was called.'
        fy = f(y),      //     sine(27) -> [0.956, 'sine was called.']
        z  = fy[0],     //                 0.956
        t  = fy[1];     //                 'sine was called.'
    
    return [z, s + t];
  };
};

composeDebuggable(sine, cube)(3)
// -> [0.956, 'cube was called.sine was called.']
Мы «скомпозировали» две функции, принимающие число и вернули пару число+строка, и создали другую функцию с такой же сигнатурой, подразумевая возможность ее композиции с другими отлаживаемыми функциями.
Для простоты я воспользуюсь некоторой нотацией из Haskell. Следующая сигнатура означает что функция cube принимает число и возвращает пару, содержащую число и строку:
cube :: Number -> (Number,String)
Это сигнатура, которой обладают все наши отлаживаемые функции и их композиции. Наши изначальные функции имеют более простую сигнатуру Number -> Number; симметрия типа аргумента и типа возвращаемых значений это то, что делает наши функции композируемыми. Вместо того, чтобы писать отдельную логику композиции для наших отлаживаемых функций, мы просто преобразуем их сигнатуры к виду:
cube :: (Number,String) -> (Number,String)
Далее мы можем использовать нашу функцию compose для их дальнейшего композирования. Мы можем делать это преобразование от руки и сделать так, чтобы исходные функции cube и sine принимали пару (Number,String) вместо просто Number но это не масштабируемо, и вам придется писать тоже самое во всех ваших отлаживаемых функциях. Далее нам нужно сделать так, чтобы каждая функция выполняла свою задачу и было единое средство приведения функций к единому необходимому формату. Мы можем назвать эту функцию bind, и ее задача будет принимать в качестве аргумента функцию Number -> (Number,String) и возвращать функцию (Number,String) -> (Number,String).
var bind = function(f) {
  return function(tuple) {
    var x  = tuple[0],
        s  = tuple[1],
        fx = f(x),
        y  = fx[0],
        t  = fx[1];
    
    return [y, s + t];
  };
};
Мы можем использовать это чтобы преобразовать наши функции в имеющие композируемые сигнатуры и чтобы композировать их результаты.
var f = compose(bind(sine), bind(cube));
f([3, '']) // -> [0.956, 'cube was called.sine was called.']
Но теперь все функции, с которыми мы работаем, принимают пару (Number,String) как аргумент, а гораздо удобнее было бы передавать просто Number. Также как мы преобразовывали функции, теперь нам нужно приводить значения к требуемым типам, вот почему нам нужна еще одна функция:
unit :: Number -> (Number,String)
Роль функции unit принимать значение и оборачивать его в простой контейнер, чтобы мы могли работать с функциями, которые мы создали. Для наших отлаживаемых функций, это означает всего-лишь объединение числа в пару с пустой строкой:
// unit :: Number -> (Number,String)
var unit = function(x) { return [x, ''] };
var f = compose(bind(sine), bind(cube));
f(unit(3)) // -> [0.956, 'cube was called.sine was called.']
// or ...
compose(f, unit)(3) // -> [0.956, 'cube was called.sine was called.']
Эта фукнция unit  также позволяет нам привести любую функцию к виду отлаживаемой, преобразуя возвращаемое ею значение в принимаемое отлаживаемыми функциями:
// round :: Number -> Number
var round = function(x) { return Math.round(x) };
// roundDebug :: Number -> (Number,String)
var roundDebug = function(x) { return unit(round(x)) };
Снова, этот тип преобразования из ‘обычных’ функций в отлаживаемые может быть абстрагирован в функцию, которую мы назовем lift. Сигнатура функции lift говорит нам, что она принимает функцию с сигнатурой Number -> Number и возвращает функцию с сигнатурой Number -> (Number,String)
// lift :: (Number -> Number) -> (Number -> (Number,String))
var lift = function(f) {
  return function(x) {
    return unit(f(x));
  };
};
// or, more simply:
var lift = function(f) { return compose(unit, f) };
Давайте проверим как она работает с нашими функциями:
var round = function(x) { return Math.round(x) };
var roundDebug = lift(round);
var f = compose(bind(roundDebug), bind(sine));
f(unit(27)) // -> [1, 'sine was called.']
Мы изучили 3 важных абстракции для связывания отлаживаемых функций:
  • lift, которая преобразует ‘простую’ функцию в отлаживаемую
  • bind, которая преобразует отлаживаемую функцию в композируемую форму
  • unit, которая преобразует простое значение в формат, необходимый для отладки, помещая значение в контейнер
Эти абстракции (на самом деле, только bind и unit), определяют монаду. В стандартной библиотеке языка Haskell она называется монадой Writer. Возможно, еще не понятно какие части этого паттерна главные, поэтому рассмотрим другой пример.
Одна из проблем, с которой вы сталкивались много раз, это понимание того принимает ли функция единственное значение или список значений. Единственное отличие обычно, это наличие конструкции цикла for вокруг тела функции, которая является шаблонным кодом. Но это не имеет существенного значение для композирования таких функций But it does have a significant impact on how you are allowed to compose these functions. Например, представьте что у вас есть функция, вся работа которой это получение одного DOM узла и возвращение всех его потомков в виде массива; сигнатура этой функции говорит нам, что функция принимает единственный HTMLElement и возвращает массив HTMLElement.

// children :: HTMLElement -> [HTMLElement]
var children = function(node) {
  var children = node.childNodes, ary = [];
  for (var i = 0, n = children.length; i < n; i++) {
    ary[i] = children[i];
  }
  return ary;
};
// e.g.
var heading = document.getElementsByTagName('h3')[0];
children(heading)
// -> [
//      "Translation from Haskell to JavaScript...",
//      <span class=​"edit">​…​</span>​
//    ]
Теперь предположим я хочу найти grandchildren заголовка, то есть потомок потомка заголовка. Интуитивно, это определение достаточно хорошо:
var grandchildren = compose(children, children)
Но children не имеет симметричных типов аргументов и результат, поэтому мы не можем так их композировать. Если бы нас попросили написать от руки функцию grandchildren, она выглядела бы так:
// grandchildren :: HTMLElement -> [HTMLElement]
var grandchildren = function(node) {
  var output = [], childs = children(node);
  for (var i = 0, n = childs.length; i < n; i++) {
    output = output.concat(children(childs[i]));
  }
  return output;
};
Мы просто находим всех потомков потомков узла, передаваемого как аргумент, и объединяем результат в виде списка, чтобы предоставить единый список всех прапотомков. Но это неверный способ, и фактически содержит много шаблонного кода, который является результатом того, что мы работаем со списком, а не нашей проблемы, которую мы пытаемся решить. Лучше бы подошло композирование двух функций, работающих со списками, и мы бы закончили на этом.
Думая о предыдущем примере, нам необходимо два шага, чтобы исправить это: создать функцию bind чтобы преобразовать функцию children к композируемому виду, и написать функцию unit чтобы привести аргумент – heading – к допустимому типу.
Основная проблема здесь в том, что наша функция принимает единственный аргумент типа HTMLElement и возвращает список такого же типа, следовательно наше преобразование должно преобразовывать единственный объект в список объектов и так далее. То, что аргументы имеют тип HTMLElements не существенно, и в Haskell когда конкретный тип чего либо может варьировать мы используем один символ в качестве имени аргумента. unit принимает элемент и возвращает список содержащий элемент, и bind принимает функцию ‘один-ко-многим’ и возвращает функцию ‘многие-ко-многим’.
// unit :: a -> [a]
var unit = function(x) { return [x] };
// bind :: (a -> [a]) -> ([a] -> [a])
var bind = function(f) {
  return function(list) {
    var output = [];
    for (var i = 0, n = list.length; i < n; i++) {
      output = output.concat(f(list[i]));
    }
    return output;
  };
};
Теперь мы можем композировать children:
var div = document.getElementsByTagName('div')[0];
var grandchildren = compose(bind(children), bind(children));

grandchildren(unit(div))
// -> [<h1>…</h1>, <p>…</p>, ...]
Мы только что реализовали то, что в Haskell называется монадой List, которая позволяет вам композировать функции, которые отображают один элемент в список элементов.
Так что такое монада? Это паттерн проектирования. Он говорит, что если вы имеете некий класс функций принимающий один тип аргументов и возвращающий другой тип, есть две функции которые могут быть применены, чтобы сделать функции этого класса композируемыми:
  • Функция bind которая принимает любую функцию и преобразовывает в такую функцию, что она принимает тип, который возвращает, делая ее композируемой
  • Есть функция unit которая оборачивает значение в тип, принимаемый композируемыми функциями.
Я должен обеспокоится, что это черес чур поверхностное определение, и не затрагивает математическую основу монад, которую я и не собирался объяснять. Но для тех, кто программирует то, что и я, этот шаблон очень полезно знать, так как он помогает избежать дополнительной сложности там, где код занимается не решением той проблемы, для которой предназначен, а обвязыванием типов данных. Имея возможность обнаружить и устранить такой повторно используемый код, можно значительно повысить ясность вашего кода.

Примечание переводчика

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

Отдельная благодарность за идею этого поста Сергею Гулину. Благодаря нему этот перевод увидел свет.


В продолжение темы

Enhanced by Zemanta
Отправить комментарий