rslt ← (func ##.acc) argt ⍝ Accumulating reduction. Phil Last's operator applies its function operand cumulatively between pairs of items in its vector argument. Technical note: For a side-effect-free associative operand function, this operator _could_ be coded in terms of primitive scan. However, this scan would be evaluated using (0.5××/0 ¯1+⍴⍵) reductions, resulting in an O(n*2) algorithm. acc←{⌽⍺⍺⍨\⌽⍵} ⍝ slow O(n*2) coding. Gianluigi Quario adds this nice surprise: ( A few months ago I received some helpful suggestions about polynomial evalu- ation when the polynomial P(Y) is represented (in ascending order) by a vec- tor "poly". P(Y) : poly[0] + Y×poly[1] + Y×poly[2] + ..... +Y×poly[N] I was impressed by this idiom: value ← point {⍺+⍺⍺×⍵}/poly which calculates the value of a real polynomial "poly" at point "point" by means of Ruffini's rule and Horner's {⍺+⍺⍺×⍵}/ algorithm. I think that this idiom has a greater semantic clarity than the primitive "base value": value ← point ⊥ ⌽poly which internally uses <but externally hides> Horner's algorithm. Over and above it can easily be extended to rectangular arrays by means of the following D-fn: PolyEval ← {⊃⍵{⍺+⍺⍺×⍵}/⍺} In fact we can play: values ← poly PolyEval points even when "points" is an array . But I had another surprise when I matched the Horner's algorithm with [acc]. If we write: point {⍺+⍺⍺×⍵} acc poly instead of point {⍺+⍺⍺×⍵} / poly we obtain not only the value of the polynomial at point "point", i.e. the remainder of division of poly with monomial "Y-point" , but also the quot- ient polynomial according to Ruffini's rule, which we studied at school. If P(Y) is a polynomial and "Y - point" a monomial, then substituting "{⍺+⍺⍺×⍵}/" with "{⍺+⍺⍺×⍵} acc" returns the quotient polynomial Q(Y) and the remainder polynomial R(Y) of the polynomial division. By means of the simple idiom {⍺+⍺⍺×⍵} and operator "acc" it is possible to implement the Ruffini simple_division_rule between a polynomial and a mono- mial with neither iterations nor recursions. The use of operator "acc" is performing something similar to: ⎕←poly[0] + point×⎕←poly[1] +point×⎕←poly[2] + ..... + point×⎕←poly[N] Now we are the masters of a holistic window on Ruffini's rule for simple division. "** APL is an actual tool for supporting the chains of reasoning and creating knowledge **" - Gianluigi Quario. ) Examples: {⍺,'f',⍵}acc'abcd' ┌───────┬─────┬───┬─┐ │afbfcfd│bfcfd│cfd│d│ └───────┴─────┴───┴─┘ ,acc ⍳4 ┌───────┬─────┬───┬─┐ │1 2 3 4│2 3 4│3 4│4│ └───────┴─────┴───┴─┘ slow←{⌽⍺⍺⍨\⌽⍵} ⍝ O(n*2) coding. disp ,slow ⍳4 ⍝ slow coding concurs for associative operand fn. ┌───────┬─────┬───┬─┐ │1 2 3 4│2 3 4│3 4│4│ └───────┴─────┴───┴─┘ ⍲acc 1 0 0 ⍝ ⍲ is non-associative (although it is commutative). 0 1 0 ⍲slow 1 0 0 ⍝ slow coding differs for non-associative operand. 1 1 0 See also: pred scan traj while foldl trav Back to: contents Back to: Workspaces