Vocabulary/fcap
u F:. v Fold Multiple Forward Conjunction
u F:: v Fold Multiple Reverse Conjunction
u F: v Fold Multiple Conjunction
u F.. v Fold Single Forward Conjunction
u F.: v Fold Single Reverse Conjunction
u F. v Fold Single Conjunction
Rank Infinity -- operates on [x and] y as a whole -- WHY IS THIS IMPORTANT?
Generates a sequence defined by a recurrence relation.
Fold is the collective name given to the six primitives F.. F.: F. F:. F:: F:
x=: i.3 3 NB. seed (used as initial right argument to v) y=: 10 20 30 40 NB. driver sequence v=: + NB. recurrence relation between terms of sequence y seeded by x u=: <@:- NB. used for post-processing each term of the result x u F:. v y ┌───────────┬───────────┬───────────┬──────────────┐ │_10 _11 _12│_30 _31 _32│_60 _61 _62│_100 _101 _102│ │_13 _14 _15│_33 _34 _35│_63 _64 _65│_103 _104 _105│ │_16 _17 _18│_36 _37 _38│_66 _67 _68│_106 _107 _108│ └───────────┴───────────┴───────────┴──────────────┘
All members of the Fold family can be viewed as variants of one master conjunction: Fold Multiple Forward (F:.).
When should I consider Fold?
Fold is an elaboration of the features offered by insert (or reduction) (u/) and scan (u/\ or u/\.), which iterate over items of an array and produce either one result of u (for reduction) or one result of u per input item (for scan).
Fold does nothing that reduction and scan can't do. It offers advantages in space, speed, and convenience:
- Fold improves on scan by allowing each execution of the verb to select the parts of the iterated result that are preserved in the final result.
- Fold allows you to specify an initial value for the iteration, which
- saves you the effort of appending the initial value to the argument
- allows the initial value to have a different type or shape than the argument
- Fold allows you to terminate the iteration before all items have been operated on
Why not just use a loop?
In Basic, Python and C/C++, you'd use a loop for the things Fold does.
J has looping constructs too, notably while. and for. . But they are slow, cumbersome, and lack power. You feel this lack of power most when designing loops to save executing wasted code by use of break., continue., try. and throw.. The objective of J is to let you work on entire arrays with powerful flexible verbs, avoiding the need to map-out buggy complicated flow-of-control using blunt tools. See: Loopless programming explained.
Fold furthers this objective. It hides the complexity of optimized flow-of-control, implementing it in native code. This allows you to focus on designing two verbs:
- u to massage the returned result, term-by-term
- v to implement your recurrence relation.
Definitions
- Fold: A derived verb which successively combines values of its y argument, its optional x argument (if present) is used in the first combination. (Also, as shorthand, sometimes the conjunction which derives the fold.)
- Forward: y is processed left to right (or top to bottom) in the context of the fold's y argument
- Multiple: Every intermediate combined result appears in the fold's result
- Reverse: y is processed right to left (or bottom to top) in the context of the fold's y argument
- Single: Only the final intermediate combined result appears in the fold's result
Note also that x and y for the derived fold verb are different from x and y in the verbs which are arguments to the fold conjunction, and that we use "forward" and "reverse" here because left to right in terms of the fold's y argument would be different from J's right to left evaluation order.
Fold single examples:
- Forward (dyad): 0 u F.. v 2 3 4 is equivalent to u 4 v 3 v 2 v 0
- Reverse: u F.: v 2 3 4 is equivalent to u 2 v 3 v 4
Quickstart
If you are familiar with J's / picking up F.: should be quick:
U/Ymatches]F.:U Y
+/2 3 5 10 ]F.:+2 3 5 10
V@(U/)YmatchesV F.:U Y
-F.:+2 3 5 _10 -@(+/)2 3 5 _10
U/Y,Xwhere X is a single item inY,XmatchesX]F.:U Y
7]F.:+2 3 5 17
U/|.Ymatches]F..UandU/(|.Y),Xwhere X is a single item in(|.Y),XmatchesX]F..U Y
4 ]F..;1 2 3 ┌─┬─┬─┬─┐ │3│2│1│4│ └─┴─┴─┴─┘
]F::U Ytypically matches|.}: U/\. Y
Note that the result of ]F::U here only includes results from U. It does not include the single value from the far right of Y without U getting used.
|. }: ,/\. 'abc' bc abc ]F::, 'abc' bc abc
Of course, other variations are possible (and potentially more useful).
How should I define u and v?
The operands u and v together specify the recurrence relation that generates the result.
- Operand v implements the mathematical recurrence relation, building a notional underlying sequence to which u does not contribute.
- Operand u processes each term of the underlying sequence to build the returned result.
If you don't need the returned result to differ from the underlying sequence generated by v then set: u=:]
If you need only the last element of the sequence, use the Fold Single family
This diagram shows the dataflow from the x- and y-arguments of Fold to the returned noun:
|
|
Fold allows you to avoid needless computation and data storage. Improve the efficiency of your code like this:
- If you don't need the result item from each intermediate iteration, use Fold Single… (F.) not Fold Multiple… (F:)
- Call the primitive dyad Terminate Fold (Z:) within u or v to suppress the creation of redundant data as your code detects the opportunity for it. Use the x-arguments: _1, 0, or 1, which stop the iterations to return an abbreviated result.
There is little reason to use Z: this way in Fold Single. - For many purposes, u=:] will suffice. This returns the underlying sequence unchanged, viz. the list of intermediate values passed from each call of v to the next. But if you don't need this list as it stands, design u to keep only what data you need, in the format you need it. See a code example here which does exactly this in an extreme way.
- If v is commutative, the result of a forward fold will match that of a reverse fold.
How should I specify y?
Limited vs unlimited
The Fold Forward and Fold Reverse primitives (called limited folds) treat y as a list of candidate arguments for v, and generate an underlying sequence with one fewer item than y with monadic fold.
One element of the sequence is produced for each application of v. If x is not provided, then the first application of v consumes 2 items of y.
- F:. Fold Multiple Forward
- F:: Fold Multiple Reverse
- F.. Fold Single Forward
- F.: Fold Single Reverse
The other Folds (called unlimited folds) operate on y in its entirety and generate an underlying sequence of unlimited length
- F. Fold Single
- F: Fold Multiple
Therefore you must call Terminate Fold (Z:) within the body of either u or v in order to halt the execution of (unlimited) Fold.
When experimenting with F. or F:, it is wise to include (_3 Z: n) to force termination after a set number of iterations.
Single vs Multiple
Every execution of u produces a u-result. If you need only the last of the u-results, use a Single Fold. If you need all the u-results, use a Multiple Fold. Each u-result is one item of the overall result.
The result of a Single Fold is the same as taking the last item of the corresponding Multiple Fold, usually.
How should I specify x?
x in unlimited folds
In unlimited Folds (F. and F:) the x argument (if present) is applied to every execution of v; it can be thought of as supplying unchanging control information to the unlimited Fold.
x in Forward and Reverse Folds
In contrast, for folds that process items of y, the sole purpose of x is to supply the y-argument to the first call of v.
In other words, it provides an initial value for the whole series of iterations.
x is suitable as a right argument to v, which means it resembles a result from v.
Each subsequent call of v takes as its y-argument the output of the previous call of v. If x is absent then the first item of y is used as the initial y-argument to v.
As such, the following two phrases always return the same result – provided x is a valid item of y:
x u F:. v y NB. Dyad
u F:. v x,y NB. Monad
where F:. can be replaced by F::. The principle applies to reverse folds as well, but then the monad would be u F:. v y,x
The disadvantage of the second phrase, Monad, is that the types or shapes of x and y may be incompatible, making it undesirable or even illegal to form x,y.
Example: y may be hard-coded as i.n (for some integer n) but x may represent a given choice of starting condition and may have any type. Even if x and y are type-compatible, Dyad is better because it avoids the computational expense of forming (x,y) especially if y is large and low-precision.
Which primitive should I use?
To choose which primitive to use, read the inflections as follows:
- The 3 primitives: Fold Multiple * (F:…) return the whole sequence.
- The 3 primitives: Fold Single * (F.…) return only the last term (of the same sequence).
- The 2 primitives: Fold * Forward (F….) process y left-to-right. (C/f IndexOf(i.).)
- The 2 primitives: Fold * Reverse (F…:) process y right-to-left. (C/f IndexOfLast (i:).)
Mnemonically, the inflections are F[single|multiple][forward|backward|neither] where
- in the first character, . (one dot) means 'one result item' while : (multiple dots) means 'multiple result items' - reminiscent of #. and #:
- in the second character, . means 'from the beginning' while : means 'from the end' - reminiscent of {. and {: - and omitted means 'neither - the iteration is not by items'
Common uses
1. Apply a given recurrence relation to a list of numbers to yield a list of the same size
v=: dyad define z=. y + 0.01 z [smoutput x ; 'v' ; y ; '-->' ; z ) u=: monad define z=. -y z [smoutput ' u' ; y ; '-->' ; z ) x=: 100 ]y=: x, 0.1 + i.4 100 0.1 1.1 2.1 3.1 ]z=: u F:. v y NB. multiple forward ┌───┬─┬───┬───┬──────┐ │0.1│v│100│-->│100.01│ └───┴─┴───┴───┴──────┘ ┌─────┬──────┬───┬───────┐ │ u│100.01│-->│_100.01│ └─────┴──────┴───┴───────┘ ┌───┬─┬──────┬───┬──────┐ │1.1│v│100.01│-->│100.02│ └───┴─┴──────┴───┴──────┘ ┌─────┬──────┬───┬───────┐ │ u│100.02│-->│_100.02│ └─────┴──────┴───┴───────┘ ┌───┬─┬──────┬───┬──────┐ │2.1│v│100.02│-->│100.03│ └───┴─┴──────┴───┴──────┘ ┌─────┬──────┬───┬───────┐ │ u│100.03│-->│_100.03│ └─────┴──────┴───┴───────┘ ┌───┬─┬──────┬───┬──────┐ │3.1│v│100.03│-->│100.04│ └───┴─┴──────┴───┴──────┘ ┌─────┬──────┬───┬───────┐ │ u│100.04│-->│_100.04│ └─────┴──────┴───┴───────┘ _100.01 _100.02 _100.03 _100.04 z-: x u F:. v }.y NB. Try the equivalent dyad phrase ...identical boxed-trace omitted... 1
2. Apply a given recurrence relation to a list of numbers to yield the final result (an integer atom)
]z=: u F.. v y NB. single forward
┌───┬─┬───┬───┬──────┐
│0.1│v│100│-->│100.01│
└───┴─┴───┴───┴──────┘
┌─────┬──────┬───┬───────┐
│ u│100.01│-->│_100.01│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│1.1│v│100.01│-->│100.02│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│ u│100.02│-->│_100.02│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│2.1│v│100.02│-->│100.03│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│ u│100.03│-->│_100.03│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│3.1│v│100.03│-->│100.04│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│ u│100.04│-->│_100.04│
└─────┴──────┴───┴───────┘
_100.04
z-: {:(u F:. v y)
...identical boxed-trace omitted...
1
Notes
- Define u, v, x, y as in 1.
- The boxed entries generated by v are the underlying sequence. Observe they are the same as in 1.
- Likewise the boxed entries generated by u are the same as in 1.
- (u F.. v y) -: {: u F:. v y
Things to try
- Hide the boxed (trace) entries by commenting-out the smoutput lines in the bodies of u and v.
- Does the above monad/dyad identity work with…? (u F.: v y) -: {: u F:: v y
3. Build a sequence of any desired length from a single starting value
COUNT=: 5 NB. 1+ max length of generated sequence v=: monad define wd'msgs' NB. force pending smoutputs to appear in Term window. _2 Z: -.*COUNT=:COUNT-1 NB. _2 means: terminate Fold altogether z=. y + 1 z [smoutput ' v' ; y ; '-->' ; z ) u=: monad define z=. -y z [smoutput ' u' ; y ; '-->' ; z ) y=: 100 u F: v y ┌────┬───┬───┬───┐ │ v│100│-->│101│ └────┴───┴───┴───┘ ┌────┬───┬───┬────┐ │ u│101│-->│_101│ └────┴───┴───┴────┘ ┌────┬───┬───┬───┐ │ v│101│-->│102│ └────┴───┴───┴───┘ ┌────┬───┬───┬────┐ │ u│102│-->│_102│ └────┴───┴───┴────┘ ┌────┬───┬───┬───┐ │ v│102│-->│103│ └────┴───┴───┴───┘ ┌────┬───┬───┬────┐ │ u│103│-->│_103│ └────┴───┴───┴────┘ ┌────┬───┬───┬───┐ │ v│103│-->│104│ └────┴───┴───┴───┘ ┌────┬───┬───┬────┐ │ u│104│-->│_104│ └────┴───┴───┴────┘ _101 _102 _103 _104
Notes
- y-argument of Z: must be a boolean.
- y=0 is no-op.
- y=1 causes Z: to terminate Fold.
4. Simulate the trajectory of a falling object
cocurrent 'base' require 'plot' MAXITER=: 50 NB. safety long-stop S=: 100 NB. height above ground (m) - UPDATED T=: 0 NB. time at end of current epoch (s) - UPDATED e=: 0.1 NB. time interval of simulation epoch (s) - CONST U=: 0 NB. starting velocity (m/s) - CONST V=: U NB. velocity at end of current epoch (s) - UPDATED g=: 9.81 NB. acceleration due to gravity at earth surface (m/s^2) - CONST mean =: +/ % # NB. definition of mean - VERB trajectory=: monad : 'u F: v y' v=: monad define NB. Trajectory of solid object in free-fall _3 Z: MAXITER NB. Stop Fold when there have been too many iterations _2 Z: S<:0 NB. Stop Fold when object hits the ground NB. Recurrence relation is based on free-fall formula: V = U + gt V=: y + g*e NB. free-fall: vertical velocity at end of epoch S=: S - e*mean y,V NB. free-fall: vertical height at end of epoch T=: T + e NB. time of flight at end of epoch if. S<:0 do. smoutput '+++ LANDED: T=',":T end. V return. ) u=: monad : 'S' plot trajectory U +++ LANDED: T=4.6
Notes
- The underlying series is computed iteratively by operand: v
- Verb v returns current velocity V . But we want S trajectory, not V trajectory. Use operand u to return the current value of S
- Original model assumes motion is vertical. But the formulas remain valid even if object has constant horizontal velocity.
- By plotting successive epochs horizontally, addon plot manufactures a constant horizontal velocity for the falling object, now a projectile.
- A more advanced model capable of computing the trajectory of a spacecraft will handle velocity (V) and earth gravity (g) as 2-D or 3-D vectors, g becoming variable and directional. For extreme precision g even needs correction for general relativity, as required in practice for a GPS satellite.
More Information
1. Z: can appear multiple times during the execution of u and v.
- If (_2 Z: 1) is executed, the Fold terminates immediately, returning the most recent overall result.
- If (_1 Z: 1) is executed during the execution of v, v terminates immediately and the next iteration, if there is one, begins with the same right-argument as the previous iteration. The overall result is unchanged from the previous iteration.
- If (_1 Z: 1) is executed during the execution of u, u terminates immediately and the next iteration, if there is one, begins with the result of v as the right-argument. The overall result is unchanged from the previous iteration.
- If (0 Z: 1) is executed, execution proceeds normally, but the result of u is ignored and leaves the overall result unchanged from the previous iteration.
- If (1 Z: 1) is executed, the current iteration proceeds normally but is treated as the final iteration; at its conclusion, the overall result is returned.
When u completes, whether it contributes to the overall result depends on whether (0 Z: 1) was executed in the that iteration. Z:left-arguments of _2 and _1 cause u not to be completed for that iteration.
2. For Forward and Reverse Folds, the maximum number of iterations i is (((#y)-1) plus 1 if x is specified). If this value is _1 or 0, there are not enough items to apply v even once between items. In this case a result item r is calculated:
- if i is _1 (x is omitted and y has no items), r is u (v/) y, which is the neutral for u@(v/)
- if i is 0, r is u x if x is given, or u {. y if x is omitted.
note that u {. y is the same as u v/ y when y has one item.
Then, the result of Fold Single is r; the result of Fold Multiple is i # ,: r (which fails with error if i is _1).
3. If no execution of u has contributed to the final result, domain error is returned.
4. If the u-results do not have the same shape, the individual u-results are filled to bring them to a common item shape. In this case the last item of a Fold Multiple might differ from the result of the corresponding Fold Single because of the fill.