Реализация монад в JavaScript

Question

Теперь, когда node.js поддерживает генераторы ECMAScript Harmony, мы можем кратко написать монадический код do блоки в Хаскеле:

function monad(unit, bind) {
    return function (f) {
        return function () {
            var g = f.apply(this, arguments);

            return typeOf(g) === "Generator" ? send() : unit(g);

            function send(value) {
                var result = g.next(value);
                if (result.done) return unit(result.value);
                else return bind(result.value, send);
            }
        };
    };
}

function typeOf(value) {
    return Object.prototype.toString.call(value).slice(8, -1);
}

В коде выше monad это функция, которая может быть использована для создания детерминированных монад, таких как:

var maybe = monad(function (a) {
    return {just: a};
}, function (m, f) {
    return m === null ? null : f(m.just);
});

Теперь вы можете использовать maybe следующее:

var readZip = maybe(function * (a, b) {
    var a = yield readList(a);
    var b = yield readList(b);
    return _.zip(a, b);
});

Выше функция readZip берет две строки, преобразует их в списки и затем архивирует их. Если есть ошибка, она сразу возвращается null, Это зависит от следующей функции:

function readList(string) {
    try {
        var value = JSON.parse(string);
        return value instanceof Array ? {just: value} : null;
    } catch (error) {
        return null;
    }
}

Мы проверяем его, чтобы проверить, работает ли он так, как ожидается:

console.log(readZip('[1,2,3,4]', '["a","b"]')); // [[1,"a"],[2,"b"],[3,"c"]]
console.log(readZip('hello', '["a","b"]'));     // null
console.log(readZip('[1,2,3,4]', 'world'));     // null

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

var cont = monad(function (a) {
    return function (k) {
        return k(a);
    };
}, function (m, k) {
    return function (c) {
        return m(function (a) {
            return k(a)(c);
        });
    };
});

Теперь мы можем использовать cont для создания функций в стиле продолжения кратко:

var fib = cont(function * (n) {
    switch (n) {
    case 0: return 0;
    case 1: return 1;
    default:
        var x = yield fib(n - 1);
        var y = yield fib(n - 2);
        return x + y;
    }
});

Вы можете использовать fib функционировать следующим образом:

fib(10)(function (a) { console.log(a); }); // 55

к несчастью monad работает только для детерминированных монад. Это не работает для недетерминированных монад, таких как list монада, потому что вы можете возобновить генератор из определенной позиции только один раз.

Поэтому мой вопрос заключается в следующем: есть ли другой способ реализации недетерминированных монад, таких как list Монада кратко в JavaScript?

Answer 1

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

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

var extend = function(a, b) {
  for (var i in b)
    a[i] = b[i];
  return a;
};

// Chain a new `this`
var fluent = function(f) {
  return function() {
    var clone = extend(Object.create(null), this);
    f.apply(clone, arguments);
    return clone;
  };
};

var toArray = function(x) {
  return Array.prototype.slice.call(x);
};

var List = {
  unit: fluent(function() {
    this.x = toArray(arguments);
  }),
  bind: function(f) {
    var fx = this.x.map(f.bind(this));
    var a = fx[0];
    for (var i=1; i<fx.length; i++)
      a.x = a.x.concat(fx[i].x);
    return a;
  },
  lift: function(f) {
    return function(x) {
      return List.unit(f(x));
    }
  },
  valueOf: function() {
    return this.x;
  }
};

var add1 = function(x) {
  return x + 1;
};

// Laws
var m = List.unit(3);
var f = List.lift(add1);

var laws = [
  m.bind(f)[0] == f(3)[0],
  m.bind(function(x){ return List.unit(x) })[0] == m[0],
  m.bind(function(x){ return f(x).bind(f) })[0] == m.bind(f).bind(f)[0]
];

console.log(laws); //=> [true, true, true]

// lift
var result = List.unit(1,2).bind(List.lift(add1)); //=> [2,3]

console.log(result.valueOf());

// do
var result = List.unit(1,2).bind(function(x) {
  return this.unit(3,4).bind(function(y) {
    return this.unit(x + y);
  });
});

console.log(result.valueOf()); //=> [4,5,5,6]

Очевидно, что синтаксис "do" ведет к адскому обратному вызову, но в LiveScript вы можете облегчить боль:

result = do
  x <- List.unit 1 2 .bind
  y <- @unit 3 4 .bind
  @unit x + y

Вы также можете назвать bind метод творчески:

result = do
  x <- List.unit 1 2 .\>=
  y <- @unit 3 4 .\>=
  @unit x + y

Answer 2

Поэтому мой вопрос заключается в следующем: есть ли другой способ реализации недетерминированных монад, таких как list Монада кратко в JavaScript?

Да, вы можете реализовать недетерминированные монады, такие как монада списка, в JavaScript с использованием генераторов, как, например, immutagen. Однако, поскольку генераторы в JavaScript не могут быть возобновлены с определенной позиции несколько раз, вы должны эмулировать это поведение, создавая и воспроизводя несколько генераторов. Это решение имеет несколько недостатков.

1. Это неэффективно, потому что необходимо создавать и воспроизводить несколько генераторов, что приводит к квадратичному росту сложности времени.
2. Это работает только для чистых монад и чистых вычислений, потому что необходимо создать и воспроизвести несколько генераторов. Следовательно, побочные эффекты будут неправильно выполняться несколько раз.

То, что нам нужно для создания недетерминированных монад, таких как монада списка, является неизменяемым генератором. Неизменный генератор может быть возобновлен с определенной позиции несколько раз. К сожалению, JavaScript не поддерживает встроенные генераторы. Однако мы можем эмулировать его, создавая и воспроизводя несколько изменяемых генераторов. Итак, давайте посмотрим, как создать неизменный генератор.

Первая проблема, которую нам нужно решить, это способ воспроизведения изменяемого генератора в определенной точке. Мы делаем это с помощью специального класса функций, называемых регенераторами. Регенератор - это любая функция, которая возвращает изменяемый генератор. Простейшим примером такой функции является function* () {}, Таким образом, каждая функция генератора является регенератором, но не каждая функция генератора является функцией генератора. Вы можете создавать новые регенераторы, продвигая старый регенератор, используя следующую функцию.

// type Regenerator = Arguments -> MutableGenerator

// next :: (Regenerator, Arguments) -> Regenerator
const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

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

const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

const regen1  = next(regen0, 1, 2, 3);
const regen2  = next(regen1, undefined); // first value of mutable generator ignored
const regen3  = next(regen2, 10);

const gen1 = regen3(20);
const gen2 = regen3(30);

const result1 = gen1.next(40).value; // 10 + 20 + 40
const result2 = gen2.next(50).value; // 10 + 30 + 50

console.log(result1, result2);

function* regen0(a, b, c) {
    const x = yield a;
    const y = yield b;
    const z = yield c;
    return x + y + z;
}

Как видите, мы можем продвинуть регенератор, используя next Функция или применить регенератор к значению, чтобы получить изменяемый генератор. Теперь, когда у нас есть возможность воспроизвести изменяемый генератор в определенной точке, мы можем создать неизменяемые генераторы следующим образом.

// immutagen :: Regenerator -> Arguments -> ImmutableGenerator
const immutagen = regen => (...args) => function loop(regen) {
    return (gen, data) => {
        const {value, done} = gen.next(data);
        if (done) return {value, next: null};

        let replay = false;
        const recur = loop(next(regen, data));
        return {value, next: value => {
            if (replay) return recur(regen(data), value);
            replay = true; return recur(gen, value);
        }};
    };
}(next(regen, ...args))(regen(...args));

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

const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

const immutagen = regen => (...args) => function loop(regen) {
    return (gen, data) => {
        const {value, done} = gen.next(data);
        if (done) return {value, next: null};

        let replay = false;
        const recur = loop(next(regen, data));
        return {value, next: value => {
            if (replay) return recur(regen(data), value);
            replay = true; return recur(gen, value);
        }};
    };
}(next(regen, ...args))(regen(...args));

const foo = immutagen(function* (a, b, c) {
    const x = yield a;
    const y = yield b;
    const z = yield c;
    return x + y + z;
});

const bar = foo(1, 2, 3).next(10).next(20);

const result1 = bar.next(30).value; // 10 + 20 + 30
const result2 = bar.next(40).value; // 10 + 20 + 40

console.log(result1, result2);

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

const next = (regen, ...args) => data => {
    const gen = regen(...args);
    return gen.next(data), gen;
};

const immutagen = regen => (...args) => function loop(regen) {
    return (gen, data) => {
        const {value, done} = gen.next(data);
        if (done) return {value, next: null};

        let replay = false;
        const recur = loop(next(regen, data));
        return {value, next: value => {
            if (replay) return recur(regen(data), value);
            replay = true; return recur(gen, value);
        }};
    };
}(next(regen, ...args))(regen(...args));

const monad = bind => regen => (...args) => function loop({value, next}) {
    return next ? bind(value, val => loop(next(val))) : value;
}(immutagen(regen)(...args));

const flatMap = (array, callback) => array.flatMap(callback);

const list = monad(flatMap);

const foo = list(function* (xs, ys) {
    const x = yield xs;
    const y = yield ys;
    return [x * y];
});

console.log(foo([1, 2, 3], [4, 5, 6]));

Обратите внимание, что monad функция нужна только bind, Это не нужно unit,

Answer 3

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

Но по крайней мере вы можете абстрагироваться от chain применяя монады как аппликативы:

const arrChain = mx => fm =>
  mx.reduce((acc, x) => arrAppend(acc) (fm(x)), []);

const arrAppend = xs => ys =>
  (xs.push.apply(xs, ys), xs);

