How to implement a generic lift function for monads?

Question

I have a bunch of arity aware lift functions:

const chain = f => xs =>
  xs.reduce((acc, x) => acc.concat(f(x)), []);

const of = x => [x];

const add = (x, y) => x + y;

const liftM2 = (chain, of) => f => m1 => m2 =>
  chain(x => chain(y => of(f(x, y))) (m2)) (m1);

console.log(liftM2(chain, of) (add) ([2]) ([3])); // [5]

Is it possible to implement a corresponding generic lift function?

const liftM = (chain, of) => f => (...ms) => ...

I guess it is a recursive algorithm, but I cannot wrap my head around it.

Answer 1

Yes, you can do it recursively over ms, but I guess a fold is more suited:

const lift = (chain, of) => f => (...ms) =>
  ms.reduceRight((acc, m) =>
    (...xs) => chain(x => acc(...xs, x))(m)
  , (...xs) => of(f(...xs))
  )()

Answer 2

Here's the recursive program, in case you were still interested in it -

const chain = f => xs =>
  xs .reduce
    ( (acc, x) => acc .concat (f (x))
    , []
    )

const of = x =>
  [ x ]

const add = (x, ...xs) =>
  x === undefined
    ? 0
    : x + add (...xs)

const lift = (chain, of) => f => (...ms) =>
{ const loop = (xs, [ m, ...rest ]) =>
    m === undefined
      ? of (f (...xs))
      : chain (x => loop ([ ...xs, x ], rest)) (m)
  return loop ([], ms)
}

const print = (...xs) =>
  xs .forEach (x => console .log (JSON .stringify (x)))

print
  ( lift (chain, of) (add) ()
  , lift (chain, of) (add) ([ 1 ])
  , lift (chain, of) (add) ([ 1 ], [ 2 ])
  , lift (chain, of) (add) ([ 1 ], [ 2 ], [ 3 ])
  , lift (chain, of) (add) ([ 1 ], [ 2 ], [ 3 ], [ 4 ])
  )

// [ 0 ] [ 1 ] [ 3 ] [ 6 ] [ 10 ]

We could modify lift so that it depends on the arity of the user-supplied function, such as this two-parameter function add2 -

const add2 = (x, y) =>
  x + y

lift (chain, of) (add2) ([ 1 ]) ([ 2 ])
// [ 3 ]

lift (chain, of) (add2) ([ 1, 1 ]) ([ 2, 2, 2 ])
// [ 3, 3, 3, 3, 3, 3 ]

Or this three-parameter function, add3 -

const add3 = (x, y, z) =>
  x + y + z

lift (chain, of) (add3) ([ 1 ]) ([ 2 ]) ([ 3 ])
// [ 6 ] 

lift (chain, of) (add3) ([ 1, 1 ]) ([ 2, 2, 2 ]) ([ 3, 3, 3, 3 ])
// [ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 ]

Here's the implementation -

const curry = (f, n = f.length) =>
{ const loop = (xs, n) =>
    n === 0
      ? f (...xs)
      : x => loop ([ ...xs, x ], n - 1)
  return loop ([], n)
}

const lift = (chain, of) => f =>
{ const loop = (xs, [ m, ...rest ]) =>
    m === undefined
      ? of (f (...xs))
      : chain (x => loop ([ ...xs, x ], rest)) (m)
  return curry
    ( (...ms) => loop ([], ms)
    , f.length
    )
}

Expand the snippet below to verify the results in your own browser -

const chain = f => xs =>
  xs .reduce
    ( (acc, x) => acc .concat (f (x))
    , []
    )

const of = x =>
  [ x ]

const curry = (f, n = f.length) =>
{ const loop = (xs, n) =>
    n === 0
      ? f (...xs)
      : x => loop ([ ...xs, x ], n - 1)
  return loop ([], n)
}

const lift = (chain, of) => f =>
{ const loop = (xs, [ m, ...rest ]) =>
    m === undefined
      ? of (f (...xs))
      : chain (x => loop ([ ...xs, x ], rest)) (m)
  return curry ((...ms) => loop ([], ms), f.length)
}

const print = (...xs) =>
  xs .forEach (x => console .log (JSON .stringify (x)))


const add2 = (x, y) =>
  x + y

const add3 = (x, y, z) =>
  x + y + z

print
  ( lift (chain, of) (add2) ([ 1 ]) ([ 2 ])
  , lift (chain, of) (add2) ([ 1, 1 ]) ([ 2, 2, 2 ])
  , lift (chain, of) (add3) ([ 1, 1 ]) ([ 2, 2, 2 ]) ([ 3, 3, 3, 3 ])
  )

// [ 3 ]
// [ 3, 3, 3, 3, 3, 3 ]
// [ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 ]