Transduce

Transduce

关注
发信
关注(28)粉丝(399)

javascript - 如何以正确的顺序链接映射和过滤函数

我真的很喜欢链接 Array.prototype.map 、 filter 和 reduce 来定义数据转换。不幸的是，在最近的一个涉及大型日志文件的项目中，我无法再多次循环遍历我的数据......

我的目标:

我想创建一个链接 .filter 和 .map 方法的函数，而不是立即映射数组，而是组成一个循环遍历数据一次的函数。 IE。:

const DataTransformation = () => ({
    map: fn => (/* ... */),
    filter: fn => (/* ... */),
    run: arr => (/* ... */)
});

const someTransformation = DataTransformation()
    .map(x => x + 1)
    .filter(x => x > 3)
    .map(x => x / 2);

// returns [ 2, 2.5 ] without creating [ 2, 3, 4, 5] and [4, 5] in between
const myData = someTransformation.run([ 1, 2, 3, 4]);

我的尝试:

受到 this answer 和 this blogpost 的启发，我开始编写 Transduce 函数。
const filterer = pred => reducer => (acc, x) =>
    pred(x) ? reducer(acc, x) : acc;

const mapper = map => reducer => (acc, x) =>
    reducer(acc, map(x));

const Transduce = (reducer = (acc, x) => (acc.push(x), acc)) => ({
    map: map => Transduce(mapper(map)(reducer)),
    filter: pred => Transduce(filterer(pred)(reducer)),
    run: arr => arr.reduce(reducer, [])
});

问题:

上面 Transduce 片段的问题在于它“向后”运行......我链接的最后一个方法是第一个执行的:
const someTransformation = Transduce()
    .map(x => x + 1)
    .filter(x => x > 3)
    .map(x => x / 2);

// Instead of [ 2, 2.5 ] this returns []
//  starts with (x / 2)       -> [0.5, 1, 1.5, 2]
//  then filters (x < 3)      -> []
const myData = someTransformation.run([ 1, 2, 3, 4]);

或者，用更抽象的术语:



我想我明白它为什么会发生，但我无法弄清楚如何在不改变我的函数的“接口(interface)”的情况下修复它。

问题:

如何使Transduce方法链以正确顺序链接filter和map操作？

笔记:
  • 我只是在学习我正在尝试做的一些事情的命名。如果我错误地使用了 Transduce 术语或者是否有更好的方法来描述问题，请告诉我。
  • 我知道我可以使用嵌套的 for 循环来做同样的事情:


    • const push = (acc, x) => (acc.push(x), acc);
const ActionChain = (actions = []) => {
  const run = arr =>
    arr.reduce((acc, x) => {
      for (let i = 0, action; i < actions.length; i += 1) {
        action = actions[i];

        if (action.type === "FILTER") {
          if (action.fn(x)) {
            continue;
          }

          return acc;
        } else if (action.type === "MAP") {
          x = action.fn(x);
        }
      }

      acc.push(x);
      return acc;
    }, []);

  const addAction = type => fn =>
    ActionChain(push(actions, { type, fn }));

  return {
    map: addAction("MAP"),
    filter: addAction("FILTER"),
    run
  };
};

// Compare to regular chain to check if
// there's a performance gain
// Admittedly, in this example, it's quite small...
const naiveApproach = {
  run: arr =>
    arr
      .map(x => x + 3)
      .filter(x => x % 3 === 0)
      .map(x => x / 3)
      .filter(x => x < 40)
};

const actionChain = ActionChain()
  .map(x => x + 3)
  .filter(x => x % 3 === 0)
  .map(x => x / 3)
  .filter(x => x < 40)


const testData = Array.from(Array(100000), (x, i) => i);

console.time("naive");
const result1 = naiveApproach.run(testData);
console.timeEnd("naive");

console.time("chain");
const result2 = actionChain.run(testData);
console.timeEnd("chain");
console.log("equal:", JSON.stringify(result1) === JSON.stringify(result2));


  • 这是我在堆栈片段中的尝试:


    • const filterer = pred => reducer => (acc, x) =>
  pred(x) ? reducer(acc, x) : acc;

const mapper = map => reducer => (acc, x) => reducer(acc, map(x));

const Transduce = (reducer = (acc, x) => (acc.push(x), acc)) => ({
  map: map => Transduce(mapper(map)(reducer)),
  filter: pred => Transduce(filterer(pred)(reducer)),
  run: arr => arr.reduce(reducer, [])
});

const sameDataTransformation = Transduce()
  .map(x => x + 5)
  .filter(x => x % 2 === 0)
  .map(x => x / 2)
  .filter(x => x < 4);

// It's backwards:
// [-1, 0, 1, 2, 3]
// [-0.5, 0, 0.5, 1, 1.5]
// [0]
// [5]
console.log(sameDataTransformation.run([-1, 0, 1, 2, 3, 4, 5]));

    最佳答案

    在我们知道更好之前



    我明白了，我会安抚你，但你会明白强制你的程序通过链接 API 是不自然的，而且在大多数情况下比它值得的麻烦更多。



    问题确实出在您的 Transduce 构造函数上。您的 map 和 filter 方法将 map 和 pred 堆叠在传感器链的外部，而不是将它们嵌套在内部。

    下面，我已经实现了您的 Transduce API，它以正确的顺序评估 map 和过滤器。我还添加了一个 log 方法，以便我们可以看到 Transduce 的行为

    const Transduce = (f = k => k) => ({
  map: g =>
    Transduce(k =>
      f ((acc, x) => k(acc, g(x)))),
  filter: g =>
    Transduce(k =>
      f ((acc, x) => g(x) ? k(acc, x) : acc)),
  log: s =>
    Transduce(k =>
      f ((acc, x) => (console.log(s, x), k(acc, x)))),
  run: xs =>
    xs.reduce(f((acc, x) => acc.concat(x)), [])
})

