3

I have a variadic lifting function that allows for flat monadic chains without deeply nested function composition:

const varArgs = f => {
  const go = args =>
    Object.defineProperties(
      arg => go(args.concat(arg)), {
        "runVarArgs": {get: function() {return f(args)}, enumerable: true},
        [TYPE]: {value: "VarArgs", enumerable: true}
      });

  return go([]);
};

const varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold
  const go = (ms, g, i) =>
    i === ms.length
      ? of(g)
      : chain(ms[i]) (x => go(ms, g(x), i + 1));

  return varArgs(ms => go(ms, f, 0));
};

It works but I'd like to abstract from the recursion with a fold. A normal fold doesn't seem to work, at least not along with the Task type, 

const varLiftM = (chain, of) => f =>
  varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms))); // A

because the algebra in line A would return a Task for each iteration, not a partially applied function.

How can I replace the non-tail recursion with a fold?

Here is a working example of the current recursive implementation:

const TYPE = Symbol.toStringTag;

const struct = type => cons => {
  const f = x => ({
    ["run" + type]: x,
    [TYPE]: type,
  });

  return cons(f);
};

// variadic argument transformer

const varArgs = f => {
  const go = args =>
    Object.defineProperties(
      arg => go(args.concat(arg)), {
        "runVarArgs": {get: function() {return f(args)}, enumerable: true},
        [TYPE]: {value: "VarArgs", enumerable: true}
      });

  return go([]);
};

// variadic monadic lifting function

const varLiftM = (chain, of) => f => { // TODO: replace recursion with a fold
  const go = (ms, g, i) =>
    i === ms.length
      ? of(g)
      : chain(ms[i]) (x => go(ms, g(x), i + 1));

  return varArgs(ms => go(ms, f, 0));
};

// asynchronous Task

const Task = struct("Task") (Task => k => Task((res, rej) => k(res, rej)));

const tOf = x => Task((res, rej) => res(x));

const tMap = f => tx =>
  Task((res, rej) => tx.runTask(x => res(f(x)), rej));

const tChain = mx => fm =>
  Task((res, rej) => mx.runTask(x => fm(x).runTask(res, rej), rej));

// mock function

const delay = (ms, x) =>
  Task(r => setTimeout(r, ms, x));

// test data

const tw = delay(100, 1),
  tx = delay(200, 2),
  ty = delay(300, 3),
  tz = delay(400, 4);

// specialization through partial application

const varAsyncSum =
  varLiftM(tChain, tOf) (w => x => y => z => w + x + y + z);

// MAIN

varAsyncSum(tw) (tx) (ty) (tz)
  .runVarArgs
  .runTask(console.log, console.error);

console.log("1 sec later...");

[EDIT] As desired in the comments my fold implementation:

const arrFold = alg => zero => xs => {
  let acc = zero;

  for (let i = 0; i < xs.length; i++)
    acc = alg(acc) (xs[i], i);

  return acc;
};
Improve this question
9
  • That is a lot of minified code to go over. Could you simplify the example? Commented Jun 2, 2019 at 17:39
  • @cristy thats not minified, thats "functional programming" :) Commented Jun 2, 2019 at 17:56
  • 2
    Well, naming your parameters like ms, g, x, f, fm, of, tx, res, rej and then using all of them (almost at once) for me looks like unnecessary minification, making the code much harder to read unless you know what it is about. Commented Jun 2, 2019 at 17:59
  • 3
    @Cristy most of those, if not all, are rather idiomatic in functional programming. Similar to how you'd name a variable i if it's a counter or index of some sort. f - function, g also a function (alphabetically after f, akin to j being used as a counter after i is declared), fm - function returning a monad, ms - monads plural, so an array, of function doing a type lift into a monad. x - generic name for an input variable. res and rej - result (success) and rejection (failure). tx, ty, tz - task1, task2, task3. Commented Jun 2, 2019 at 18:16
  • The short names just reflect how general the code is. You can use varLiftM with any monad, for instance. To complete the name legend by @VLAZ: mx monadic value, ms monadic values, fm monadic action (function that returns a monad). tx just means a value wrapped in a type without telling something about the constraints (i.e. if it is monadic, applicative, functorial, traversal, foldable, etc). Commented Jun 2, 2019 at 18:38

2 Answers 2

Reset to default
0

That of call around arrFold seems a bit out of place.

I'm not sure whether your arrFold is a right fold or left fold, but assuming it is a right fold you will need to use continuation passing style with closures just as you did in your recursive implementation:

