title: Lazy, but persisted, evaluation of java 8 lambda
body: <p>I am currently working on creating my own persistent array in java, which uses a binary search tree to store an collection of values.</p>
  
  <p>I want to add a map method that takes a <code>Function</code> as an argument to generate a new array. I don't want to evaluate the functions unless the particular value is requested. This is pretty simple to do as lambdas are lazy evaluated. However, I also only want a function to be evaluated only once, even if the result is requested multiple times. </p>
  
  <p>I could create a node that stores the supplier and updates the result when evaluated:</p>
  
  <pre><code>class Node&lt;T&gt; {
  
      private T value;
      private Supplier&lt;T&gt; supplier;
  
      public T get() {
          if (null != value)
              return value;
          value = supplier.get();
          return value;
      }
  }
  </code></pre>
  
  <p>...where <code>supplier</code> is derived from a <code>Function</code> being applied to a value in an older version of the persisted array.</p>
  
  <p>However, this is no longer a functional approach, and has the potential to cause errors in a multi-threaded system*. It also doesn't yield an advantage in the case where supplier returns a null value**.</p>
  
  <p>Another approach would be return an instance of <code>Node</code> on a get call:</p>
  
  <pre><code>class Node&lt;T&gt; {
  
      private final Optional&lt;T&gt; value;
      private final Supplier&lt;T&gt; supplier;
  
      Node(Supplier&lt;T&gt; supplier, T value) {
          this.supplier = supplier;
          this.value = Optional.ofNullable(value);
      }
  
      public Tuple&lt;Node&lt;T&gt;, T&gt; get() {
          if (null != value)
              return new Tuple&lt;&gt;(this, value.orElse(null));
          T result = supplier.get();
          Node&lt;T&gt; newNode = new Node&lt;&gt;(null, result);
          return new Tuple&lt;&gt;(newNode, result);
      }
  }
  </code></pre>
  
  <p>I like this approach for staying functional; but it would require a lot of overhead in all the parent nodes going up the tree for just a get call. And it would require cumbersome unboxing in the using application's code.</p>
  
  <p>Does anyone have another approach they can think of to make this work the way I'm asking? Thanks.</p>
  
  <p>*This could be solved using locking mechanisms, but adds a layer of complexity I'm hoping to avoid.</p>
  
  <p>**I've thought about making <code>value</code> an <code>Optional&lt;T&gt;</code>, where <code>null</code> means hasn't been evaluate, and <code>Optional.empty()</code> as has been evaluated and returns a null. However, this works around my issue, rather than solving it.</p>
  
  <p>For anyone not familiar with a persisted array, it's a data structure that creates a new instance of itself whenever an update is performed. This allows it to be purely immutable. Using a binary tree (or more common 32-bit tree) method allows the updates to reduce duplicating data, both in speed and memory.</p>
  
  <p>EDIT:</p>
  
  <p>The code for the collection can be found on <a href="https://github.com/coopstools/statedfp/tree/master/src/main/java/com/coopstools/statedfp/struct" rel="nofollow noreferrer">github</a>. For description of use, you can look in the test folder.</p>