Last active
June 1, 2020 15:44
-
-
Save gabejohnson/1b6e2665860b1b47dff3f0a7d2c2ee1c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Adapted from https://github.com/russellmcc/fantasydo/blob/master/index.js | |
// The `monad` argument has been added to avoid modifying the prototype of | |
// the yielded value to provide `pure` and `bind`. | |
// Note: | |
// This algorithm is not stack safe, and is inefficient due to the | |
// requirement that we bring the generator up to the previous state on each | |
// iteration. | |
// I suspect it's particularly bad for arrays. I may come back to this at | |
// some point to calculate just how bad it really is. | |
const Do = monad => genFn => { | |
const doRec = (value, state) => { | |
const gen = genFn(); | |
// Bring the new generator to the appropriate state. | |
state.forEach(it => gen.next(it)); | |
const a = gen.next(value); | |
return a.done ? | |
// Lift the return value into the monadic context | |
monad.pure(a.value) : | |
// Call bind passing the value from the call to `gen.next(...)`, | |
// add the value from the previous call to `doRec` to `state`, and | |
// call `doRec` recursively. | |
monad.bind(a.value)(value_ => doRec(value_, state.concat(value))); | |
}; | |
return doRec(null, []); | |
}; | |
// Array example | |
const ArrayMonad = { | |
pure: Array.of, | |
bind: xs => f => xs.flatMap(f) | |
}; | |
Do(ArrayMonad)(function*() { | |
const x = yield [1,2,3]; | |
const y = yield [x+1,x+2,x+3]; | |
return x + y; | |
}); // [3, 4, 5, 5, 6, 7, 7, 8, 9] | |
// Promise example | |
// Note: JavaScript `Promise` is not a valid Monad as it doesn't obey | |
// the Monad laws (see https://buzzdecafe.github.io/2018/04/10/no-promises-are-not-monads). | |
// However, promises can still be used with `Do` given the below definition | |
const PromiseMonad = { | |
pure: x => Promise.resolve(x), | |
bind: p => f => p.then(f) | |
}; | |
Do(PromiseMonad)(function*() { | |
const x = yield Promise.resolve(1); | |
const y = yield Promise.resolve(2); | |
return x + y | |
}); // Promise(3) | |
// Helpers | |
const match = v => matcher => { | |
for (let case_ in matcher) { | |
if (case_ in v) { return matcher[case_](v[case_]); } | |
} | |
throw Error(`No case matched for ${v}`); | |
} | |
const flip = f => x => y => f(y)(x); | |
const compose = f => g => x => f(g(x)); | |
// Maybe example | |
const Maybe = { | |
Nothing: {Nothing: undefined}, | |
Just: x => ({Just: x}), | |
pure: x => Maybe.Just(x), | |
bind: m => f => match(m) ({ | |
Nothing: () => Maybe.Nothing, | |
Just: x => f(x) | |
}), | |
do: genFn => Do(Maybe)(genFn) | |
}; | |
Maybe.do(function*() { | |
const x = yield Maybe.Just(1); | |
const y = yield Maybe.Just(2); | |
return x + y; | |
}); // { Just: 3 } | |
Maybe.do(function*() { | |
const x = yield Maybe.Nothing; | |
const y = yield Maybe.Just(2); | |
return x + y; | |
}); // { Nothing: undefined } | |
// List example | |
const List = { | |
Nil: {Nil: undefined}, | |
Cons: head => tail => ({Cons: {head, tail}}), | |
reduce: f => { | |
const go = d => xs => | |
match(xs) ({ | |
Nil: () => d, | |
Cons: ({head, tail}) => go (f(d)(head)) (tail) | |
}); | |
return go; | |
}, | |
reduceRight: f => d => { | |
const reverse = List.reduce (flip (List.Cons)) (List.Nil); | |
return compose (List.reduce (flip(f)) (d)) (reverse); | |
}, | |
concat: xs => ys => List.reduceRight(List.Cons)(ys)(xs), | |
pure: x => List.Cons(x)(List.Nil), | |
bind: xs => f => match(xs) ({ | |
Nil: () => List.Nil, | |
Cons: ({head, tail}) => List.concat(f(head)) (List.bind(tail)(f)) | |
}), | |
do: genFn => Do(List)(genFn), | |
fromArray: xs => xs.reduceRight((acc, x) => List.Cons(x)(acc), List.Nil), | |
toArray: xs => List.reduce(acc => x => (acc.push(x), acc))([])(xs) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment