Below is the function count_leaf, that appends mutable list branch_counts, which is not stateless.

def count_leaf(tree):
    if is_leaf(tree):
        return 1
    branch_counts = list()
    for b in tree:
    return sum(branch_counts)

Below is the program that uses list comprehension.

def count_leaves(tree):
    if is_leaf(tree):
        return 1
        branch_counts = [count_leaves(b) for b in tree]
        return sum(branch_counts)

Is the function count_leaves using list comprehension [count_leaves(b) for b in tree] purely functional?

  • 1
    Where do you think you see state? – Andres F. Jul 16 '15 at 13:32

Yes it is, because there is no state being mutated. The line branch_counts = [count_leaves(b) for b in tree] can be interpreted as a simple binding (like a let statement in Haskell or Lisp), as there are no further reassignments or mutations.

Additionally, you could reformat it like this to make it clearer:

def count_leaves(tree):
    return 1 if is_leaf(tree) else sum([count_leaves(b) for b in tree])
  • Ok so, list comprehensions & generator expressions help us do functional programming ): – overexchange Jul 16 '15 at 11:58
  • 1
    Yes they're a frequent idiom in functional programming. Why the sadface @overexchange? – jcora Jul 16 '15 at 12:18

In this case you can pretend that it is, but be careful. List comprehentions create or mutate variables in the surrounding scope. (in ipython console):

In [1]: x
NameError: name 'x' is not defined

In [2]: [x for x in range(10)]
Out[2]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In [3]: x
Out[3]: 9

So if you had something like

x = "foo"
[x for x ...]

x will not be "foo" any more.

Note that this doesn't happen when using generator expressions:

In [4]: y
NameError: name 'y' is not defined

In [5]: (y for y in range(10))
Out[5]: <generator object <genexpr> at 0x7f55b7861e10>

In [6]: y
NameError: name 'y' is not defined

In [7]: y = "foo"

In [8]: y
Out[8]: 'foo'

In [9]: (y for y in range(10))
Out[9]: <generator object <genexpr> at 0x7f55b7877410>

In [10]: y
Out[10]: 'foo'

edit: Forgot to actually answer the question clearly. No, it is not stateless, it mutates state locally.

  • 1
    "No, it is not stateless, it mutates state locally." Maybe it introduces bindings, but strictly speaking his function is stateless. – jcora Jul 16 '15 at 14:03
  • yes, it does not mutate any variables in the enclosing scope and it does not modify it's arguments. But the same is true for the first function as well. – Pavel Penev Jul 16 '15 at 14:12
  • It's not because of this line: branch_counts.append(count_leaf(b)). This is mutating the state referred to by the branch_counts variable. – jcora Jul 16 '15 at 14:15

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.