4 ms·
Does making the py recursive miss the point because py isnt guranteed to be immutable? def sum(list): if list: return list.pop() + sum(list)
by jakeogh 11y ago
Does making the py recursive miss the point because py isnt guranteed to be immutable?
def sum(list):
if list:
return list.pop() + sum(list)
return 0
- scardine 11y agoPython lacks the tail recursion optimizations common in functional languages like lisp. Seems like the language designers favor iteration instead of recursion, because recursion is limited to a depth of ~1000 on the default implementation (see sys.getrecursionlimit). It is always possible to convert recursive into iterative, and most of the time doing so is trivial. I recommend doing this unless your algorithm is O(log n) or better.
- dorfsmay 11y agoIs that true even with "generator expression" (Python's lazy evaluation)?
- solipsism 11y agoGenerators take the guts of a loop and make them first class. In order to evaluate that generator incrementally, you still need to provide a loop or a recursive function.
- groovy2shoes 11y agoThe OCaml version presented in the video isn't tail-recursive, either.
- jakeogh 11y agoaaah. The recursion limit. So sum() fails on large inputs.
- agumonkey 11y agoThe functional bits of python were a very early addition by a colleague of GvR, he never wanted lambdas, map and such to be in python.
- jakeogh 11y agoFor anyone curious, @ 15 min https://www.youtube.com/watch?v=r75X4Vn_E9k https://www.youtube.com/watch?v=r75X4Vn_E9k discusses a recursive sum() and why getrecursionlimit() is there.
- scardine 11y agoExcelent resource! I could not put it better than Gavin Bong in this talk "Functional Programming in Python for the Uninitiated". Thanks!
- thedufer 11y agoEven if Python did tail-recursion optimization, this implementation isn't tail-recursive so it would fail in the same way. This version is: def sum(li, s=0): if len(li) == 0: return s else: return sum(li[1:], li[0] + s)
- thinkpad20 11y agoI'm not sure if that's something that he wrote or you wrote, but a `sum` function which has a side-effect of emptying its input list seems like a terrible thing. I hope you wouldn't use that in production.
- jakeogh 11y agoWhy's that bad? If there's nothing else the input is needed for, why keep it around?
- lambda 11y agoWhen someone calls that, they wouldn't expect the input to be consumed. >>> list = [1,2,3] >>> sum(list)/len(list) >>> Traceback (most recent call last): File "<stdin>", line 1, in <module> ZeroDivisionError: integer division or modulo by zero
- jakeogh 11y agoThanks. I keep forgetting py isnt working on a copy of the var. copy.deepcopy() kinda fixes it, but then memory use is doubled, and the recursion limit kills it all anyway. I better go read my py code...
- cobaltblue 11y agoThe only one who knows if the input is needed anymore is the caller, not all callers will agree, so it's bad form to let the called function decide automatically unless it's very clearly marked as a mutating, list-destroying function.
- adrusi 11y agoIt's not bad necessarily to do it that way inline in another function, because there's no way to use it elsewhere without realizing that it has the side effect of emptying the list. However since this is recursive that's not realistically how it would be used. It wouldn't be bad if it were obvious what it did, which it isn't with the name "sum", but would be with the name 'sum_and_empty". For good measure, maybe "sum_in_linear_space_and_empty" is even better. It's also less efficient (although in the context of a recursive sum definition that's not too relevant). Essentially what you're doing here is using the length of the list as the iteration variable — the `i' in `for (i = n-1; i >= 0; i--)'. But `pop()' probably does more than decrement the length field, I imagine it also does some memory management bookkeeping at least. I also take issue with how `list' is mutated and accessed in the same expression. I don't really use python, but I think I recall reading that it in fact guarantees left-to-right evaluation of such expressions. Even still, it's confusing and makes programmers, especially those who write C/C++ where this is undefined behavior, uneasy.
- solipsism 11y agoYou can write functional code in any language, just as you've shown. But your mistake perfectly elucidates the point. When you call a function in a functional language, you know the variable you pass as the parameter won't be mutated. When you call a function in a non-functional language, you only hope it won't. And even when the type system allows you to know the input variable won't be mutated (say, passing by copy in C++), you don't know what other kinds of side-effects the function may be having.
- sampo 11y agoFortran, usually not regarded a functional language, has `pure` keyword to declare that a function (or procedure) has no side effects, and `intent(in)` to declare that a function argument will not be mutated.