如何为 monad 实现通用提升功能？

Question

我有一堆 arity 感知提升函数：

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]

是否可以实现相应的通用提升功能？

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

我猜这是一个递归算法，但我无法理解它。

Answer 1

是的，你可以递归地完成 ms，但我想折叠更合适：

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

Answer 2

这是递归程序，以防你仍然对它感兴趣 -

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 ]

我们可以修改 lift 使其取决于用户提供的函数的数量，例如这个双参数函数 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 ]

或者这个三参数函数，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 ]

这是实现 -

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 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 ]

如何为 monad 实现通用提升功能？

How to implement a generic lift function for monads?

javascript

monads

functional-programming

lifting