Mutating with `foldl` undefined behaviour?

General Usage
1 
help?> foldl
search: foldl mapfoldl foldr mapfoldr

  foldl(op, v0, itr)

  Like reduce, but with guaranteed left associativity. v0 will be used exactly
  once.

Is it undefined behaviour for op to mutate one (or both) of its arguments in the method above?

2

This is an interesting question — it is not documented explicitly, but given that the associativity is imposed, I would argue that

foldl(op, v0, itr)

should have a fixed evaluation order, and thus be equivalent in results and side effects to

let x = v0
    for elt in itr
        x = op(x, elt)
    end
    x
end

and deviations are bugs.

3

I assume you referring to the itr argument? Yes, it’s undefined what happens to an iterator when you change its underlying container.

4

Then I misunderstood the question, I was thinking about something like

julia>  x = [[i] for i in 1:5]
5-element Array{Array{Int64,1},1}:
 [1]
 [2]
 [3]
 [4]
 [5]

julia>  mutating_plus(acc, vec) = (acc=acc+vec[1]; vec[1] += 1; acc)

julia>  foldl(mutating_plus, 0, x)
15

julia>  x
5-element Array{Array{Int64,1},1}:
 [2]
 [3]
 [4]
 [5]
 [6]

ie foldl having a well-defined traversal order, which is the same as iteration.

1 Like
5

This is what I meant. I encountered a strange issue recently through a definition of

append!(x, y) = foldl(push!, x, y)

for a custom data structure; the issue went away after I replaced the foldl with an explicit loop. I asked this question to help diagnose the problem.