I'm attempting to implement functors in Javascript without using container types ([]/{}). Hence, I solely utilize pure higher order functions to construct them:
const option = x => f => isAssigned(x) ? option(f(x)) : none;
const none = option(null);
const isAssigned = x => x !== null && x !== undefined;
const inc = x => x + 1;
const sqr = x => x * x;
const head = xs => xs[0]
const log = x => (console.log(x), x);
option(head([4])) (inc) (sqr) (log); // 25
option(head([])) (inc) (sqr) (log); // not executedoption takes a value and a pure function, lifts the function into its context, applies it to the value and returns the result in the same context. I guess it is a functor. However, it doesn't follow the functor prototcol in Javascript, that each functor must own a map function on its prototype.
option can apparently be extended to a monad-like type (at least it behaves like one in my example):
const option = x => f => isAssigned(x) ? option(f(x)) : none;
const option_ = x => f => isAssigned(x) ? flatten(option(f(x))) : none;
const none = option(null);
const of = x => option(x); // return
const flatten = F => { // it gets a bit ugly here
let y;
F(z => (y = z, z));
return y;
};
// auxiliary functions
const compn = (...fs) => x => fs.reduceRight((acc, f) => f(acc), x);
const getOrElse = x => F => {
let y;
F(z => (y = z, z));
return isAssigned(y) ? y : x;
};
const isAssigned = x => x !== null && x !== undefined;
const log = prefix => x => (console.log(prefix, x), x);
const head = xs => xs[0];
const head_ = xs => option(xs[0]);
const sqr = x => x * x;
// some data
const xs = [5],
ys = [];
// run
const w = option(xs) (head),
x = option(ys) (head),
y = option_(xs) (head_),
z = option_(ys) (head_);
log("square head of xs:") (compn(sqr, getOrElse(1)) (w)); // 25
log("square head of ys:") (compn(sqr, getOrElse(0)) (x)); // 0
log("square head_ of xs:") (compn(sqr, getOrElse(0)) (y)); // 25
log("square head_ of ys:") (compn(sqr, getOrElse(0)) (z)); // 0Provided option is actually a functor my question is: Is it possible to express every functor/monad solely with (pure) higher order functions, where the results of contextual (or effectful) computations are held in the call stack?
Of course. Aside from a couple JS primitives (*, +, Number, and String) to demonstrate functionality, below you will only see:
const identity = x => x
const fromNullable = x => x == null ? None : Option(x)
const Option = (value) => k => {
const join = () => value
const map = f => Option(f(value))
const bind = f => f(value)
const ap = m => optionMap(value)(m)
const fold = f => f(value)
return k (value, join, map, bind, ap, fold)
}
const None = () => k => {
const join = identity
const map = f => None()
const bind = f => None()
const ap = m => None()
const fold = f => f(null)
return k (null, join, map, bind, ap, fold)
}
const optionJoin = m => m((value, join, map, bind, ap, fold) => join())
const optionMap = f => m => m((value, join, map, bind, ap, fold) => map(f))
const optionBind = f => m => m((value, join, map, bind, ap, fold) => bind(f))
const optionAp = n => m => m((value, join, map, bind, ap, fold) => ap(n))
const optionFold = f => m => m((value, join, map, bind, ap, fold) => fold(f))
optionFold (console.log) (Option(5)) // 5
optionFold (console.log) (None()) // null
optionFold (console.log) (optionMap (x => x * 2) (Option(5))) // 10
optionFold (console.log) (optionMap (x => x * 2) (None()))// null
optionFold (console.log) (optionAp(Option(3)) (Option(x => x + 4))) // 7
optionFold (console.log) (optionAp(Option(3)) (None())) // null
optionFold (console.log) (optionBind(x => Option(x * x)) (Option(16))) // 256
optionFold (console.log) (optionBind(x => Option(x * x)) (None())) // null
optionFold (console.log) (optionJoin (Option(Option('hi')))) // 'hi'
optionFold (console.log) (optionJoin (Option(None())))// nullWe can skip some intermediate assignments and write it using only single-param lambdas -
const Option = value => k => // unit
k (_ => value) // join
(f => Option(f(value))) // map
(f => f(value)) // bind
(m => map(value)(m)) // ap
(f => f(value)) // fold
const None = k => // unit
k (_ => None) // join
(_ => None) // map
(_ => None) // bind
(_ => None) // ap
(f => f(null)) // fold
const join = m =>
m(v => _ => _ => _ => _ => v())
const map = f => m =>
m(_ => v => _ => _ => _ => v(f))
const bind = f => m =>
m(_ => _ => v => _ => _ => v(f))
const ap = f => m =>
f(_ => _ => _ => v => _ => v(m))
const fold = f => m =>
m(_ => _ => _ => _ => v => v(f))
const log =
fold(console.log)
log(Option(5)) // 5
log(None) // null
log(map (x => x * 2)(Option(5))) // 10
log(map (x => x * 2)(None)) // null
log(ap(Option(x => x + 4))(Option(3))) // 7
log(ap(Option(x => x + 4))(None)) // null
log(ap(None)(Option(3))) // null
log(bind(x => Option(x * x))(Option(16))) // 256
log(bind(x => Option(x * x))(None)) // null
log(join(Option(Option('hi')))) // 'hi'
log(join(Option(None))) // nullMaybe this help us see the pattern m(_ => _ => ... => ?) in the join, map, bind, ap, fold functions -
const join = m =>
m(v => _ => _ => _ => _ => v())
const map = f => m =>
m(_ => v => _ => _ => _ => v(f))
const bind = f => m =>
m(_ => _ => v => _ => _ => v(f))
const ap = f => m =>
f(_ => _ => _ => v => _ => v(m))
const fold = f => m =>
m(_ => _ => _ => _ => v => v(f))
This can be abstracted as a generic function. arity(len) returns a function, arg(n), that returns a curried function with len parameters, that returns the nth argument. This is more plainly demonstrated in code -
arity(3)(0)
// (x => _ => _ => x)
arity(4)(0)
// (x => _ => _ => _ => x)
arity(4)(1)
// (_ => x => _ => _ => x)
arity(4)(2)
// (_ => _ => x => _ => x)
arity(5)(3)
// (_ => _ => _ => x => _ => x)
We can implement arity like so -
const arity = (len = 1) => (n = 0) =>
len <= 1
? id
: n <= 0
? comp(T)(arity(len - 1)(0))
: T(arity(len - 1)(n - 1))
const id = x => x // identity
const T = x => _ => x // true
const F = _ => x => x // false
const comp = f => g => x => f(g(x)) // function composition
Now we can easily write the public api functions as simple argument selectors -
const Option = value => k => // unit
k (value) // join
(f => Option(f(value))) // map
(f => f(value)) // bind
(m => map(m)(value)) // ap
(f => f(value)) // fold
const None = k => // unit
k (None) // join
(_ => None) // map
(_ => None) // bind
(_ => None) // ap
(f => f(null)) // fold
const arg = arity(5)
const join = m => m(arg(0))
const map = m => m(arg(1))
const bind = m => m(arg(2))
const ap = m => m(arg(3))
const fold = m => m(arg(4))
There's nothing more to it :D Expand the snippet below to see verify the results in your own browser -
const id = x => x // identity
const T = x => _ => x // true
const F = _ => x => x // false
const comp = f => g => x => f(g(x)) // function composition
const arity = (len = 1) => (n = 0) =>
len <= 1
? id
: n <= 0
? comp(T)(arity(len - 1)(0))
: T(arity(len - 1)(n - 1))
const arg = arity(5)
const Option = value => k => // unit
k (value) // join
(f => Option(f(value))) // map
(f => f(value)) // bind
(m => map(m)(value)) // ap
(f => f(value)) // fold
const None = k => // unit
k (None) // join
(_ => None) // map
(_ => None) // bind
(_ => None) // ap
(f => f(null)) // fold
const join = m => m(arg(0))
const map = m => m(arg(1))
const bind = m => m(arg(2))
const ap = m => m(arg(3))
const fold = m => m(arg(4))
const log = x =>
fold(x)(console.log)
log(Option(5)) // 5
log(None) // null
log(map(Option(5))(x => x * 2)) // 10
log(map(None)(x => x * 2)) // null
log(ap(Option(x => x + 4))(Option(3))) // 7
log(ap(Option(x => x + 4))(None)) // null
log(ap(None)(Option(3))) // null
log(bind(Option(16))(x => Option(x * x))) // 256
log(bind(None)(x => Option(x * x))) // null
log(join(Option(Option('hi')))) // 'hi'
log(join(Option(None))) // null