#javascript #functional-programming #monads #monad-transformers
#javascript #функциональное программирование #монады #monad-transformers
Вопрос:
Я знаю, как реализовать преобразователь монад с одним связанным списком, но не смог запустить его аналог массива. Проблема в том, что существует эффект группировки, который делает преобразователь действительным только для коммутативных базовых монад. Вот пример, в котором для простоты и трансформатор, и базовая монада являются массивами, и нет оболочки типа transformer:
// ARRAY
const arrMap = f => xs =>
xs.map((x, i) => f(x, i));
const arrAp = tf => xs =>
arrFold(acc => f =>
arrAppend(acc)
(arrMap(x => f(x)) (xs)))
([])
(tf);
const arrOf = x => [x];
const arrChain = mx => fm =>
arrFold(acc => x =>
arrAppend(acc) (fm(x))) ([]) (mx);
// Transformer
const arrChainT = ({map, ap, of ,chain}) => mmx => fmm =>
chain(mmx) (mx => {
const go = ([x, ...xs]) =>
x === undefined
? of([])
: ap(map(arrCons) (fmm(x))) (go(xs));
return chain(go(mx)) (ys => of(arrFold(arrAppend) ([]) (ys)));
});
const arrOfT = of => x => of([x]);
// Transformer stack
const arrArrChain = arrChainT(
{map: arrMap, ap: arrAp, of: arrOf, chain: arrChain});
const arrArrOf = arrOfT(arrOf);
// auxiliary functions
const arrFold = f => init => xs => {
let acc = init;
for (let i = 0; i < xs.length; i )
acc = f(acc) (xs[i], i);
return acc;
};
const arrAppend = xs => ys =>
xs.concat(ys);
const arrCons = x => xs =>
[x].concat(xs);
// MAIN
foo = x =>
x === 0
? [[0, 1]]
: [[0], [1]];
console.log(JSON.stringify(
arrArrChain(arrArrChain(foo(0)) (foo)) (foo)));
// yields [[0,1,0,0,1],[0,1,1,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1]]
console.log(JSON.stringify(
arrArrChain(foo(0)) (x => arrArrChain(foo(x)) (foo))));
// yields [[0,1,0,0,1],[0,1,0,0],[0,1,0,1],[0,1,1,0,1],[0,1,1,0],[0,1,1,1]] Оба вычисления должны дать одинаковый результат. Теперь мой вопрос: есть ли способ реализовать преобразователь массива законным способом?
Комментарии:
1. Экземпляр monad transformer массивов будет таким же, как у списков , поскольку они изоморфны. Обратите внимание, что наивная реализация экземпляра преобразователя монады списка также не выдает монаду, если аргумент monad не является коммутативным.
2. @AaditMShah Я сделал Listt-done-right строгим, и он все еще работает. Мне не нравится это признавать, но в конце концов вы правы.
Ответ №1:
Преобразователь монад массива такой же, как и преобразователь монад списка.
// Step m a = null | { head : a, tail : ListT m a }
// ListT m a = m (Step m a)
// nil : Monad m -> ListT m a
const nil = M => M.pure(null);
// cons : Monad m -> a -> ListT m a -> ListT m a
const cons = M => head => tail => M.pure({ head, tail });
// foldr : Monad m -> (a -> m b -> m b) -> m b -> ListT m a -> m b
const foldr = M => f => a => m => M.bind(m)(step =>
step ? f(step.head)(foldr(M)(f)(a)(step.tail)) : a);
// append : Monad m -> ListT m a -> ListT m a -> ListT m a
const append = M => m1 => m2 => foldr(M)(cons(M))(m2)(m1);
// pure : Monad m -> a -> ListT m a
const pure = M => x => cons(M)(x)(nil(M));
// bind : Monad m -> ListT m a -> (a -> ListT m b) -> ListT m b
const bind = M => m => f => foldr(M)(x => append(M)(f(x)))(nil(M))(m);
// MonadListT : Monad m -> Monad (ListT m)
const MonadListT = M => ({ pure: pure(M), bind: bind(M) });
// MonadArray : Monad Array
const MonadArray = { pure: x => [x], bind: a => f => a.flatMap(f) };
// MonadListArray : Monad (ListT Array)
const MonadListArray = MonadListT(MonadArray);
// fromArray : Monad m -> Array a -> ListT m a
const fromArray = M => a => a.reduceRight((xs, x) => cons(M)(x)(xs), nil(M));
// lift : Monad m -> m a -> ListT m a
const lift = M => m => M.bind(m)(pure(M));
// foo : Nat -> ListT Array Nat
const foo = x => x === 0
? fromArray(MonadArray)([0, 1])
: lift(MonadArray)([0, 1]);
// associativityLHS : Monad m -> m a -> (a -> m b) -> (b -> m c) -> m c
const associativityLHS = M => m => k => h => M.bind(M.bind(m)(k))(h);
// associativityRHS : Monad m -> m a -> (a -> m b) -> (b -> m c) -> m c
const associativityRHS = M => m => k => h => M.bind(m)(x => M.bind(k(x))(h));
// lhs :: ListT Array Nat
const lhs = associativityLHS(MonadListArray)(foo(0))(foo)(foo);
// rhs :: ListT Array Nat
const rhs = associativityRHS(MonadListArray)(foo(0))(foo)(foo);
console.log(JSON.stringify(lhs) === JSON.stringify(rhs));
console.log(JSON.stringify(lhs)); Обратите внимание, что каждый шаг списка заключен в аргумент monad . Это позволяет чередовать другие монадические действия, и необходимо сохранить законы монады, если аргумент monad не является коммутативным.
Комментарии:
1. Спасибо за добавление типа sigs.
2. По моему скромному мнению, вам действительно следует потратить часть своего времени на обучение людей. Ваши ответы всегда затрагивают суть проблемы, не ходя вокруг да около. И они предполагают наличие необходимого объема предварительных знаний, чтобы иметь возможность следовать им.
3. Раньше я был ассистентом преподавателя в Университете Индианы на курсе бакалавриата «Введение в информатику». Следовательно, я, вероятно, мог бы начать онлайн-курс по обучению функциональному программированию на JavaScript. Хотя это был бы очень простой курс. Моей целевой аудиторией будут люди, которые знают JavaScript, но не знакомы с функциональным программированием. Мне нужно будет подумать над курсовой работой. Дайте мне знать, если вы хотите помочь. Я думаю, важно, чтобы больше людей понимали принципы функционального программирования.
4. Я скорректировал кодировку вашего метода в соответствии с кодировкой моей функции и попытался сделать
foldrнестрогий с помощью неявных звуков, как в Haskell. Хотя неявные прогоны должны быть полностью прозрачными для алгоритма, это не сработало. Только когда я добавилstrictкомбинатор (похожий на шаблон взрыва Хаскелла) внутриappendнего. Это захватывающее открытие для меня. Вы можете понять решение на repl