是否有可能在Java 8中创建由递归定义的惰性（更好的无限）集合？

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

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

但是那样它就行不通了 – 我无法通过索引从流中获取一个项目。另一个问题是，如果我以后再沿着流，它将被消耗，我不能重复使用它。 如果我将流复制到List，它就不再是懒惰了。

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

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

Answer 1

看来你要求这样的东西：

 public class Fibonacci extends AbstractList { @Override public Stream 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 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; } 

但是，当您必须处理大量元素并希望有效地执行它时，您应该确保处理迭代器或流以避免重复get调用的O(n²)复杂性。

请注意，我将元素类型更改为BigInteger因为在涉及Fibonacci序列和int或long值类型时考虑无限流是没有意义的。 即使使用long值类型，序列仅在92个值之后结束，然后发生溢出。

---

更新：既然您已经明确表示要查找惰性存储 ，则可以按如下方式更改上面的类：

 public class Fibonacci extends AbstractList { final Map 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 stream() { return Stream.iterate(BigInteger.ZERO, i->i.add(BigInteger.ONE)).map(this::get); } @Override public Iterator iterator() { return stream().iterator(); } @Override public int size() { return Integer.MAX_VALUE; } } 

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

 final Map 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))); } 

或者委托给上述get方法的流：

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

这创建了一个只有“几乎无限”的流，而上面的完整示例类，使用BigInteger理论上是无限的……

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

Answer 2

我无法想出一个好的通用解决方案，但是如果你想特别访问前两个元素，可以通过非常简单的方式完成定义自定义Spliterator如下所示：

 public static IntStream iterate(int first, int second, IntBinaryOperator generator) { Spliterator.OfInt spliterator = new AbstractIntSpliterator(Long.MAX_VALUE, Spliterator.ORDERED) { int prev1 = first, prev2 = second; int pos = 0; @Override public boolean tryAdvance(IntConsumer action) { if(pos < 2) { action.accept(++pos == 1 ? prev1 : prev2); } else { int next = generator.applyAsInt(prev1, prev2); prev1 = prev2; prev2 = next; action.accept(next); } return true; } }; return StreamSupport.intStream(spliterator, false); } 

用法：

 iterate(1, 1, Integer::sum).limit(20).forEach(System.out::println); 

Answer 3

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

这类类的对象的声明看起来如此：

  FunctionalSequence 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 implements Iterable{ LinkedList> realList = new LinkedList<>(); StackOverflowingFunction calculate = null; public FunctionalSequence initialize(Stream start){ start.forEachOrdered((T value) -> { realList.add(new CountedFlighweight<>()); realList.getLast().set(value); }); return this; } public FunctionalSequence setSequenceFunction(StackOverflowingFunction calculate){ this.calculate = calculate; return this; } @Override public Iterator iterator() { return new SequenceIterator(); } public T get(int currentIndex) throws StackOverflowError{ if(currentIndex < 0) return null; while (currentIndex >= realList.size()){ realList.add(new CountedFlighweight()); } try { return (T) realList.get(currentIndex).get(calculate, currentIndex); } catch (Exception e) { return null; } } public class SequenceIterator implements Iterator{ int currentIndex; @Override public boolean hasNext() { return true; } @Override public T next() { T result = null; if (currentIndex == realList.size()){ realList.add(new CountedFlighweight()); } // 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  */ public class CountedFlighweight{ 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 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  { public U apply(K index) throws StackOverflowError; } } 

由于递归函数可以轻松地满足StackOverflowError，我们应该组织递归，以便在这种情况下整个递归序列将回滚而不会真正满足任何更改并抛出exception。

FunctionalSequence的使用看起来如此：

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

或者：

 static private void tryFibo(FunctionalSequence 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）变得可达。 我们做到了！