JavaScript:折叠无限流(生成器函数) [英] JavaScript: Folding infinite streams (generator function)

问题描述

在Java中，可以这样声明和折叠无限流

In Java it is possible to declare and fold infinite streams as so

List<Integer> collect = Stream.iterate(0, i -> i + 2)
    .map(i -> i * 3)
    .filter(i -> i % 2 == 0)
    .limit(10)
    .collect(Collectors.toList());

// -> [0, 6, 12, 18, 24]

在JavaScript中，我可以使用生成器函数来产生和散布值流.

In JavaScript I could use generator functions to yield and spread stream of values.

// Limit the value in generator
let generator = (function* () {
    for (let i=0; i<10; i++) {
        yield i
    }
})()

[ ...generator ]
    .map(i => i * 3)
    .filter(i => i % 2 === 0)

// -> [0, 6, 12, 18, 24]

但是我如何流式传输并折叠无限流?我知道我可以使用for (n of generator)循环来迭代和限制流.但是，使用Java示例之类的流畅API是否有可能?

But how could I stream and fold an infinite stream? I know I could iterate and limit the stream with for (n of generator) loop. But is it possible with fluent API such as Java example?

推荐答案

下面是一个示例-

// a terminating generator
const range = function* (from, to)
{ while (from < to)
    yield from++
}

// higher-order generator
const G =
  range(0, 100).filter(isEven).map(square)

for (const x of G)
  console.log(x)

// (0*0) (2*2) (4*4) (6*6) (8*8) ...
// 0 4 16 36 64 ...

我们可以通过扩展生成器原型来使类似的事情成为可能-

We can make something like this possible by extending the generator prototype -

const Generator =
  Object.getPrototypeOf(function* () {})

Generator.prototype.map = function* (f, context)
{ for (const x of this)
    yield f.call(context, x)
}

Generator.prototype.filter = function* (f, context)
{ for (const x of this)
    if (f.call(context, x))
      yield x
}

展开下面的代码片段，以验证我们在浏览器中的进度-

Expand the snippet below to verify our progress in your browser -

const Generator =
  Object.getPrototypeOf(function* () {})

Generator.prototype.map = function* (f, context)
{ for (const x of this)
    yield f.call(context, x)
}

Generator.prototype.filter = function* (f, context)
{ for (const x of this)
    if (f.call(context, x))
      yield x
}

// example functions
const square = x =>
  x * x

const isEven = x =>
  (x & 1) === 0
  
// an terminating generator
const range = function* (from, to)
{ while (from < to)
    yield from++
}

// higher-order generator
for (const x of range(0, 100).filter(isEven).map(square))
  console.log(x)

// (0*0) (2*2) (4*4) (6*6) (8*8) ...
// 0 4 16 36 64 ...

继续进行操作，例如fold或collect之类的方法假定流最终终止，否则它无法返回值-

Moving on, something like fold or collect assumes that the stream eventually terminates, otherwise it cannot return a value -

Generator.prototype.fold = function (f, acc, context)
{ for (const x of this)
    acc = f.call(context, acc, x)
  return acc
}

const result =
  range(0, 100)      // <- a terminating stream
    .filter(isEven)
    .map(square)
    .fold(add, 0)    // <- assumes the generator terminates

console.log(result)
// 161700

如果必须折叠无限个流，则可以实现limit-

If you have to fold an infinite stream, you can implement limit -

Generator.prototype.limit = function* (n)
{ for (const x of this)
    if (n-- === 0)
      break // <-- stop the stream
    else
      yield x
}

// an infinite generator
const range = function* (x = 0)
{ while (true)
    yield x++
}

// fold an infinite stream using limit
const result =
  range(0)          // infinite stream, starting at 0
    .limit(100)     // limited to 100 values
    .filter(isEven) // only pass even values
    .map(square)    // square each value
    .fold(add, 0)   // fold values together using add, starting at 0

