(JS/TS) 为什么我的生成器函数代码在幂等性上有不同的行为？

Question

这是由生成器函数定义的惰性序列：

type Fn <T, R> = (p: T) => R ;

class Stream
<T> 
{
    
    constructor 
    (private readonly generatorFunction: () => Generator<T>) 
    {} ;
    
    
    static readonly iterate = 
    <T,> (initHead: T, f: Fn<T, T>)
    : Stream<T> => 
        
        new Stream
        ( function* ()
        : Generator<T> 
        {
            let head = initHead;
            while (true) 
            {
                yield head ;
                head = f(head);
            } ;
        } ) ;
    
    
    static readonly unfold = 
    <T, R> (initHead: T, f: Fn<T, { bloom: R; iter: T } | undefined>)
    : Stream<R> => 
        
        new Stream
        ( function* ()
        : Generator<R> 
        {
            let head = initHead;
            let next: { bloom: R, iter: T } | undefined = f(head);
            
            while (!(next === undefined)) 
            {
                yield next.bloom ;
                
                head = next.iter;
                next = f(head);
            } ;
        } ) ;
    
    
    
    readonly map = 
    <R,> (f: Fn<T, R>)
    : Stream<R> => 
        
        new Stream
        (( function* (this: Stream<T>)
        : Generator<R> 
        {
            const iterator = this.generatorFunction() ;
            while (true) 
            {
                const { value: head, done } = iterator.next();
                if (done) break;
                
                yield f(head) ;
            } ;
        } ).bind(this)) ;
    
    
    
    readonly tookUntil = 
    (when: Fn<T, boolean>)
    : [T[], Stream<T>] => 
    {
        const result: T[] = [] ;
        const iterator = this.generatorFunction() ;
        
        while (true) 
        {
            const { value: head, done } = iterator.next();
            if (done) break;
            
            result.push(head);
            if (when(head)) break;
        } ;
        
        const drops = iterator ;
        
        return [result, new Stream
        (( function* (this: Stream<T>)
        : Generator<T> 
        {
            while (true) 
            {
                const { value, done } = drops.next();
                if (done) break;
                
                yield value ;
            }
        } ).bind(this)), ] ;
    } ;
    
    readonly took = 
    (n: number)
    : [T[], Stream<T>] => 
    {
        let count = 1;
        return this.tookUntil(() => !(count++ < n));
    } ;
    
    
    readonly takeUntil = 
    (when: Fn<T, boolean>)
    : T[] => 
        
        this.tookUntil(when)[0] ;
    
    readonly take = 
    (n: number)
    : T[] => 
        
        this.took(n)[0] ;
    
    
    readonly dropUntil2 = 
    (when: Fn<T, boolean>)
    : Stream<T> => 
        
        new Stream
        (( function* (this: Stream<T>)
        : Generator<T> 
        {
            const iterator = this.generatorFunction() ;
            
            while (true) 
            {
                const { value, done } = iterator.next();
                if (done || when(value)) break;
            } ;
            
            while (true) 
            {
                const { value, done } = iterator.next();
                if (done) break;
                
                yield value ;
            } ;
        } ).bind(this)) ;
    
    
    readonly dropUntil = 
    (when: Fn<T, boolean>)
    : Stream<T> => 
        
        this.tookUntil(when)[1] ;
    
    readonly drop = 
    (n: number)
    : Stream<T> => 
        
        this.took(n)[1] ;
    
    
    
    [Symbol.iterator] = () => this.generatorFunction() ;
} ;

这是测试：

const fibonacci = Stream.iterate([0, 1], ([a, b]) => [b, a + b]).map(([x]) => x) ;
console.log(fibonacci.take(16)); // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
console.log(fibonacci.take(16)); // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
console.log(fibonacci.drop(10).take(6)); // [55, 89, 144, 233, 377, 610]


const xs = Stream.unfold(3, x => ({bloom: x-1, iter: x+1})) ;
console.log(xs.take(10)); // [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
console.log(xs.take(10)); // [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

const ys = Stream.iterate(2, x => x + 1).dropUntil2(x => !(x < 2)) ;
console.log(ys.take(10)); // [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
console.log(ys.take(10)); // [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

const zs = Stream.iterate(2, x => x + 1).map(x => x * 2) ;
console.log(zs.take(6)); // [4, 6, 8, 10, 12, 14]
console.log(zs.take(6)); // [4, 6, 8, 10, 12, 14]

