Infinite Fibonacci Sequence with Memoized in Java 8

Question

Firstly, I'm a JavaScript programmer, and fairly new to Java8 and trying the new functional feature.

Since I expertise JS coding, I implemented my own JS lazy-functional library for proof of concept.

Using the library, I could write Infinite sequence of Natural numbers and Fibonacci as 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 enough. The point is that I can define Natural/Fibonacci infinite sequence as the math definition as it is, then later compute the required part of the infinite sequence with lazy-evaluation.

So, now I wonder if I can do the same manner with Java8.

For natural sequence, I had post another Question here.

Infinite sequence of Natural numbers with Java8 generator

One of the way to define Natural sequence is to use iterator of Java8:

Java8

IntStream natural = IntStream.iterate(0, i -> i + 1);

natural
 .limit(10)
 .forEach(System.out::println);

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

However, I wonder if it's 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 this looks more concise. Unfortunately, the answers suggest it's probably not possible even we use generate.

In addition, IntStream.iterate does not fit for Fibonacci sequence.

I seek web to generate indefinite sequence of Fibonacci, 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 infinite sequence (lazy Stream in Java8).

and

Providing Limit condition on 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 could say it's defined as Math. However I do not like this implementation because, as you can see, there are many internal valuable to obtain the sequence such as n1 n2 n3 then fibonacci, accordingly the code structure is complicated and you need to control mutable state which is anti-functional manner - unlike the math definition, and probably this is not memoized.

So, here's my question. With Java8 Stream, is there any way to write a code to define the infinite sequence of fibonacci in concise math 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.

This other article [Java Infinite Streams](http://www.ticocoding.com/java-infinite-streams/) provides a conceptual explanation of streams and the last example demonstrates an infinite stream of fibonacci numbers, although it does not use Java 8 streams. — Edwin Dalorzo, Dec 18 '14 at 18:22

score 16 · Accepted Answer · answered Oct 09 '14 at 23:39

16

You can take your map-based memoized fibonacci(x) and make an infinite stream out of it like this:

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

But the easiest way to make an infinite stream of fibonacci numbers is like this:

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

As the article you linked to points out, "infinite" really means "until long overflows" which happens quickly. If you want to generate hundreds of fibonacci numbers, replace long with 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]);

answered Oct 09 '14 at 23:39

Misha

27,433
6
62
78

Great.Although the style presentation of the function in Java8 still confuses me, I could fairly confirm it corresponds the math definition. Perhaps I would post another question. What is `map` or `mapToLong` (f -> f[0]), I know what the `map` is, but I could not follow the logical role here. Also the `map` has automatic memorisation functionality? – Oct 10 '14 at 01:34
I post another Q for this issue: http://stackoverflow.com/questions/26290716/map-based-memoized-in-java8 – Oct 10 '14 at 01:52
You may want to study [this related question and its answers](http://stackoverflow.com/q/25880331/2711488)… – Holger Oct 10 '14 at 07:56
please explain flow of this answer and parameter given LongStream fibs = Stream.iterate( new long[]{1, 1}, f -> new long[]{f[1], f[0] + f[1]} ).mapToLong(f -> f[0]); – Akash kumar Mar 29 '18 at 20:43

Infinite Fibonacci Sequence with Memoized in Java 8

1 Answers1

Linked