Functional programming: Self-referencing list in Java (Fibonacci)

Question

While implementing a self-referencing lazy-list version to calculate fibonacci numbers in Java, I came across this:

LazyList<Long> fibs = new LazyList<>(0L,
    () -> new LazyList<>(1L,
        () -> fibs.zip(fibs.getTail()).map(p -> p.getA() + p.getB()) 
    )
);

See https://gist.github.com/lenalebt/e627e13d034011ac156d44917fe466d3 for the complete code. The lazy list is calculating values on demand and caches them for later re-use.

It complains in the second lambda about "fibs might not have been initialized". While I think I understand why it complains and have a workaround (in the gist, using a setter for the tail), I am looking for a solution that

works with an immutable interface to the outside world (so no setters on LazyList!)
does not completely change the idea of that lazy list (which effectively is a Stream from Scala)

I know e.g. https://dzone.com/articles/do-it-java-8-recursive-and (last approach). While this works nicely, I wanted to formulate an example for lazy evaluation with memoization and self-reference, which the Java-Stream solution presented there is not.

I was trying to port this example from Scala to Java: http://derekwyatt.org/2011/07/29/understanding-scala-streams-through-fibonacci/

A Scala Fibonacci Stream (lazy). Calculated values are cached (memoized) for future reference : val fibs: Stream[Long] = 0 #:: fibs.scan(1L)(_+_) Change the val to a def to turn off memoization. — jwvh
@Oleg right :). I added a little more precision there, I wanted that self-reference and memoization. — lena_punkt

Hannes Tenter Hannes Tenter · Accepted Answer · 2017-10-24T14:25:04

I'm a colleague of the thread creator - we already talked about the problem.

The JVM cannot pass an uninitialized reference into the lambda. The reference is not initialized because the constructor call can fail - same as with a method call. Scala allows this scenario, because there are ynthetic classed generated that implement the "property" fibs instead of a variable. Nice finding: Some old Scala compilers don't allow this scenario either and state something like "illegal forward reference" (old bugs). With Java, one would work around with a property-like intermediate class or a factory method, that does the same as the Scala compiler - just more ugly :)

Functional programming: Self-referencing list in Java (Fibonacci)

1 Answers