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

Question

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

我的目标:

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

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

我的尝试:

受到这个答案和这篇博文的启发,我开始编写一个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]);

或者,用更抽象的术语:

从...来:

Transducer(concat).map(f).map(g) == (acc, x) => concat(acc, f(g(x)))

至:

Transducer(concat).map(f).map(g) == (acc, x) => concat(acc, g(f(x)))

这类似于:

mapper(f) (mapper(g) (concat))

我想我明白为什么会这样,但我无法弄清楚如何修改它而不改变我的功能的"界面".

问题:

如何以正确的顺序进行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]));

Answer 1

在我们知道更好之前

我真的很喜欢链接......

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

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构造函数确实存在问题.你map和filter方法堆叠map和pred在传感器链的外面,而不是嵌套了他们.

下面,我已经实现了TransduceAPI,以正确的顺序评估地图和过滤器.我还添加了一个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只尝试使用Arrays,但实际上它可以使用任何具有空值([])和concat方法的类型.这两个属性构成了一个名为Monoids的类别,如果我们没有利用传感器在此类别中使用任何类型的能力,我们将自己做一个伤害.

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

除此之外,两种实现方式基本相同.最大的区别是Trans链接答案中提供的实现Trans本身就是一个幺半群,但事实Transduce并非如此.Trans在该concat方法中整齐地实现换能器的组成,而Transduce(上文)在每种方法中混合有组合物.使其成为一个独异使我们能够合理化Trans以同样的方式做所有其他类群,而不必把它理解为具有独特的一些专门的链接接口map,filter和run方法.

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

吃蛋糕,也吃

所以我们学到了统一界面的宝贵经验,我们理解这Trans本身就很简单.但是,你仍然想要那个甜蜜的链接API.好的好的...

我们将再实施Transduce一次,但这次我们将使用Transmonoid实现.这里,Transduce保持Trans值而不是continuation(Function).

其他一切都保持不变 - foo需要进行一次微小的改动并产生相同的输出.

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

包起来

所以我们从乱七八糟的lambdas开始,然后使用monoid使事情更简单.的Trans半群,所述半群接口是已知的提供不同的优点和通用的实现是非常简单的.但是我们很顽固,或者我们有目标要实现,而不是我们设定的 - 我们决定构建魔术Transduce链API,但我们使用我们坚如磐石的Transmonoid 来实现这一目标,它给了我们所有的力量,Trans但也很好地保持了复杂性区域化.

dot chaining fetishists anonymous

这是我最近写的关于方法链的其他几个答案

• 有没有办法让函数返回通过属性访问？
• 链接功能和使用匿名功能
• 将功能链的结果传递给功能