3

This question may apply to other languages but it is explicitly about JavaScript.

I've been trying to write a lazy evaluation implementation to filter through an array of elements. The filter process can be made up of 2 functions, F and G, that each check an element against some logic and return a Boolean that is used to determine whether or not the element will appear in the final resulting array.

This is what it would look like traditionally using the built-in methods.

const result = elements.filter(F).filter(G);

This is my first attempt at writing a lazy evaluation way of handling the same scenario WITHOUT returning intermittent arrays and calling the intermediate filter method:

for (let i = 0; i < elements.length; i++) {
    if (F(elements[i])) {
        if (G(elements[i])) {
            newArray.push(elements[i]);
        }
    }
}

Now I know my code is wonky and wrong because I've looked at other libraries that use iterators and generators. Why?

Why not use a for loop if the collection is an array? What makes it faster, if it is?

|improve this question
  • Your implementation isn't lazy. You eagerly consume the entire input collection and compute an entirely materialized result. – Servy Sep 30 '16 at 15:36
  • @Servy - I think I'm beginning to understand. What do you mean by consume the entire collection? How am I consuming the whole thing if I'm iterating one index at a time and only appending the elements that pass the if statements? – MSD Sep 30 '16 at 15:43
  • Because you finish iterating the entire collection before this method returns, rather than returning without having iterated the collection at all, and iterating the source collection as the results of the iterator you return are consumed. – Servy Sep 30 '16 at 15:47
  • @Servy - Thank you so much for your comments. You've done so much for helping me understand. Just to make sure I understand, within a for loop, any method I use will not return until I iterate over the entire collection? And not sure I grok this part of your response: "rather than returning without having iterated the collection at all, and iterating the source collection as the results of the iterator you return" If you provide an answer, I'll gladly accept it as the correct one. – MSD Sep 30 '16 at 15:58
  • Your particular for loop is going to iterate the entire sequence before returning, thus making it not lazy. That's not to say that a lazy implementation cannot possibly use a for loop. It can do whatever it wants, so long as it doesn't read in information from the source until that information is needed by the result. – Servy Sep 30 '16 at 16:00
1

You use Lazy Evaluation so that the program doesn't take the cost of the calculation, if it doesn't have to. The fastest possible calculation is the one that never executes.

You use an iterator/generator for the lazy evaluation, if the element in the set that you're after depends on the previous elements in the set. This allows you to get the next element in the set without re-calculating all of the previous elements.

For example:

function* fibonacci(){
  var fn1 = 0;
  var fn2 = 1;
  while (true){  
    var current = fn1;
    fn1 = fn2;
    fn2 = current + fn1;
    yield current;
  }
}

var f = fibonacci();
f.next().value;     // 0
f.next().value;     // 1
f.next().value;     // 1
f.next().value;     // 2
f.next().value;     // 3
f.next().value;     // 5
f.next().value;     // 8

To answer your question about why would you iterate over an array instead of using a for-loop, iterators are functionally composable; for-loops are not. Iterators and Generators are the programming language's way of passing a for-loop as a function.

As an example of functional composition, you could change your fibonacci function to accept a function as a filter. This would allow you to, for example, specify that the iterator return only those numbers in the sequence that were even (divisible by two).

|improve this answer
  • Are there any resources you could point me towards so that I may learn more about iterators and generators being functionally composable? – MSD Sep 30 '16 at 16:12
  • That does indeed seem difficult to Google. I have added a simple example. You might also try looking at Linq, which is lazily evaluated using iterators, and a detailed example of functional composition in use. Linq has a Javascript counterpart: linqjs.codeplex.com – Robert Harvey♦ Sep 30 '16 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.