rslt ← ival (func ##.foldl) vals            ⍝ Fold (reduce) from the left.

Phil  Last's  operator  uses  dyadic operand function [func] to accumulate items
from vector right argument [vals] starting with initial value [ival]. In effect:

    a f foldl i j k ··· →  (((a f i)f j)f k) ··· 

[foldl] is equivalent to, but faster than, the traditional operator:

    ∇ rslt←ival(func foldl)vals;val
[1]   rslt←ival
[2]   :For val :In vals
[3]       rslt←rslt func val    ⍝ accumulate result.
[4]   :End
    ∇

A related cumulative left-to-right scan operator might look like this:

    scanl←{⎕ML←0                ⍝ Scan from the left.
        2>⊃⌽⍴⍵:⍵                ⍝ few items: done.
        ⌽↑⍺⍺{
            (⊂(⊃⍵)⍺⍺ ⍺),⍵
        }/(⌽⍵),⊂⊂⍺
    }

    disp 'hello' ⌽⍨ scanl 1 1 0 ¯1 ¯1       ⍝ cf ascan in →scan←
┌→────┬─────┬─────┬─────┬─────┬─────┐ 
│hello│elloh│llohe│llohe│elloh│hello│
└────→┴────→┴────→┴────→┴────→┴────→┘ 

Technical note:

The domain or "type" of left argument [ival] is in general distinct from that of
the  items  of  right  argument  vector [vals]. In the  text replacement example
below,  the  left  argument is a character vector (text string) and the right, a
vector of from/to pairs.

To show what's going on, we could invent a type notation:

    ::                  "is of type",
    ⍺, ⍵, ∊, ⍳, ⍴, ···  arbitrary types ("type variables"),
    ∇, ∇∇               place marker for function, operator,
    ⍴ ←                 result type,
    ⍺[], ⍺[;], ···      vector, matrix, ··· of ⍺s.

Then:

    foldl :: ⍺ ← ⍺ ((⍺ ← ⍺ ∇ ⍵) ∇∇) ⍵[]

From this we can see that:

- the type of the result of the derived function is the same as the type of its
  left argument, which is also  ¯¯¯¯¯¯¯

- the type of the result of the operand function and the type of its left argu-
  ment;                         ¯¯¯¯¯¯¯

- the type of the right argument of the operand function is the same as the type
  of each item of the derived function's right argument vector.

Note how our type notation corresponds with traditional header syntax:

           ∇ rslt ← ival ( func        foldl ) vals     ⍝ trad header syntax.
    foldl :: ⍺    ← ⍺    ( (⍺ ← ⍺ ∇ ⍵) ∇∇    ) ⍵[]      ⍝ type notation.

where operand function [func] might be:

           ∇  new ← old func val                        ⍝ trad header syntax.
    func  ::  ⍺   ← ⍺   ∇    ⍵                          ⍝ type notation.

This  topic is explored in a little more depth in supplied workspace Max; search
for "type of" and "foldl" in max.dws/Introduction.

Similarly, the type of scanl, above, is:

    scanl :: ⍺[] ← ⍺ ((⍺ ← ⍺ ∇ ⍵) ∇∇) ⍵[]

Examples:

    repl←subs⍨                                  ⍝ ⍺ with ⍵ replacement.

    'I dare not' repl 'dare' 'would'            ⍝ single word replacement.
I would not

    'many a mickle' repl foldl 'nk' 'ye' 'iu'   ⍝ multiple letter replacement.
make a muckle

      0 ,foldl 2 3⍴⍳6                           ⍝ higher rank arrays.
0 1 2 3
0 4 5 6

    ⍝ For more examples, see →remnode← and →Graphs←

See also: acc pred scan remnode Graphs

Back to: contents

Back to: Dyalog APL

Trouble seeing APL font?