3
\$\begingroup\$

Below is the problem:

Show that both summation and product are instances of a more general function, called accumulate, with the following signature:

def accumulate(combiner, start, n, term):
    """Return the result of combining the first n terms in a sequence."""
    "*** YOUR CODE HERE ***"

Accumulate takes as arguments the same arguments term and n as summation and product, together with a combiner function (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and a start value that specifies what base value to use to start the accumulation. Implement accumulate and show how summation and product can both be defined as simple calls to accumulate:

def summation_using_accumulate(n, term):
    """An implementation of summation using accumulate.

    >>> summation_using_accumulate(4, square)
    30
    """
    "*** YOUR CODE HERE ***"

def product_using_accumulate(n, term):
    """An implementation of product using accumulate.

    >>> product_using_accumulate(4, square)
    576
    """
    "*** YOUR CODE HERE ***"

For which, solution is mentioned below:

from operator import add
from operator import mul

def square(x):
    """ Retrun x squared"""
    return x * x


def accumulate(combiner, start, n, term):
    """Return the result of combining the first n terms in a sequence."""
    if n == 0:
        return start
    else:
        start = combiner(term(n), start)
        return accumulate(combiner, start, n-1, term)

def summation_using_accumulate(n, term):
    """An implementation of summation using accumulate.

    >>> summation_using_accumulate(4, square)
    30
    """
    assert n >= 0
    return accumulate(add, 0, n, term)



def product_using_accumulate(n, term):
    """An implementation of product using accumulate.

    >>> product_using_accumulate(4, square)
    576
    """
    assert n > 0
    return  accumulate(mul, 1, n, term)    

result =  summation_using_accumulate(4, square)
print(result)
result = product_using_accumulate(3, square)
print(result)

Please let me know if this program can be improved further using functional paradigm and the DRY principle.

\$\endgroup\$
1

2 Answers 2

2
\$\begingroup\$

The start parameter of accumulate is a bit misleading. My first thought was that start is the first element of the sequence, but it's an accumulated value. A more common name is acc or accum.

Reassigning function parameter is considered a bad practice, in any language as far as I remember. It's basically reusing an input variable for one additional purpose. start is an input to your function, but when you reassign it, it becomes something else: instead of being just the input, now it carries the result of a calculation. When you look at your function body, the variable start is sometimes the input, sometimes the result of a local calculation. This duality in purpose can be confusing and can lead to errors. It's cleaner to assign the mutated value to a completely new local variable.

In this version, acc always has the same value, there can be no confusion and misuse, it's perfectly clear:

def accumulate(combiner, acc, n, term):
    """Return the result of combining the first n terms in a sequence."""
    if n == 0:
        return acc
    else:
        next_acc = combiner(term(n), acc)
        return accumulate(combiner, next_acc, n-1, term)

The benefit may not be obvious in this simple function, but I hope you see the truth in the principle of not reusing parameter variables. In a longer, more complicated function the benefits would become more clear.

In languages that have out-parameters, re-assignment of parameters forces me to double-check the signature. Although Python doesn't have out-parameters, I still review code like this with suspicion, in case the author may have mistakenly believed that the re-assigned value will produce a side effect outside the function. This may sound a bit paranoid, but I've seen this kind of thing happen more than once. By not re-assigning parameters, all suspicions are cleared, and the code is easier to review.

For the record, I was tempted to suggest to drop the else clause there, to simplify to:

def accumulate(combiner, acc, n, term):
    """Return the result of combining the first n terms in a sequence."""
    if n == 0:
        return acc
    next_acc = combiner(term(n), acc)
    return accumulate(combiner, next_acc, n-1, term)

But then, most functional languages return the last evaluation, and explicit return statements are not recommended, which makes if-else necessary. For example the Scala solution would look something like this:

def accumulate(combiner, acc, n, term): Int = {
    if (n == 0) {
        acc
    } else {
        val nextAcc = combiner(term(n), acc)
        accumulate(combiner, nextAcc, n-1, term)
    }
}

So using the explicit else clause is closer to the spirit of functional programming, so I'd leave that as you did.

\$\endgroup\$
6
  • \$\begingroup\$ For your point: when you reassign it, it becomes something else, which can be confusing and can lead to errors. What kind of errors does this re-assignment can lead to? This is the most vague part for me which is yet to be understood. I learnt that re-assignment is against the spirit of FP. why? am not sure. Please help me on this!!! \$\endgroup\$ Commented Feb 13, 2015 at 8:23
  • \$\begingroup\$ Hi @overexchange, I rephrased that part, and added a new paragraph about an additional concern of misunderstood out-parameters. Let me know if any of this is still not yet clear. \$\endgroup\$
    – janos
    Commented Feb 13, 2015 at 10:54
  • \$\begingroup\$ @janos Yes, I agree that, Reassigning function parameter is considered a bad practice and further reasons make sense. But If we have locally scoped object count in the solution given by OP, count is re-assigned to carry the result of a calculation. What is the rationale behind re-assignment of locally scoped objects pointed by count, being considered a bad practice in FP? Because count holds the meaning of purpose it is introduced for. In addition reassignment of countis an abstraction from the user who is using that function. \$\endgroup\$ Commented Feb 13, 2015 at 13:06
  • 1
    \$\begingroup\$ @overexchange for the record, my argument against reusing function parameters for local mutations is for all languages, not only FP. About the count variable in the question you linked, the variable is local, not a function parameter, so mutating it with += is fine. Although FP prefers no mutations, in this case, since the variable is local, and as such there's no danger of concurrent access by multiple threads, I think the mutation is acceptable. \$\endgroup\$
    – janos
    Commented Feb 13, 2015 at 13:38
  • \$\begingroup\$ Wrt the point Although Python doesn't have out-parameters Is the second parameter of codesnippet in this solution def computeSequence(n, listOfSequence): not an out-param? I did not get you when you say, Python does not have out-parameters. \$\endgroup\$ Commented Feb 14, 2015 at 7:40
0
\$\begingroup\$

Looks fine to me, except this line:

start = combiner(term(n), start)

Reassigning variables is considered improper in functional programming.

\$\endgroup\$
5
  • \$\begingroup\$ Is it? The "improper" thing is mutating; rebinding is normally fine, albeit is just shadowing in most functional languages. \$\endgroup\$
    – Veedrac
    Commented Feb 13, 2015 at 3:54
  • \$\begingroup\$ So, Can you suggest me with alternate solution? \$\endgroup\$ Commented Feb 13, 2015 at 4:01
  • \$\begingroup\$ @Veedrac Whether you re-bind or mutate, python creates a new object and get refers by name start. So every object in the above program has a single state in its life time. \$\endgroup\$ Commented Feb 13, 2015 at 4:03
  • 1
    \$\begingroup\$ @overexchange I can't tell whether you're agreeing with me or not. Anyway, I wrote an example in OCaml to make it obvious what I mean. \$\endgroup\$
    – Veedrac
    Commented Feb 13, 2015 at 5:33
  • \$\begingroup\$ @Veedrac The shadowing in your OCaml is OK, since let makes a new scope, and the rebinding has no side-effect outside that scope. In start = combiner(term(n), start), however, no new scope is created; the new value of start is henceforth effective throughout the function's stack frame. That side-effect is why I think it is against the spirit of functional programming. Since Python doesn't offer a better scoping mechanism than the function, my recommendation is to either choose a different variable name or just write accumulate(combiner, combiner(term(n), start), n-1, term) inline. \$\endgroup\$ Commented Feb 13, 2015 at 7:07

Your Answer

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

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