title: Do Immutable.js or Lazy.js perform short-cut fusion?
body: <p>First, let me define what is <a href="https://www.haskell.org/haskellwiki/Short_cut_fusion" rel="noreferrer">short-cut fusion</a> for those of you who don't know. Consider the following array transformation in JavaScript:</p>
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>var a = [1,2,3,4,5].map(square).map(increment);
  
  console.log(a);
  
  function square(x) {
      return x * x;
  }
  
  function increment(x) {
      return x + 1;
  }</code></pre>
  </div>
  </div>
  </p>
  <p>Here we have an array, <code>[1,2,3,4,5]</code>, whose elements are first squared, <code>[1,4,9,16,25]</code>, and then incremented <code>[2,5,10,17,26]</code>. Hence, although we don't need the intermediate array <code>[1,4,9,16,25]</code>, we still create it.</p>
  <p>Short-cut fusion is an optimization technique which can get rid of intermediate data structures by merging some functions calls into one. For example, short-cut fusion can be applied to the above code to produce:</p>
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>var a = [1,2,3,4,5].map(compose(square, increment));
  
  console.log(a);
  
  function square(x) {
      return x * x;
  }
  
  function increment(x) {
      return x + 1;
  }
  
  function compose(g, f) {
      return function (x) {
          return f(g(x));
      };
  }</code></pre>
  </div>
  </div>
  </p>
  <p>As you can see, the two separate <code>map</code> calls have been fused into a single <code>map</code> call by composing the <code>square</code> and <code>increment</code> functions. Hence the intermediate array is not created.</p>
  <hr />
  <p>Now, I understand that libraries like <a href="https://github.com/facebook/immutable-js" rel="noreferrer">Immutable.js</a> and <a href="http://philosopherdeveloper.com/posts/introducing-lazy-js.html" rel="noreferrer">Lazy.js</a> emulate lazy evaluation in JavaScript. Lazy evaluation means that results are only computed when required.</p>
  <p>For example, consider the above code. Although we <code>square</code> and <code>increment</code> each element of the array, yet we may not need all the results.</p>
  <p>Suppose we only want the first 3 results. Using Immutable.js or Lazy.js we can get the first 3 results, <code>[2,5,10]</code>, without calculating the last 2 results, <code>[17,26]</code>, because they are not needed.</p>
  <p>However, lazy evaluation just delays the calculation of results until required. It does not remove intermediate data structures by fusing functions.</p>
  <p>To make this point clear, consider the following code which emulates lazy evaluation:</p>
  <p><div class="snippet" data-lang="js" data-hide="true" data-console="true" data-babel="false">
  <div class="snippet-code snippet-currently-hidden">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>var List = defclass({
      constructor: function (head, tail) {
          if (typeof head !== "function" || head.length &gt; 0)
              Object.defineProperty(this, "head", { value: head });
          else Object.defineProperty(this, "head", { get: head });
  
          if (typeof tail !== "function" || tail.length &gt; 0)
              Object.defineProperty(this, "tail", { value: tail });
          else Object.defineProperty(this, "tail", { get: tail });
      },
      map: function (f) {
          var l = this;
  
          if (l === nil) return nil;
  
          return cons(function () {
              return f(l.head);
          }, function () {
              return l.tail.map(f);
          });
      },
      take: function (n) {
          var l = this;
  
          if (l === nil || n === 0) return nil;
  
          return cons(function () {
              return l.head;
          }, function () {
              return l.tail.take(n - 1);
          });
      },
      mapSeq: function (f) {
          var l = this;
          if (l === nil) return nil;
          return cons(f(l.head), l.tail.mapSeq(f));
      }
  });
  
  var nil = Object.create(List.prototype);
  
  list([1,2,3,4,5])
      .map(trace(square))
      .map(trace(increment))
      .take(3)
      .mapSeq(log);
  
  function cons(head, tail) {
      return new List(head, tail);
  }
  
  function list(a) {
      return toList(a, a.length, 0);
  }
  
  function toList(a, length, i) {
      if (i &gt;= length) return nil;
  
      return cons(a[i], function () {
          return toList(a, length, i + 1);
      });
  }
  
  function square(x) {
      return x * x;
  }
  
  function increment(x) {
      return x + 1;
  }
  
  function log(a) {
      console.log(a);
  }
  
  function trace(f) {
      return function () {
          var result = f.apply(this, arguments);
          console.log(f.name, JSON.stringify([...arguments]), result);
          return result;
      };
  }
  
  function defclass(prototype) {
      var constructor = prototype.constructor;
      constructor.prototype = prototype;
      return constructor;
  }</code></pre>
  </div>
  </div>
  </p>
  <p>As you can see, the function calls are interleaved and only the first three elements of the array are processed, proving that the results are indeed computed lazily:</p>
  <pre><code>square [1] 1
  increment [1] 2
  2
  square [2] 4
  increment [4] 5
  5
  square [3] 9
  increment [9] 10
  10
  </code></pre>
  <p>If lazy evaluation is not used then the result would be:</p>
  <pre><code>square [1] 1
  square [2] 4
  square [3] 9
  square [4] 16
  square [5] 25
  increment [1] 2
  increment [4] 5
  increment [9] 10
  increment [16] 17
  increment [25] 26
  2
  5
  10
  </code></pre>
  <p>However, if you see the source code then each function <code>list</code>, <code>map</code>, <code>take</code> and <code>mapSeq</code> returns an intermediate <code>List</code> data structure. No short-cut fusion is performed.</p>
  <hr />
  <p>This brings me to my main question: do libraries like Immutable.js and Lazy.js perform short-cut fusion?</p>
  <p>The reason I ask is because according to the documentation, they “apparently” do. However, I am skeptical. I have my doubts whether they actually perform short-cut fusion.</p>
  <p>For example, this is taken from the <a href="https://github.com/facebook/immutable-js/blob/master/README.md" rel="noreferrer">README.md</a> file of Immutable.js:</p>
  <blockquote>
  <p><code>Immutable</code> also provides a lazy <code>Seq</code>, allowing efficient chaining of collection methods like <code>map</code> and <code>filter</code> without creating intermediate representations. Create some <code>Seq</code> with <code>Range</code> and <code>Repeat</code>.</p>
  </blockquote>
  <p>So the developers of Immutable.js claim that their <code>Seq</code> data structure allows efficient chaining of collection methods like <code>map</code> and <code>filter</code> <strong>without creating intermediate representations</strong> (i.e. they perform short-cut fusion).</p>
  <p>However, I don't see them doing so in their <a href="https://github.com/facebook/immutable-js/blob/master/src/Seq.js" rel="noreferrer">code</a> anywhere. Perhaps I can't find it because they are using ES6 and my eyes aren't all too familiar with ES6 syntax.</p>
  <p>Furthermore, in their documentation for <a href="https://github.com/facebook/immutable-js/blob/master/README.md#lazy-seq" rel="noreferrer">Lazy Seq</a> they mention:</p>
  <blockquote>
  <p><code>Seq</code> describes a lazy operation, allowing them to efficiently chain use of all the Iterable methods (such as <code>map</code> and <code>filter</code>).</p>
  <p><strong>Seq is immutable</strong> — Once a Seq is created, it cannot be changed, appended to, rearranged or otherwise modified. Instead, any mutative method called on a Seq will return a new Seq.</p>
  <p><strong>Seq is lazy</strong> — Seq does as little work as necessary to respond to any method call.</p>
  </blockquote>
  <p>So it is established that <code>Seq</code> is indeed lazy. However, there are no examples to show that <em>intermediate representations are indeed not created</em> (which they claim to be doing).</p>
  <hr />
  <p>Moving on to Lazy.js we have the same situation. Thankfully, Daniel Tao wrote a <a href="http://philosopherdeveloper.com/posts/introducing-lazy-js.html" rel="noreferrer">blog post</a> on how Lazy.js works, in which he mentions that at its heart Lazy.js simply does function composition. He gives the following example:</p>
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>Lazy.range(1, 1000)
      .map(square)
      .filter(multipleOf3)
      .take(10)
      .each(log);
  
  function square(x) {
      return x * x;
  }
  
  function multipleOf3(x) {
      return x % 3 === 0;
  }
  
  function log(a) {
      console.log(a);
  }</code></pre>
  <pre class="snippet-code-html lang-html prettyprint-override"><code>&lt;script src="https://rawgit.com/dtao/lazy.js/master/lazy.min.js"&gt;&lt;/script&gt;</code></pre>
  </div>
  </div>
  </p>
  <p>Here the <code>map</code>, <code>filter</code> and <code>take</code> functions produce intermediate <code>MappedSequence</code>, <code>FilteredSequence</code> and <code>TakeSequence</code> objects. These <code>Sequence</code> objects are essentially iterators, which eliminate the need of intermediate arrays.</p>
  <p>However, from what I understand, there is still no short-cut fusion taking place. The intermediate array structures are simply replaced with intermediate <code>Sequence</code> structures which are not fused.</p>
  <p>I could be wrong, but I believe that expressions like <code>Lazy(array).map(f).map(g)</code> produce two separate <code>MappedSequence</code> objects in which the first <code>MappedSequence</code> object feeds its values to the second one, instead of the second one replacing the first one by doing the job of both (via function composition).</p>
  <p><strong>TLDR:</strong> Do Immutable.js and Lazy.js indeed perform short-cut fusion? As far as I know they get rid of intermediate arrays by emulating lazy evaluation via sequence objects (i.e. iterators). However, I believe that these iterators are chained: one iterator feeding its values lazily to the next. They are not merged into a single iterator. Hence they do not “eliminate intermediate representations“. They only transform arrays into constant space sequence objects.</p>