const chain2 = chain => tx => ty => fm =>
  chain(chain(tx) (x => fm(x)))
    (gm => chain(ty) (y => gm(y)));

const main = chain2(arrChain)
  ([1,2])
    ([3,4])
      (x => [y => [x, y]]); // nested constructor application

// prev-val-next-eff-dependency:

const main2 = chain2(arrChain)
  ([1,2])
    ([3,4])
        (x =>
          x === 1
            ? []
            : [y => [x, y]]);

console.log(main);
console.log(main2);

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

Answer 4

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

function* unit(value) {
    yield value;
}
function* bind(list, transform) {
    for (var item of list) {
        yield* transform(item);
    }
}
var result = bind(['a', 'b', 'c'], function (element) {
    return bind([1, 2, 3], function* (element2) {
        yield element + element2;
    });
});
for (var item of result) {
    console.log(item);
}

на основе https://curiosity-driven.org/monads-in-javascript

Answer 5

потому что вы можете возобновить работу генератора с определенной позиции только один раз.

Поскольку все решения, претендующие на клонирование итераторов, на самом деле дают квадратичную сложность (технически O (| yield depth| * | количество итераторов |)), возможно, решение состоит в том, чтобы избегать итераторов, насколько это возможно, и ... настолько уродливо, насколько это возможно. вместо этого напишите соответствующие части программы в стиле передачи продолжения. Ведь продолжение может возвращаться не один раз. И я думал, что монада продолжения универсальна в том смысле, что с ней могут быть реализованы другие монады.

Возможно, тогда можно было бы выполнить какое-то синтаксическое преобразование (возможно, даже во время выполнения), чтобы упростить жизнь и не иметь гигантских вложенных операторов функций. Хотя в предыдущем вашем ответе у вас был красивый вызов / cc-but-in-CPS.

Мы могли бы использовать парсер javascript, написанный на javascript, например https://esprima.org/ , чтобы посмотреть исходный код, проверив функцию .toString(). Затем превратите его в CPS.

Например, мы могли бы сказать:

      decoCPS(
function square(x) {
    return x**2;
});

decoCPS(
function hypotenuse(a,b) {
    var sqrt = Math.sqrt;
    let aSquared = a*a;
    return sqrt(aSquared+square(b));
});

Затем это было бы волшебным образом преобразовано в CPS ... все становится сложнее, если пользователь хочет использовать изменяемое состояние или неконфлюэнтные структуры данных (возможно, передать состояние через какую-то монаду продолжения и состояния ... прототипное наследование работает медленно, но прокси-сервер может помочь), но если в настоящее время мы заботимся только о функциях, мы могли бы сказать: «поскольку мы могли бы захотеть вернуть функцию, которая закрывается по переменной, всякий раз, когда мы назначаем переменную ... или всякий раз, когда мы вызываем функция (даже в середине выражения) ... сгенерировать продолжение этого вычисления "рекурсивным образом:

      hypotenuse(a,b) {
    // original code
}

Шаг 1: параметры преобразованы:

      hypotenuse.cps = function hypotenuseCps(k, a,b) {
    var sqrt = Math.sqrt;
    let aSquared = a*a;
    return sqrt(aSquared+square(b));
}

шаг 2-9999: ??? Здесь я заблудился ... Я не уверен в точном преобразовании прямого стиля в CPS с мучительной полной детализацией. Я видел некоторые соображения здесь и здесь . Вызов функций в середине выражения может вызвать затруднения, но синтаксический анализатор действительно дает вам AST, с которым можно поиграть.

Возможно, сначала нужно превратить операторы return в k(returned value, function restOfComputationHere{...}), затем после завершения преобразования, если глобальный параметр настроен на включение стиля трамплина, преобразовать обратно в преобразователь или какую-то оболочку для преобразователя, например return new TrampolineCallMeNext(k, {args:[returned value], callback:function restOfComputationHere{...}}). Это даст пользователю выбор, всегда ли злоупотреблять механизмом SetTimeout ecmascript, что может вызвать чрезмерное замедление.

Тогда я не уверен, продвигается ли общее синтаксическое преобразование в обратном направлении построчно и / или подвыражение за подвыражением ... Я уверен, что вы знаете об этом больше и можете собрать его вместе из приведенных выше ссылок. Я бы подумал, что, возможно, у парсера-генератора (например, antlr или друзей) может быть какой-то встроенный способ преобразования CPS, но он не может найти ничего такого.

Я не разбираюсь в CPS или монадах, поэтому, пожалуйста, поправьте меня, если я ошибаюсь. Затем вы можете реализовать любую монаду, которую хотите, используя монаду продолжения. Первая ссылка дает пример реализации монады списка с использованием продолжений.

Возможно, я недооцениваю, насколько распространенным будет прямое преобразование в CPS большой части программы с такими вещами, как циклы for и другие конструкции.