他们是正确的，但是

const qs = Stream.iterate(2, x => x + 1).tookUntil(x => !(x < 2))[1] ;
console.log(qs.take(10)); // [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
console.log(qs.take(10)); // [13, 14, 15, 16, 17, 18, 19, 20, 21, 22] ？？？？

const ps = Stream.iterate(2, x => x + 1).dropUntil(x => !(x < 2)) ;
console.log(ps.take(10)); // [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
console.log(ps.take(10)); // [13, 14, 15, 16, 17, 18, 19, 20, 21, 22] ？？？？

// and ...

const fs = fibonacci.drop(10) ;
console.log(fs.take(6)); // [55, 89, 144, 233, 377, 610]
console.log(fs.take(6)); // [987, 1597, 2584, 4181, 6765, 10946] ！？！？
console.log(fs.take(6)); // [17711, 28657, 46368, 75025, 121393, 196418] ！？！？

是什么让他们与

xs

ys

zs

不同？

为什么

qs

方法只能改变

ps

fs

和

take

而不能改变

xs

ys

或

zs

？

它们都是以相同的形式创建的：

• dropUntil2

  回归：

  new Stream(( function* (this: Stream<T>): Generator<T> { ... } ).bind(this))

• （部分）

  tookUntil

  的回归：

  new Stream(( function* (this: Stream<T>): Generator<T> { ... } ).bind(this))

它们是相同的...所以，我无法理解原因...

我在 TS Playground (v5.1.6).

尝试了所有代码

PS。 我刚刚读过iterator helpers，所以我知道我的实现可能很丑陋......

Answer 1

您的代码的主要问题是您正在尝试重用迭代器。但迭代器是有状态的，一旦你调用

iterator.next()

，迭代器就会前进，你不一定能从同一个迭代器中获取较早的信息。因此，您永远不想使用现有迭代器创建新的

Stream

，也不允许

Stream

的任何方法使用现有迭代器。相反，您需要为每个操作生成一个新的迭代器。

由于你的

Stream

已经有一个生成器函数（

function*(⋯){⋯}

），你可以调用它来获取一个新的迭代器。这意味着当您创建一个新的

Stream

时，您应该创建一个新的生成器函数来配合它。

这是原始代码的精简版本，它为返回新

Stream

的方法执行此操作。例如，

dropUntil()

保留对原始生成器函数的引用，然后在新的生成器函数中调用它：

dropUntil(when: Fn<T, boolean>): Stream<T> {
    const gen = this.generatorFunction;
    return new Stream
        (function* (): Generator<T> {
            const iterator = gen();
            while (true) {
                const { value: head, done } = iterator.next();
                if (done) return;
                if (when(head)) {
                    yield head;
                    break;
                }
            }
            while (true) {
                const { value, done } = iterator.next();
                if (done) break;
                yield value;
            }
        });
};

并且

drop()

需要做类似的事情，以免持久化

count

变量的状态：

drop(limit: number): Stream<T> {
    const thiz = this;
    return new Stream(function* () {
        let count = 0;
        yield* thiz.dropUntil(() => !(count++ < limit));
    });
}

（使用

yield*

委托给

dropUtil

生成器。）

---

现在我们可以看到它按预期工作了：

const ps = Stream.iterate(2, x => x + 1).dropUntil(x => x > 5);
console.log(ps.take(10)); // [6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 
console.log(ps.take(10)); // [6, 7, 8, 9, 10, 11, 12, 13, 14, 15] 

const qs = Stream.iterate(2, x => x + 1).drop(7);
console.log(qs.take(10)); // [9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
console.log(qs.take(10)); // [9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
console.log(qs.take(10)); // [9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

const fibonacci = Stream.iterate([0, 1], ([a, b]) => [b, a + b]).map(([x]) => x);
const fs = fibonacci.drop(10);
console.log(fs.take(6)); // [55, 89, 144, 233, 377, 610]
console.log(fs.take(6)); // [55, 89, 144, 233, 377, 610] 
console.log(fs.take(6)); // [55, 89, 144, 233, 377, 610] 

---

请注意，此实现会多次执行所有计算，并且不会尝试缓存任何结果以供以后重用。您可以编写自己的可迭代包装器，它采用迭代器并将其元素缓存在数组中以供重播，但我认为这超出了所提出问题的范围。

Playground 代码链接