是否可以在Java8中创建一个由递归定义的无限增长的惰性集合？

Question

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

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

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

因此，我需要一些可以通过索引来处理的构造。作为fibo(i)。

编辑。显然，解决方案不能是流，因为流不能使用两次。我不想在每次调用F(I)时重复所有的计算。

Answer 1

看来你是在要求这样的东西：

public class Fibonacci extends AbstractList<BigInteger> {
    @Override
    public Stream<BigInteger> stream() {
        return Stream.iterate(new BigInteger[]{ BigInteger.ONE, BigInteger.ONE },
           p->new BigInteger[]{ p[1], p[0].add(p[1]) }).map(p -> p[0]);
    }
    @Override
    public Iterator<BigInteger> iterator() {
        return stream().iterator();
    }
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
    @Override
    public BigInteger get(int index) {
        return stream().skip(index).findFirst().get();
    }
}

它可以通过list接口访问（它没有实现randomaccess有很好的原因），因此，您可以通过get(n)请求第n个值。注意，get的实现提示了如何在integer.max_value之后的位置获取值。只需使用stream().skip(position).findfirst().get()。

当心！这个列表是无限的，正如你所要求的。不要向它请求对所有元素都起作用的东西，例如，甚至不要向它请求toString()。但是像下面这样的事情会很顺利的工作：

System.out.println(new Fibonacci().subList(100, 120));

for(BigInteger value: new Fibonacci()) {
    System.out.println(value);
    if(someCondition()) break;
}   

public class Fibonacci extends AbstractList<BigInteger> {
    final Map<BigInteger,BigInteger> values=new HashMap<>();

    public Fibonacci() {
        values.put(BigInteger.ONE, BigInteger.ONE);
        values.put(BigInteger.ZERO, BigInteger.ONE);
    }

    @Override
    public BigInteger get(int index) {
        return get(BigInteger.valueOf(index));
    }
    public BigInteger get(BigInteger index) {
        return values.computeIfAbsent(index, ix ->
            get(ix=ix.subtract(BigInteger.ONE)).add(get(ix.subtract(BigInteger.ONE))));
    }

    @Override
    public Stream<BigInteger> stream() {
        return Stream.iterate(BigInteger.ZERO, i->i.add(BigInteger.ONE)).map(this::get);
    }
    @Override
    public Iterator<BigInteger> iterator() {
        return stream().iterator();
    }
    @Override
    public int size() {
        return Integer.MAX_VALUE;
    }
}

我在这里使用biginteger作为键/索引来满足（理论上）无限的要求，尽管我们也可以使用long键用于所有实际用途。关键是最初的空存储：（现在示例性地使用long):

final Map<Long,BigInteger> values=new HashMap<>();

它使用应结束每个递归的值预先初始化（除非由于已计算的值而提前结束）：

values.put(1L, BigInteger.ONE);
values.put(0L, BigInteger.ONE);

然后，我们可以通过以下方式请求一个懒散计算的值：

public BigInteger get(long index) {
    return values.computeIfAbsent(index, ix -> get(ix-1).add(get(ix-2)));
}

LongStream.range(0, Long.MAX_VALUE).mapToObj(this::get);

这创建了一个流，它只是“实际上是无限的”，而上面使用biginteger的完整示例类理论上是无限的…

映射将记住序列的每个计算值。