Infinite Fibonacci sequence with memorized in Java 8

Question

Firstly, I am a JavaScript programmer and quite new to Java8 and trying a new functional function.

Since I learned JS coding, I have implemented my own JS lazy-functional library to validate the concept.

https://github.com/kenokabe/spacetime

Using the library, I could write an Infinite sequence of natural numbers and Fibonacci , as shown below:

Javascript

var spacetime = require('./spacetime'); var _ = spacetime.lazy(); var natural = _(function(n) //memoized automatically { return n; // Natural numbers is defined as the `n`th number becomes `n` }); var natural10 = _(natural) .take(10) .compute(function(x) { console.log(x); }); //wrap a recursive function to memoize // must be at the definition in the same scope var fib = _(function(n) { if (n <= 1) return 1; // as the Fib definition in Math else return fib(n - 2) + fib(n - 1); // as the Fib definition in Math }); var fib10 = _(fib) .take(10) .compute(function(x) { console.log(x); }); 

Clear. The thing is, I can define an infinite Natural / Fibonacci sequence as a definition of mathematics as it is, and then calculate the required part of an infinite sequence with a lazy estimate.

So now I am wondering if I can do the same with Java8.

For natural consistency, I posed another question here.

Endless sequence of natural numbers with Java8 generator

One way to determine the natural sequence is to use the iterator for Java8:

Java8

 IntStream natural = IntStream.iterate(0, i -> i + 1); natural .limit(10) .forEach(System.out::println); 

I am observing IntStream natural = IntStream.iterate(0, i -> i + 1); is a fair definition of natural numbers in a mathematical sense.

However, I wonder if it is possible to define it as I did before, that is

Javascript

 var natural = _(function(n) //memoized automatically { return n; // Natural numbers is defined as the `n`th number becomes `n` }); 

because it looks more concise. Unfortunately, the answers show that this is probably not possible even when using generate .

Also, IntStream.iterate not suitable for a Fibonacci sequence.

I am looking for a network to generate an indefinite Fibonacci sequence, the best results I found are

http://blog.informatech.cr/2013/05/08/memoized-fibonacci-numbers-with-java-8/

Java8

 private static Map<Integer,Long> memo = new HashMap<>(); static { memo.put(0,0L); //fibonacci(0) memo.put(1,1L); //fibonacci(1) } //And for the inductive step all we have to do is redefine our Fibonacci function as follows: public static long fibonacci(int x) { return memo.computeIfAbsent(x, n -> fibonacci(n-1) + fibonacci(n-2)); } 

This is not an endless sequence (lazy Stream in Java8).

and

Providing a limit condition for stream generation

Java8

 Stream.generate(new Supplier<Long>() { private long n1 = 1; private long n2 = 2; @Override public Long get() { long fibonacci = n1; long n3 = n2 + n1; n1 = n2; n2 = n3; return fibonacci; } }).limit(50).forEach(System.out::println); 

This is an infinite sequence (lazy Stream in Java8), and you can say that it is defined as math. However, I do not like this implementation, because, as you can see, there are many internal prices to get a sequence, such as n1 n2 n3 , then fibonacci , respectively, the code structure is complex and you need to manage a volatile state, which is an anti-functional way , unlike the definition of mathematics, and probably it is not memoized.

So here is my question. With Java8 Stream there a way to write code to define an infinite Fibonacci sequence in a concise mathematical manner with memoization like

Javascript

  var fib = _(function(n) { if (n <= 1) return 1; // as the Fib definition in Math else return fib(n - 2) + fib(n - 1); // as the Fib definition in Math }); 

Thanks for your thought.

Answer 1

You can take your memoized fibonacci (x) based on the map and make an endless stream from it as follows:

 LongStream fibs = IntStream.iterate(1, i->i+1).mapToLong(i -> fibonacci(i)); 

But the easiest way to make an endless stream of Fibonacci numbers is this:

 LongStream fibs = Stream.iterate( new long[]{1, 1}, f -> new long[]{f[1], f[0] + f[1]} ).mapToLong(f -> f[0]); 

The article you pointed out states that “infinite” really means “longer than overflow”, which happens quickly. If you want to generate hundreds of fibonacci numbers, replace them with a long BigInteger:

  Stream<BigInteger> bigFibs = Stream.iterate( new BigInteger[]{BigInteger.ONE, BigInteger.ONE}, f -> new BigInteger[]{f[1], f[0].add(f[1])} ).map(f -> f[0]);