Are generator functions valid in functional programming?

Question

The questions are:

Do generators break the functional programming paradigm? Why or why not?
If yes, can generators be used in functional programming and how?

Consider the following:

function * downCounter(maxValue) {
  yield maxValue;
  yield * downCounter(maxValue > 0 ? maxValue - 1 : 0);
}

let counter = downCounter(26);
counter.next().value; // 26
counter.next().value; // 25
// ...etc

The downCounter method appears stateless. As well, calling downCounter with the same input, will always result in the same output. However, at the same time, calling next() does not produce consistent results.

I'm unsure whether or not generators break the functional programming paradigm because in this example counter is a generator object and so calling next() would produce the same results as another generator object created with the exact same maxValue.

As well, calling someCollection[3] on an array would always return the fourth element. Similarily, calling next() four times on a generator object would also always return the fourth element.

For more context, these questions were raise while working on a programming kata. The person that answered the question, raised the question whether or not generators could be used in functional programming and whether or not they hold state.

Every program holds state. The real question is whether it qualifies as *functional* state, which I interpret as "immutable state," state that does not change once it is assigned. I claim that the only way you can make a generator return something different on each call is if mutable state is somehow involved. — Robert Harvey, Sep 29 '16 at 19:43

amon · Accepted Answer · 2016-09-29T20:07:17.290

Generator functions are not particularly special. We can implement a similar mechanism ourselves by rewriting the generator function in a callback-based style:

function downCounter(maxValue) {
  return {
    "value": maxValue,
    "next": function () {
      return downCounter(maxValue > 0 ? maxValue - 1 : 0);
     },
  };
}

let counter = downCounter(26);
counter.value; //=> 26
counter.next().value; //=> 25

Clearly, the downCounter is as pure and functional as it gets. There is no issue here.

The generator protocol used by JavaScript involves a mutable object. This is not necessary, see the above code. In particular, mutable objects mean we loose referential transparency – the ability to replace an expression by its value. While in my example, counter.next().value will always evaluate to 25 no matter where it occurs and how often we repeat it, this is not the case with the JS generator – at one point it is 26, then 25, and it could really be any number. This is problematic if we pass a reference to the generator to another function:

counter.next().value; //=> 25
otherFunction(counter); // does this consume the counter?
counter.next().value; // what will this be? It depends on the otherFunction()

So clearly, generators hold state and are therefore unsuitable for “pure” functional programming. Fortunately, you don't have to do do pure functional programming, and may be pragmatic instead. If generators make your code clearer, you should use them without a bad conscience. After all, JavaScript isn't a pure functional language, unlike e.g. Haskell.

By the way, in Haskell there is no difference between returning a list and a generator, since it uses lazy evaluation:

downCounter :: Int -> [Int]
downCounter maxValue =
  maxValue : (downCounter (max 0 (maxValue - 1)))
-- invoke as "take n (downCounter 26)" to display n elements

Are generator functions valid in functional programming?

1 Answers1