console.log(result)
// 161700

展开下面的代码片段，以在浏览器中验证结果-

Expand the snippet below to verify the result in your browser -

const Generator =
  Object.getPrototypeOf(function* () {})

Generator.prototype.map = function* (f, context)
{ for (const x of this)
    yield f.call(context, x)
}

Generator.prototype.filter = function* (f, context)
{ for (const x of this)
    if (f.call(context, x))
      yield x
}

Generator.prototype.fold = function (f, acc, context)
{ for (const x of this)
    acc = f.call(context, acc, x)
  return acc
}

Generator.prototype.limit = function* (n)
{ for (const x of this)
    if (n-- === 0)
      break // <-- stop the stream
    else
      yield x
}

const square = x =>
  x * x

const isEven = x =>
  (x & 1) === 0
  
const add = (x, y) =>
  x + y

// an infinite generator
const range = function* (x = 0)
{ while (true)
    yield x++
}

// fold an infinite stream using limit
const result =
  range(0)          // starting at 0
    .limit(100)     // limited to 100 values
    .filter(isEven) // only pass even values
    .map(square)    // square each value
    .fold(add, 0)   // fold values together using add, starting at 0

console.log(result)
// 161700

上面，请注意在filter表达式之后将limit的顺序更改为 会如何改变结果-

Above, notice how changing the order of the limit to after the filter expression changes the result -

const result =
  range(0)          // starting at 0
    .filter(isEven) // only pass even values
    .limit(100)     // limited to 100 values
    .map(square)    // square each value
    .fold(add, 0)   // fold values together using add, starting at 0

console.log(result)
// 1313400

在第一个程序中-

1. 以无限范围(0, 1, 2, 3, 4, ...)
开始
2. 限制为100个值(0, 1, 2, 3, 4, ...,97, 98, 99)
3. 仅传递偶数值(0, 2, 4, ...94, 96, 98)
4. 平方每个值(0, 4, 16, ..., 8836, 9216, 9604)
5. 使用加号折叠值，从0开始，(0 + 0 + 4 + 16 + ..., + 8836 + 9216 + 9604)
6. 结果161700

1. start with an infinite range (0, 1, 2, 3, 4, ...)
2. limit to 100 values (0, 1, 2, 3, 4, ...,97, 98, 99)
3. only pass even values (0, 2, 4, ...94, 96, 98)
4. square each value (0, 4, 16, ..., 8836, 9216, 9604)
5. fold values using add, starting at 0, (0 + 0 + 4 + 16 + ..., + 8836 + 9216 + 9604)
6. result 161700

在第二个程序中-

1. 以无限范围(0, 1, 2, 3, 4, ...)
开始
2. 仅传递偶数值(0, 2, 4, ...)
3. 限制为100个值(0, 2, 4, 6, 8, ...194, 196, 198)
4. 平方每个值(0, 4, 16, 36, 64, ..., 37636, 38416, 29304)
5. 使用加号折叠值，从0开始，(0 + 4 + 16 + 36 + 64 + ..., + 37636+ 38416 + 29304)
6. 结果1313400

1. start with an infinite range (0, 1, 2, 3, 4, ...)
2. only pass even values (0, 2, 4, ...)
3. limit to 100 values (0, 2, 4, 6, 8, ...194, 196, 198)
4. square each value (0, 4, 16, 36, 64, ..., 37636, 38416, 29304)
5. fold values using add, starting at 0, (0 + 4 + 16 + 36 + 64 + ..., + 37636+ 38416 + 29304)
6. result 1313400

---

最后，我们实现了collect，它与fold不同，它不要求初始累加器.取而代之的是，从流中手动抽取第一个值，并将其用作初始累加器.恢复该流，将每个值与上一个折叠-

---

Finally we implement collect, which unlike fold, does not ask for an initial accumulator. Instead, the first value is manually pumped from the stream and used as the initial accumulator. The stream is resumed, folding each value with the previous one -

