Why iterator is considered functional-style in the Python documentation?

Question

I am trying to understand iterator. I notice Python documentation considers iterator to be a functional-style construct. I don't really understand it.

Isn't it true that iterator has a state inside it. So when you call it.__next__(), you mutate the state of the iterator. As far as I know, mutating state of an object is not considered functional, since functional programming emphasize on immutability and compose-ability of object/closure.

Actually, the problem comes up because I want to write a Scheme procedure/function which takes tokens and return a iterator.

(define tokens->iterator
  (lambda ls
    (lambda ()
      (if (null? ls)
          '*eoi*
          (let ((tok (car ls)))
            (set! ls (cdr ls))
            tok)))))

Notice I have to use set! to mutate ls, this is how I comes up with this question.

To use it,

(define it (tokens->iterator 1 '+ 2))

To test it,

scheme@(guile-user)> (it)
$2 = 1
scheme@(guile-user)> (it)
$3 = +
scheme@(guile-user)> (it)
$4 = 2
scheme@(guile-user)> (it)
$5 = *eoi*
scheme@(guile-user)> (it)
$6 = *eoi*

Just for fun, I also translate this to Python:

def tokens_to_iterator(*tup):
    ls = list(tup)
    def iterator():
        if not ls:
            return "*eoi*"
        else:
            tok = ls.pop(0)
            return tok
    return iterator

Similarly, the pop() method removes and return the first element by mutating the list.

To use it,

it = tokens_to_iterator(1, "+", 2)

To test it,

>>> it()
1
>>> it()
'+'
>>> it()
2
>>> it()
'*eoi*'
>>> it()
'*eoi*'

Can anyone clarify on this? By the way, I am using Python 3 and Guile Scheme in case anyone is interested in trying the examples.

Answer 1

The functional style is to work with lists of data as a whole, rather than a collection of values you can change at a whim. For instance, if you have a list of numbers, and you want to change the 3rd element, the non-functional approach is to directly change it:

>>> lst = ["a", "b", "c", "d", "e"]
>>> lst[3] = "Z"
>>> lst
["a", "b", "c", "Z", "e"]

The functional approach is to write a function that take the original sequence and returns a new list with the change made, leaving the original unchanged.

>>> lst = ["a", "b", "c", "d", "e"]
>>> new_lst = [x if i != 3 else "Z" for (i, x) in enumerate(lst)]
>>> lst
["a", "b", "c", "d", "e"]
>>> new_lst
["a", "b", "c", "Z", "e"]

Neither of your iterators is purely functional, because they do maintain mutable state, although treated as a black box you can use them functionally because the user of the iterator cannot affect that state directly.

A purely functional iterator would be a function that takes as input the list and the current state, and return a value and a new state to be passed to the next call of the function.

>>> state = 0
>>> def it(lst, state):
...   if state is None:
...       return None
...   return lst[state], state + 1
...
>>> lst = ["a", "b", "c", "d", "e"]
>>> value, new_state = it(lst, state)
>>> value
'a'
>>> state, new_state
(0, 1)
>>> it(lst, new_state)
('b', 2)
>>> state, new_state
(0, 1)

Answer 2

You have an excellent point. Iterators are certainly not "purely functional," the term often used to describe idioms that use no mutation at all. The broader term "functional," though, is more loosely defined to indicate programs that use relatively little mutation, that make use of higher-order and first-class functions, and perhaps most broadly of all, "use weird abstractions that don't look like C."

I think, to be frank, that I would not call iterators functional. That is: I agree with you.