Leonid provides a nice method for doing this within "pure functions" but I think it should be pointed out that the common method for doing this is pattern matching.
I argue that destructuring is the foundational use of pattern matching in Mathematica.
Every replacement pattern, be it an explicit rule (:>, ->) or part of a definition (:=, =), that uses a named pattern on the left-hand side that does not match the entire expression or argument is doing destructuring.
Applied to your specific example:
f[a_, {i_, j_}] := a == 0 || Abs[i - j] <= 1
triDiagonalQ[mat_] := And @@ Flatten @ MapIndexed[f, mat, {2}]
Or:
triDiagonalQ[mat_] := And @@ Flatten @
MapIndexed[#2 /. {i_, j_} :> # == 0 || Abs[i - j] <= 1 &, mat, {2}]
The second example is almost exactly what you asked for: "with a {i, j} <- #2 somewhere"
It's just turned around: #2 /. {i_, j_}.
This destructuring is common in Mathematica programming for experienced users.
Among many examples:
Here I use it with to separate a + b + c:
(a + b + c) /. head_[body___] :> {head, body} (* Out= {Plus, a, b, c} *)
Here Leonid uses it in a recursive function. ({x_, y_List})
Szabolcs uses it in iter, also recursive.
Heike uses it with /. in PerforatePolygons and with := in torn.
Here I used it simply in formula but also in MakeBoxes[defer[args__], fmt_] := where the parameter pattern defer[args__] serves to match the literal head defer while also destructuring.
In withOptions it is used both in the function definition and in the replacement rule.
The "injector pattern" is a form of destructing.
I also used it in inside, withTaggedMsg, pwSplit, dPcore etc.
Another, simpler form of destructuring exists in the form of Set and List ({}). A matching List structure on the left and right sides of = will assign values part-wise.
{{a, b}, c, {d}} = {{1, 2}, 3, {4}};
{a, b, c, d}
{1, 2, 3, 4}
This is used e.g. in the first LUDecomposition example, and R.M uses it here.