Generator.prototype.collect = function (f, context)
{ let { value } = this.next()
  for (const x of this)
    value = f.call(context, value, x)
  return value
}

const toList = (a, b) =>
  [].concat(a, b)

range(0,100).map(square).collect(toList)
// [ 0, 1, 2, 3, ..., 97, 98, 99 ]

range(0,100).map(square).collect(add)
// 4950

---

请注意，双重消耗您的视频流！ JavaScript不会为我们提供持久的迭代器，因此一旦使用了流，就无法可靠地调用该流上的其他高阶函数-

---

And watch out for double-consuming your streams! JavaScript does not give us persistent iterators, so once a stream is consumed, you cannot reliably call other higher-order functions on the stream -

// create a stream
const stream  =
  range(0)
    .limit(100)
    .filter(isEven)
    .map(square)

console.log(stream.fold(add, 0)) // 161700
console.log(stream.fold(add, 0)) // 0 (stream already exhausted!)

// create another stream
const stream2  =
  range(0)
    .limit(100)
    .filter(isEven)
    .map(square)

console.log(stream2.fold(add, 0)) // 161700
console.log(stream2.fold(add, 0)) // 0 (stream2 exhausted!)

当您执行merge-

const r =
  range (0)

r.merge(r, r).limit(3).fold(append, [])
// double consume! bug!
// [ [ 0, 1, 2 ], [ 3, 4, 5 ], [ 6, 7, 8 ] ]
// expected:
// [ [ 0, 0, 0 ], [ 1, 1, 1 ], [ 2, 2, 2 ] ]

// fresh range(0) each time
range(0).merge(range(0), range(0)).limit(3).fold(append, [])
// correct:
// [ [ 0, 0, 0 ], [ 1, 1, 1 ], [ 2, 2, 2 ] ]

每次使用新鲜生成器(range(0)...)可以避免此问题-

Using a fresh generator (range(0)...) each time avoids the problem -

const stream =
  range(0)
    .merge
      ( range(0).filter(isEven)
      , range(0).filter(x => !isEven(x))
      , range(0).map(square)
      )
    .limit(10)

console.log ('natural + even + odd + squares = ?')
for (const [ a, b, c, d ] of stream)
  console.log (`${ a } + ${ b } + ${ c } + ${ d } = ${ a + b + c + d }`)

// natural + even + odd + squares = ?
// 0 + 0 + 1 + 0 = 1
// 1 + 2 + 3 + 1 = 7
// 2 + 4 + 5 + 4 = 15
// 3 + 6 + 7 + 9 = 25
// 4 + 8 + 9 + 16 = 37
// 5 + 10 + 11 + 25 = 51
// 6 + 12 + 13 + 36 = 67
// 7 + 14 + 15 + 49 = 85
// 8 + 16 + 17 + 64 = 105
// 9 + 18 + 19 + 81 = 127

这是为我们的生成器使用参数的关键原因:它将使您考虑正确地重用它们.因此，我们的流应该始终是函数，而不是将stream定义为上面的const，即使是空值-

This is the key reason to use parameters for our generators: it will get you to think about reusing them properly. So instead of defining stream as a const above, our streams should always be functions, even if nullary ones -

// streams should be a function, even if they don't accept arguments
// guarantees a fresh iterator each time
const megaStream = (start = 0, limit = 1000) =>
  range(start) // natural numbers
    .merge
      ( range(start).filter(isEven) // evens
      , range(start).filter(x => !isEven(x)) // odds
      , range(start).map(square) // squares
      )
    .limit(limit)

const print = s =>
{ for (const x of s)
    console.log(x)
}

print(megaStream(0).merge(megaStream(10, 3)))
// [ [ 0, 0, 1, 0 ], [ 10, 10, 11, 100 ] ]
// [ [ 1, 2, 3, 1 ], [ 11, 12, 13, 121 ] ]
// [ [ 2, 4, 5, 4 ], [ 12, 14, 15, 144 ] ]

