automatic folds from for loops

[johnynek]

a common idiom in python is something like:

x = 0
for y in z:
  x += y
return x

This does not look so functional, but it could be. We could convert for comprehensions like this into folds. We could do this by considering x += y to be rebinding a new x to x + y and we could look at all such rebound variables in the loop. Then we could convert it to something like:

z.foldLeft(0, \y, x -> x + y)

This is not so dissimilar to having the do notation in haskell which allows you to write imperative looking code that still returns a value.

Similarly, we could do the same translation for map-like for comprehensions: [f(x) for x in y] to y.map(f)

There may be some subtlety with making these fully composable which we would want to support.

[johnynek]

I think this is very doable: for becomes like a let binding that sets up all the values bound in the for and to be evaluated in a result.

The translation seems totally mechanical: find all the bindings in the for loop, put those into an anonymous tuple, the only catch is that we require that they were initially bound to handle the case of empty list, but we can statically see that of course.

[johnynek]

list comprehensions were done in #174

Still have not thought more about for loops that rebind variables. I think they can all be rewritten as folds on lists.

[johnynek]

actually, I think a better way to think about this is that a for loop is a let binding + a fold. It is always setting up a let binding for any values that are assigned in the for loop:

sum = 0
for x in xs:
  sum = sum + x
fn(sum)

this is the same as:

sum = xs.fold_left(0, \sum, x -> sum + x)
fn(sum)

or:

sum = 0
count = 0
for x in xs:
  count = count + 1
  sum = sum + x

fn(count, sum)

becomes:

(count, sum) = xs.fold_left((0, 0), \(count, sum), x -> (count + 1, sum + x))
fn(count, sum)

I think this translation is workable and would make it more convenient for people not expert in writing loops as folds.

[avibryant]

I think you mean sum = xs.fold_left(0, \sum, x -> sum + x).

This is great. The only thing I worry about is that the initialization of eg sum here is part of the same expression as the for but that's not obvious; what happens if you insert some unrelated expression (like a println) in between them?

[johnynek]

so, I think you rewrite the body of the for loop so you have an expression that returns a tuple of all the bindings. Since all the code is pure, that rewrite is safe. So, you can just replace the final expression in the for loop with (count, sum) and it should be correct I think.

[avibryant]

let me give a more concrete example. Is something like this legal?

sum = 3
z = sum*2
for x in xs:
  sum = sum + x
fn(sum, z)

[johnynek]

yeah, that's fine. translate to (noting rebinding lets is already allowed):

sum = 3
z = sum * 2
sum = xs.foldLeft(sum, \sum, x ->
  sum = sum + x
  sum)
fn(sum, z)

so, you just build a tuple of the values bound in the for loop, then put those bindings into a tuple and return it a fold. Isn't that what you intend?