const foo = nums => {
  return Transduce()
    .log('greater than 2?')
    .filter(x => x > 2)
    .log('\tsquare:')
    .map(x => x * x)
    .log('\t\tless than 30?')
    .filter(x => x < 30)
    .log('\t\t\tpass')
    .run(nums)
}

// keep square(n), forall n of nums
//   where n > 2
//   where square(n) < 30
console.log(foo([1,2,3,4,5,6,7]))
// => [ 9, 16, 25 ]



    未开发的潜力



    在阅读我写的那个答案时，您忽略了 Trans 的通用质量，因为它是在那里写的。在这里，我们的 Transduce 只尝试处理数组，但实际上它可以处理任何具有空值 ( [] ) 和 concat 方法的类型。这两个属性组成了一个名为 Monoids 的类别，如果我们不利用转换器处理该类别中任何类型的能力，我们会对自己造成伤害。

    上面，我们在 [] 方法中硬编码了初始累加器 run，但这可能应该作为参数提供——就像我们对 iterable.reduce(reducer, initialAcc) 所做的一样

    除此之外，两种实现本质上是等效的。最大的区别是链接答案中提供的 Trans 实现是 Trans 本身是一个幺半群，但这里的 Transduce 不是。 Trans在concat方法中巧妙地实现了换能器的组成，而Transduce(上述)在每种方法中都有混合的组成。使其成为幺半群允许我们以与所有其他幺半群相同的方式对 Trans 进行合理化，而不必将其理解为某些具有独特 map 、 filter 和 run 方法的专门链接接口(interface)。

    我建议从 Trans 构建而不是制作自己的自定义 API

    有你的蛋糕，也吃它

    所以我们学到了统一接口(interface)的宝贵教训，我们明白 Trans 本质上很简单。但是，您仍然需要那个甜蜜的链接 API。好的好的...

    我们将再实现一次 Transduce，但这一次我们将使用 Trans monoid。在这里， Transduce 保存一个 Trans 值而不是一个延续 ( Function )。

    其他一切都保持不变 - foo 进行 1 次微小更改并产生相同的输出。
    // generic transducers
const mapper = f =>
  Trans(k => (acc, x) => k(acc, f(x)))

const filterer = f =>
  Trans(k => (acc, x) => f(x) ? k(acc, x) : acc)

const logger = label =>
  Trans(k => (acc, x) => (console.log(label, x), k(acc, x)))

// magic chaining api made with Trans monoid
const Transduce = (t = Trans.empty()) => ({
  map: f =>
    Transduce(t.concat(mapper(f))),
  filter: f =>
    Transduce(t.concat(filterer(f))),
  log: s =>
    Transduce(t.concat(logger(s))),
  run: (m, xs) =>
    transduce(t, m, xs)
})

// when we run, we must specify the type to transduce
//   .run(Array, nums)
// instead of
//   .run(nums)

    展开此代码片段以查看最终实现——当然，您可以跳过定义单独的 mapper 、 filterer 和 logger ，而是直接在 Transduce 上定义它们。我认为这读起来更好。

    // Trans monoid
const Trans = f => ({
  runTrans: f,
  concat: ({runTrans: g}) =>
    Trans(k => f(g(k)))
})

Trans.empty = () =>
  Trans(k => k)

const transduce = (t, m, xs) =>
  xs.reduce(t.runTrans((acc, x) => acc.concat(x)), m.empty())

// complete Array monoid implementation
Array.empty = () => []

// generic transducers
const mapper = f =>
  Trans(k => (acc, x) => k(acc, f(x)))

const filterer = f =>
  Trans(k => (acc, x) => f(x) ? k(acc, x) : acc)

const logger = label =>
  Trans(k => (acc, x) => (console.log(label, x), k(acc, x)))

// now implemented with Trans monoid
const Transduce = (t = Trans.empty()) => ({
  map: f =>
    Transduce(t.concat(mapper(f))),
  filter: f =>
    Transduce(t.concat(filterer(f))),
  log: s =>
    Transduce(t.concat(logger(s))),
  run: (m, xs) =>
    transduce(t, m, xs)
})

// this stays exactly the same
const foo = nums => {
  return Transduce()
    .log('greater than 2?')
    .filter(x => x > 2)
    .log('\tsquare:')
    .map(x => x * x)
    .log('\t\tless than 30?')
    .filter(x => x < 30)
    .log('\t\t\tpass')
    .run(Array, nums)
}

// output is exactly the same
console.log(foo([1,2,3,4,5,6,7]))
// => [ 9, 16, 25 ]



    总结

    所以我们从一堆 lambda 开始，然后使用幺半群使事情变得更简单。 Trans monoid 提供了明显的优势，因为 monoid 接口(interface)是已知的，并且通用实现非常简单。但是我们很顽固，或者我们有一些目标要实现，而这些目标不是我们设定的——我们决定构建神奇的 Transduce 链接 API，但我们使用坚如磐石的 Trans monoid 来实现，它为我们提供了 Trans 的所有功能，但也保持复杂性很好地划分。

    点链恋物癖匿名

    这是我最近写的关于方法链的其他几个答案
  • Is there any way to make a functions return accessible via a property?
  • Chaining functions and using an anonymous function
  • Pass result of functional chain to function

    • 10-07 23:55
    Powered by LMLPHP ©2024 Transduce 0.034254