是否可以在Java 8中创建由递归定义的无限增长的惰性方式集合？

Question

我可以创建一个递归闭包：

static IntUnaryOperator fibo;
fibo = 
    (i) -> 
    i<2 ? 1 : fibo.applyAsInt(i-1)+ fibo.applyAsInt(i-2);

但是，当然，它仅作为示例具有意义。为了有用，此类集合应该保留已经计数过的元素，并对其进行get（）而不重新计数。首先，元素的计数应以惰性方式进行。因此，无需再计算一次成员。这样，我们将得到一个看起来像递归定义序列的结构，并且该结构将是快速且可重用的。

当我开始学习Java 8时，我认为Stream可以这样工作。但事实并非如此，因为流不能被使用两次。

我考虑了以下构造：

IntStream fi;
fi=IntStream.iterate(0, i -> fi[i-1]+fi[i-2]);

但是那样就行不通了-我无法按索引从流中获取项目。另一个问题是，如果以后再浏览该流，它将被消耗并且无法重复使用。如果我将流复制到列表，它不再是惰性的。

结果，我需要一些可以按索引处理的构造。作为fibo(i)。

编辑。显然，html" target="_blank">解决方案不能是流，因为该流不能使用两次。我不想在每次调用F（i）时重复所有计算。

Answer 1

该解决方案将被创建为一个类，FunctionalSequence用于表示对象的惰性，无限序列，该对象序列由带整数参数的lambda函数定义。该函数可以迭代，也可以不迭代。对于迭代情况，FunctionalSequence该类将具有一种initialize用于设置起始值的方法。

这样的类的对象的声明将如下所示：

    FunctionalSequence<BigInteger> fiboSequence =  new FunctionalSequence<>();
    fiboSequence.
        initialize(Stream.of(BigInteger.ONE,BigInteger.ONE)).
        setSequenceFunction(
            (i) ->
            fiboSequence.get(i-2).add(fiboSequence.get(i-1))
        );

注意，就像问题中的递归lambda示例一样，我们无法声明该对象并在一个运算符中递归定义它。一个运算符用于声明，另一个运算符用于定义。

在FunctionalSequence类的定义：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.stream.Stream;

public class FunctionalSequence<T> implements Iterable<T>{
    LinkedList<CountedFlighweight<T>> realList = new LinkedList<>();
    StackOverflowingFunction<Integer, T> calculate = null;
    public FunctionalSequence<T> initialize(Stream<T> start){
        start.forEachOrdered((T value) ->
        {
                realList.add(new CountedFlighweight<>());
                realList.getLast().set(value);
        });
        return this;
    }
    public FunctionalSequence<T>  setSequenceFunction(StackOverflowingFunction<Integer, T> calculate){
        this.calculate = calculate;
        return this;
    }

    @Override
    public Iterator<T> iterator() {
        return new SequenceIterator();
    }
    public T get(int currentIndex) throws StackOverflowError{
        if(currentIndex < 0) return null;
        while (currentIndex >= realList.size()){
            realList.add(new CountedFlighweight<T>());
        }
        try {
            return (T) realList.get(currentIndex).get(calculate, currentIndex);
        } catch (Exception e) {
            return null;
        }
    }
    public class SequenceIterator implements Iterator<T>{
        int currentIndex;
        @Override
        public boolean hasNext() {
            return true;
        }

        @Override
        public T next() {
            T result = null;
            if (currentIndex == realList.size()){
                realList.add(new CountedFlighweight<T>());
            }
            // here the StackOverflowError catching is a pure formality, by next() we would never cause StackOverflow
            try {
                result = realList.get(currentIndex).get(calculate, currentIndex);
            } catch (StackOverflowError e) {
            }
            currentIndex++;
            return result;
        }

    }
    /**
     * if known is false, the value of reference is irrelevant
     * if known is true, and reference is not null, reference contains the data
     * if known is true, and reference is null, that means, that the appropriate data are corrupted in any way
     * calculation on corrupted data should result in corrupted data.
     * @author Pet
     *
     * @param <U>
     */
    public class CountedFlighweight<U>{
        private boolean known = false;
        private U reference;
        /**
         * used for initial values setting 
         */
        private void set(U value){
            reference = value;
            known = true;
        }
        /**
         * used for data retrieval or function counting and data saving if necessary
         * @param calculate
         * @param index
         * @return
         * @throws Exception
         */
        public U get(StackOverflowingFunction<Integer, U> calculate, int index) throws StackOverflowError{
            if (! known){
                if(calculate == null) {
                    reference = null;
                } else {
                    try {
                        reference = calculate.apply(index);
                    } catch (Exception e) {
                        reference = null;
                    }
                }
            }
            known = true;
            return reference;
        }
    }

    @FunctionalInterface
    public interface StackOverflowingFunction <K, U> {
        public U apply(K index) throws StackOverflowError;

    }
}

由于递归函数很容易遇到StackOverflowError，因此我们应该组织递归，以便在这种情况下，整个递归序列将回滚而不会真正满足任何更改，并引发异常。

FunctionalSequence的用法如下所示：

    // by iterator:
    int index=0;
    Iterator<BigInteger> iterator = fiboSequence.iterator(); 
    while(index++<10){
        System.out.println(iterator.next());
    }

或者：

static private void tryFibo(FunctionalSequence<BigInteger> fiboSequence, int i){
    long startTime = System.nanoTime();
    long endTime;
    try {
        fiboSequence.get(i);
        endTime = System.nanoTime();
        System.out.println("repeated timing for f("+i+")=" + (endTime-startTime)/1000000.+" ns");
    } catch (StackOverflowError e) {
        endTime = System.nanoTime();
        //e.printStackTrace();
        System.out.println("failed counting f("+i+"), time=" + (endTime-startTime)/1000000.+" ns");
    }       
}

可以按以下方式使用最后一个功能：

    tryFibo(fiboSequence, 1100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 200);
    tryFibo(fiboSequence, 1100);
    tryFibo(fiboSequence, 2100);
    tryFibo(fiboSequence, 2100);
    tryFibo(fiboSequence, 1100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 100);
    tryFibo(fiboSequence, 200);
    tryFibo(fiboSequence, 1100);

结果如下（出于测试需要，堆栈限制为256K）：

1
1
2
3
5
8
13
21
34
55
failed counting f(1100), time=3.555689 ns
repeated timing for f(100)=0.213156 ns
repeated timing for f(100)=0.002444 ns
repeated timing for f(200)=0.266933 ns
repeated timing for f(1100)=5.457956 ns
repeated timing for f(2100)=3.016445 ns
repeated timing for f(2100)=0.001467 ns
repeated timing for f(1100)=0.005378 ns
repeated timing for f(100)=0.002934 ns
repeated timing for f(100)=0.002445 ns
repeated timing for f(200)=0.002445 ns
repeated timing for f(1100)=0.003911 ns

看，对相同索引重复调用f（i）几乎不需要时间-
无需进行迭代。由于StackOverflowError，我们无法一次达到f（1100）。但是一旦我们达到f（200），f（1100）就可以达到了。我们做到了！