Hacker News Reader

Comment by alain94040 | Hacker News Reader

That example is too simple for me to grasp it. How would you code a function that iterates over an array to compute its sum. No cheating with a built-in sum function. If you had to code each addition, how would that work? Curious to learn (I probably could google this or ask Claude to write me the code).

View on HN

Carmack gives updating in a loop as the one exception:

> You should strive to never reassign or update a variable outside of true iterative calculations in loops.

If you want a completely immutable setup for this, you'd likely have to use a recursive function. This pattern is well supported and optimized in immutable languages like the ML family, but is not super practical in a standard imperative language. Something like

  def sum(l):
    if not l: return 0
    return l[0] + sum(l[1:])

Of course this is also mostly insensitive to ordering guarantees (the compiler would be fine with the last line being `return l[-1] + sum(l[:-1])`), but immutability can remain useful in cases like this to ensure no concurrent mutation of a given object, for instance.

You don't have to use recursion, that is, you don't need language support for it. Having first class (named) functions is enough.

For example you can modify sum such that it doesn't depend on itself, but it depends on a function, which it will receive as argument (and it will be itself).

Something like:

  def sum_(f, l):
    if not l: return 0
    return l[0] + f(f, l[1:])

  def runreq(f, *args):
    return f(f, *args)

  print(runreq(sum_, [1,2,3]))

> You don't have to use recursion

You're using recursion. `runreq()` calls `sum_()` which calls `sum()` in `return l[0] + f(f, l[1:])`, where `f` is `sum()`

> You're using recursion.

No, see GP.

> `runreq()` calls `sum_()` which calls `sum()` in `return l[0] + f(f, l[1:])`, where `f` is `sum()`

Also no, see GP.

I am too stupid to understand this. This:

    def sum_(f, l):
      if not l: return 0
      return l[0] + f(f, l[1:])

    def runreq(f, *args):
      return f(f, *args)

    print(995,runreq(sum_, range(1,995)))
    print(1000,runreq(sum_, range(1,1000)))

when run with python3.11 gives me this output:

    995 494515
    Traceback (most recent call last):
      File "/tmp/sum.py", line 9, in <module>
        print(1000,runreq(sum_, range(1,1000)))
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^
      File "/tmp/sum.py", line 6, in runreq
        return f(f, *args)
               ^^^^^^^^^^^
      File "/tmp/sum.py", line 3, in sum_
        return l[0] + f(f, l[1:])
                      ^^^^^^^^^^^
      File "/tmp/sum.py", line 3, in sum_
        return l[0] + f(f, l[1:])
                      ^^^^^^^^^^^
      File "/tmp/sum.py", line 3, in sum_
        return l[0] + f(f, l[1:])
                      ^^^^^^^^^^^
      [Previous line repeated 995 more times]
    RecursionError: maximum recursion depth exceeded in comparison

A RecursionError seems to indicate there must have been recursion, no?

While your example of `sum` is a nice, pure function, it'll unfortunately blow up in python on even moderately sized inputs (we're talking thousands of elements, not millions) due to lack of tail calls in Python (currently) and the restrictions on recursion depth. The CPython interpreter as of 3.14 [0] is now capable of using tail calls in the interpreter itself, but it's not yet in Python, proper.

[0]: https://docs.python.org/3/whatsnew/3.14.html#a-new-type-of-i...

Yeah, to actually use tail-recursive patterns (except for known-to-be-sharply-constrained problems) in Python (or, at least, CPython), you need to use a library like `tco`, because of the implementation limits. Of course the many common recursive patterns can be cast as map, filter, or reduce operations, and all three of those are available as functions in Python's core (the first two) or stdlib (reduce).

Updating one or more variables in a loop naturally maps to reduce with the updated variable(s) being (in the case of more than one being fields of) the accumulator object.

Reply on news.ycombinator.com