print(megaStream(0).merge(megaStream(10), megaStream(100)).limit(5))
// [ [ 0, 0, 1, 0 ], [ 10, 10, 11, 100 ], [ 100, 100, 101, 10000 ] ]
// [ [ 1, 2, 3, 1 ], [ 11, 12, 13, 121 ], [ 101, 102, 103, 10201 ] ]
// [ [ 2, 4, 5, 4 ], [ 12, 14, 15, 144 ], [ 102, 104, 105, 10404 ] ]
// [ [ 3, 6, 7, 9 ], [ 13, 16, 17, 169 ], [ 103, 106, 107, 10609 ] ]
// [ [ 4, 8, 9, 16 ], [ 14, 18, 19, 196 ], [ 104, 108, 109, 10816 ] ]

我们可以将merge实现为-

Generator.prototype.merge = function* (...streams)
{ let river = [ this ].concat(streams).map(s => [ s, s.next() ])
  while (river.every(([ _, { done } ]) => done === false))
  { yield river.map(([ _, { value } ]) => value)
    river = river.map(([ s, _ ]) => [ s, s.next() ])
  }
}

展开下面的代码片段，以在浏览器中验证结果-

Expand the snippet below to verify the result in your browser -

const Generator =
  Object.getPrototypeOf(function* () {})

Generator.prototype.map = function* (f, context)
{ for (const x of this)
    yield f.call(context, x)
}

Generator.prototype.filter = function* (f, context)
{ for (const x of this)
    if (f.call(context, x))
      yield x
}

Generator.prototype.limit = function* (n)
{ for (const x of this)
    if (n-- === 0)
      break // <-- stop the stream
    else
      yield x
}

Generator.prototype.merge = function* (...streams)
{ let river = [ this ].concat(streams).map(s => [ s, s.next() ])
  while (river.every(([ _, { done } ]) => done === false))
  { yield river.map(([ _, { value } ]) => value)
    river = river.map(([ s, _ ]) => [ s, s.next() ])
  }
}

const isEven = x =>
  (x & 1) === 0

const square = x =>
  x * x

const range = function* (x = 0)
{ while (true)
    yield x++
}

// streams should be functions, even if they don't have parameters
const megaStream = (start = 0, limit = 1000) =>
  range(start) // natural numbers
    .merge
      ( range(start).filter(isEven) // evens
      , range(start).filter(x => !isEven(x)) // odds
      , range(start).map(square) // squares
      )
    .limit(limit)

// for demo only
const print = s =>
{ for (const x of s) console.log(x) }

print(megaStream(0).merge(megaStream(10, 3)))
// [ [ 0, 0, 1, 0 ], [ 10, 10, 11, 100 ] ]
// [ [ 1, 2, 3, 1 ], [ 11, 12, 13, 121 ] ]
// [ [ 2, 4, 5, 4 ], [ 12, 14, 15, 144 ] ]

print(megaStream(0).merge(megaStream(10), megaStream(100)).limit(5))
// [ [ 0, 0, 1, 0 ], [ 10, 10, 11, 100 ], [ 100, 100, 101, 10000 ] ]
// [ [ 1, 2, 3, 1 ], [ 11, 12, 13, 121 ], [ 101, 102, 103, 10201 ] ]
// [ [ 2, 4, 5, 4 ], [ 12, 14, 15, 144 ], [ 102, 104, 105, 10404 ] ]
// [ [ 3, 6, 7, 9 ], [ 13, 16, 17, 169 ], [ 103, 106, 107, 10609 ] ]
// [ [ 4, 8, 9, 16 ], [ 14, 18, 19, 196 ], [ 104, 108, 109, 10816 ] ]

这篇关于JavaScript:折叠无限流(生成器函数)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！