I can create a recursive closure:
static IntUnaryOperator fibo;
fibo =
(i) ->
i<2 ? 1 : fibo.applyAsInt(i-1)+ fibo.applyAsInt(i-2);
But of course, it has sense only as an example. To be useful, such collection should keep already once counted elements and get() them without recounting. The counting of elements should happen in lazy way, at first need. Thus, no member will have to be calculated more than once. In such way we'll a structure that will look like a recursively defined sequence, and will be fast and reusable.
When I started to study Java 8 I thought that Stream works in that way. But it does not, for the stream cannot be used twice.
I thought about the following construction:
IntStream fi;
fi=IntStream.iterate(0, i -> fi[i-1]+fi[i-2]);
But that way it won't work - I can't get an item from the stream by index.The other problem is that if I'll later go along the stream, it will be consumed and I can't use it repeatedly. If I copy the stream to List, it is not lazy anymore.
As a result, I need some construction that I can address by index. As fibo(i)
.
Edit. Obviously, the solution cannot be a stream, for the stream cannot be used twice. I don't want to repeat all calculations on every call to F(i).
The solution will be created as a class
FunctionalSequence
for representation of a lazy, infinite sequence of objects, defined by a lambda function with integer argument. The function can be iterative or not. For the iterative case theFunctionalSequence
class will have a methodinitialize
for setting the start values.The declaration of an object of such class will look so:
Notice, as in the recursive lambda example in the question, we cannot declare the object and define it recursively in one operator. One operator for declaration, another for definition.
The
FunctionalSequence
class definition:As the recursive function could easily meet the StackOverflowError, we should organize the recursion so that in that case the whole recursive sequence will roll back without any changes really met and throw the exception.
The use of the FunctionalSequence could look so:
Or so:
The last function can be used in the following way:
Here are the results (the stack was limited to 256K for the needs of testing):
Look, the repeatable call of the f(i) for the same index takes practically no time - no iterations were made. We cannot reach f(1100) at once because of the StackOverflowError. But after we have reached once f(200), f(1100) becomes reachable. We made it!
It seems you are asking for something like this:
It’s accessible via the
List
interface (it doesn’t implementRandomAccess
for a good reason), thus, you may ask for the n’th value viaget(n)
. Note that the implementation ofget
hints how you can get values at positions afterInteger.MAX_VALUE
. Just usestream().skip(position).findFirst().get()
.Beware! This list is infinite, as you asked for. Don’t ask it for things that operate on all elements, e.g. not even
toString()
. But things like the following will work smoothly:or
However, when you have to process large sequences of elements and want to do it efficiently, you should ensure to work on the iterator or stream to avoid
O(n²)
complexity of repeatedget
calls.Note that I changed the element type to
BigInteger
as it would be pointless to think about infinite streams when it comes to the Fibonacci sequence and theint
orlong
value type. Even with thelong
value type, the sequence is over after only 92 values as then, overflow occurs.Update: now that you made clear that you are looking for a lazy storage, you may change the class above as follows:
I used
BigInteger
as key/index here to fulfill the requirement to be (theoretically) infinite, though we can use along
key as well for all practical uses. The key point is the initially empty storage: (now exemplary usinglong
):which is pre-initialized with the values that should end each recursion (unless it ends earlier due to already computed values):
Then, we can ask for a lazily computed value via:
or a stream delegating to the
get
method described above:This creates a stream that is only “practically infinite” whereas the complete example class above, using
BigInteger
is theoretically infinite…The
Map
will remember every computed value of the sequence.I cannot think up a good general solution, but if you want to access specifically two previous elements, this could be done in quite easy way defining the custom
Spliterator
like this:Usage: