A fold whose folder destructures its element is quadratic: the in-place pass rejects it

[simontreanor]

Found while writing an ordinary program with Pyfun 0.6.0.

Building a Map by folding over a list of pairs is the idiom DESIGN.md
§5.1 promises runs in linear time. It does — unless the folder names the
pair by destructuring, which is how anyone writes a folder over pairs. That
spelling falls back to _pf_fold (functools.reduce over a fresh copy each
step) and goes quadratic. On a big input the difference is not a slowdown
but a hang.

let steps = words |> List.collect stepsOf      # (prefix, next letter) pairs

## Destructuring the pair: quadratic.
let slow = List.fold (fun m (p, l) -> Map.add p l m) Map.empty steps

## The same folder over fst/snd: linear.
let fast = List.fold (fun m s -> Map.add (fst s) (snd s) m) Map.empty steps

Measured on the 267,751-word SOWPODS list, 2.4 million (prefix, letter)
pairs:

words	fun m (p, l) ->	fun m s -> … (fst s) (snd s)
500	24 ms	—
1,000	102 ms	—
2,000	478 ms	12 ms
267,751	did not finish in 4 minutes	1,758 ms

Doubling the input quadruples the time, so it is the O(n²) copy-per-step the
pass exists to remove. A named top-level folder with the same destructuring
parameter (let add m (p, l) = Map.add p l m) is rejected the same way.

The tell

The emitted Python says which path was taken:

slow = _pf_fold(_pf_fn0, dict(), steps)      # reduce, fresh dict each step

m = dict()                                   # the in-place loop
for s in steps:
    m[_pf_fst(s)] = _pf_snd(s)
fast = m

Nothing else about the two folders differs — same body, same accumulator
discipline, same reads (a folder that reads the accumulator, Map.findOr p "" m, is accepted in the fst/snd spelling too). Only the parameter's shape
decides, and the shape that loses is the readable one.

Why it happens

plan_fold takes the folder's parameter names up front and gives up when
either has none (src/lowering/fold_loop.rs:178-182):

// A destructuring folder parameter (`fun (a, b) c -> …`) has no single
// name to substitute, and the pass rewrites by name — reject and fall
// through to the byte-identical `_pf_fold` lowering.
let acc_param = params[0].name()?.to_string();
let elem_param = params[1].name()?.to_string();

That comment is about the accumulator (params[0]), where a tuple
pattern really does change the plan — it is the multi-slot case P3 handles
via tuple_destructure when the body matches on it. But params[1] is the
loop variable, and a destructuring loop variable needs no substitution at
all: the ordinary lowering already binds a fresh _pf_arg1 and unpacks the
pattern at the top of the function body, and the fold loop could do exactly
that on its first line (for _pf_x in steps: p, l = _pf_x — or Python's own
for (p, l) in steps: for a flat tuple). The P8 shadowing check would then
see the pattern's bound names as body binders, which is where they already
land for the non-loop lowering.

The gap is easy to step around once you know it is there, but it is the
kind of cliff the fold-loop pass was written to make impossible: the same
program, two spellings a reader would call equivalent, linear versus
non-terminating.