1

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:
        branch_counts.append(count_leaf(b))
    return sum(branch_counts)

Below is the program that uses list comprehension.

def count_leaves(tree):
    if is_leaf(tree):
        return 1
    else:
        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?

Improve this question
1
  • 1
    Where do you think you see state? Commented Jul 16, 2015 at 13:32

2 Answers 2

Reset to default
2

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])
Improve this answer
2
  • Ok so, list comprehensions & generator expressions help us do functional programming ): Commented Jul 16, 2015 at 11:58
  • 1
    Yes they're a frequent idiom in functional programming. Why the sadface @overexchange? Commented Jul 16, 2015 at 12:18
0

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.

Improve this answer
3
  • 1
    "No, it is not stateless, it mutates state locally." Maybe it introduces bindings, but strictly speaking his function is stateless. Commented Jul 16, 2015 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. Commented Jul 16, 2015 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. Commented Jul 16, 2015 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.