varArgs(ms => of(arrFold(g => mx => chain(mx) (g)) (f) (ms)))

becomes

varArgs(ms => arrFold(go => mx => g => chain(mx) (x => go(g(x)))) (of) (ms) (f))

With a left fold, you could write

varArgs(arrFold(mg => mx => chain(g => map(g) (mx)) (mg)) (of(f)))

but you need to notice that this builds a different call tree than the right fold:

of(f)
chain(of(f))(g0 => map(m0)(g0))
chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1))
chain(chain(chain(of(f))(g0 => map(m0)(g0)))(g1 => map(m1)(g1)))(g2 => map(m2)(g2))

vs (with the continuations already applied)

of(f)
chain(m0)(x0 => of(f(x0)))
chain(m0)(x0 => chain(m1)(x1 => of(f(x0)(x1))))
chain(m0)(x0 => chain(m1)(x1 => chain(m2)(x2) => of(f(x0)(x1)(x2)))))

According to the monad laws, they should evaluate to the same, but in practice one might be more efficient than the other.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Clever - at least i think it is. I need to look deeper into this tomorrow. +1 because i am pretty sure i'll learn something tomorrow.
The arrFold function is a left fold.
@Bergi builds a different call tree - OK, this only matters if the binary operator isn't associative/commutative. Additionally, at least for Arrays you can transform any left fold to a right one and vice versa by applying flip/Array.prototype.reverse to the operator and the consumed array respectively. This could cause performance iusses though...
0

You don't need the full power of monads for this particular use case. Applicative functors are all you need:

// type Cont r a = (a -> r) -> r

// type Async a = Cont (IO ()) a

// pure :: a -> Async a
const pure = a => k => k(a);

// ap :: Async (a -> b) -> Async a -> Async b
const ap = asyncF => asyncA => k => asyncF(f => asyncA(a => k(f(a))));

// delay :: (Number, a) -> Async a
const delay = (ms, a) => k => setTimeout(k, ms, a);

// async1, async2, async3, async4 :: Async Number
const async1 = delay(100, 1);
const async2 = delay(200, 2);
const async3 = delay(300, 3);
const async4 = delay(400, 4);

// sum :: Number -> Number -> Number -> Number -> Number
const sum = a => b => c => d => a + b + c + d;

// uncurry :: (a -> b -> c) -> (a, b) -> c
const uncurry = f => (a, b) => f(a)(b);

// result :: Async Number
const result = [async1, async2, async3, async4].reduce(uncurry(ap), pure(sum));

// main :: IO ()
result(console.log);
console.log("1 second later...");

If you want, you can define an applicative context function (i.e. apply) as follows:

const apply = (asyncF, ...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);

const result = apply(pure(sum), async1, async2, async3, async4);

If you curry this function then you can create a lift function:

const apply = asyncF => (...asyncArgs) => asyncArgs.reduce(uncurry(ap), asyncF);

const lift = f => apply(pure(f));

const asyncSum = lift(sum);

const result = asyncSum(async1, async2, async3, async4);

Notice that reduce is the equivalent to arrFold. Hence, lift is equivalent to varLiftM.

Improve this answer

7 Comments

I guess I got the hint: Don't get too complicated and maybe my varArgs approach is too complicated. I'll keep that in mind. Oh, and I know the difference between applicative (depends on the previous effect) and monad (may additionally depend on the value of the previous effect) . At work I try to use the former as often as possible.
Yes, it is indeed convoluted. The problem is that although JavaScript is not a good functional programming language, yet people try to write complex functional programs using it. JavaScript is more suitable for Pythonic code than Haskelline code. However, because it tries to borrow elements of myriad languages it ends up being neither as versatile as Python nor as elegant as Haskell. If you are really keen on becoming a better functional programmer, try writing a compiler for a functional programming language in JavaScript. en.m.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours
A compiler is an excellent project to work on if you're keen on becoming a great programmer. Not only will you learn how a programming language is designed, but also you will experience how to write and maintain a non-trivial piece of software. The best goal to strive for is to build a self-hosting compiler (i.e. a compiler for a source language written in the same source language, which is able to compile itself to some target language). I love compiler construction. I was pursuing my PhD in it before I decided to join the industry. If you ask questions about it I'd be more than happy to help
Thanks for the advice. Maybe you recall my runtime type validator project a year ago. I always wanted to take the next step but I've never found the time so far.
Runtime type validation is nice but it'll never be as powerful as compile time type checking/inference. You can only do so much at runtime.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.