Vocabulary/fcap
u F:. v Fold Multiple Forward Conjunction
u F:: v Fold Multiple Reverse Conjunction
u F.. v Fold Single Forward Conjunction
u F.: v Fold Single Reverse Conjunction
Rank Infinity -- operates on [x and] y as a whole -- WHY IS THIS IMPORTANT?
Limited Folds (F:. F:: F.. F.:) use the dyadic recurrence relation v to successively combine the items of array y one at a time with an accumulating value, optionally collecting the intermediate results.
Fold is the collective name given to the six primitives F.. F.: F. F:. F:: F:
The first character can be . or :, read as single or multiple. The second character can be ., :, or omitted, read as forward, reverse, or no direction.
x=: 100 NB. seed value
v=: {{x+y}} NB. recurrence relation
u=: {{-y}} NB. post-processing for each intermediate result
x u F:. v i.4 NB. fold multiple forward (i.e., from the left)
_100 _101 _103 _106
Fold Multiple Forward
All limited Folds can be thought of as variants of Fold Multiple Forward (F:.). Therefore F:. will be discussed first, and differences in the other Fold variants will be discussed with respect to F:. .
- Operand v implements the recurrence relation, building a notional underlying sequence. Operand u does not contribute to this sequence.
- 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 use u=:] .
The following diagram illustrates the dataflow of u F:. v . u0 is the first item of the overall result, and so on.
y=: 0 1 2 3
u F:. v y | x u F:. v y
|
v -------> u --> u2 | v -------> u --> u3
/ \ | / \
3 v -----> u --> u1 | 3 v ------> u --> u2
/ \ | / \
2 v ---> u --> u0 | 2 v ----> u --> u1
/ \ | / \
1 0 | 1 v --> u --> u0
| / \
| 0 x
The y argument is processed left to right (or top to bottom if y is multidimensional).
The x argument, if present, is used only as the "seed" (the right argument to v in the first iteration).
In each iteration, the next y-item to be processed is the left argument to v, and the v-result from the previous iteration is the right argument to v (reminiscent of u/).
Note that x and y for the derived verb (u F:. v) are different from x and y in the u and v operands, as described above.
u must be a monad, and v must be a dyad.
Every execution of u produces a u-result, which becomes one item of the overall result.
If the u-results do not all have the same shape, the individual u-results are filled to bring them to a common item shape.
If no execution of u has contributed to the final result (because each u-result was discarded by an execution of Terminate Fold (Z:)), a domain error is raised.
The following sections discuss how the other fold variants differ from Fold Multiple Forward.
Reverse Folds
The Reverse Folds (F:: and F.:) process y right to left (or bottom to top if y is multidimensional).
The following diagram illustrates the dataflow of Fold Multiple Reverse (u F:: v) . u0 is the first item of the overall result, and so on.
y=: 0 1 2 3
u F:: v y | x u F:: v y
|
v -------> u --> u2 | v -------> u --> u3
/ \ | / \
0 v -----> u --> u1 | 0 v ------> u --> u2
/ \ | / \
1 v ---> u --> u0 | 1 v ----> u --> u1
/ \ | / \
2 3 | 2 v --> u --> u0
| / \
| 3 x
Just as with a Forward Fold: in each iteration, the next y-item to be processed is the left argument to v, and the v-result from the previous iteration is the right argument to v.
If v is commutative (for example v=:+), the result of a Forward Fold will match that of a Reverse Fold.
Single Folds
The limited Single Folds (F.. and F.:) process the argument(s) in the same way as Multiple Folds.
The difference is that in a limited Single Fold, the result of the final application of u is itself the overall result of the fold; each u-result effectively replaces the previous one.
The result of a limited Single Fold is the same as taking the last item of the corresponding Multiple Fold, except that the latter may have framing fill.
Common uses
1. Apply a given recurrence relation to a list of numbers to yield an array with the same number of items
[x=: 100+i.3 3 NB. seed value (used as initial right argument to v) 100 101 102 103 104 105 106 107 108 y=: 10 20 30 40 NB. sequence of inputs to fold into accumulated result, one at a time v=: -~ NB. recurrence relation: [next item of y] -~ [result of the prior application of v] u=: < NB. post-processing for each intermediate result x u F:. v y NB. fold forward (i.e. from the left), collecting intermediate results ┌────────┬────────┬────────┬─────┐ │90 91 92│70 71 72│40 41 42│0 1 2│ │93 94 95│73 74 75│43 44 45│3 4 5│ │96 97 98│76 77 78│46 47 48│6 7 8│ └────────┴────────┴────────┴─────┘
When should I use Fold?
The only reason to use a limited Fold instead of insert (u/) or scan (u/\ or u/\.) is one of efficiency in space or speed, or of convenience. Use Fold in the following cases:
- When you want to essentially do an insert or scan, but you see that each item of the result is large, while only a small portion of each item is needed afterward. Or when you want to do a scan, but you see that only a small number of the result items which fulfill some condition are needed.
- Have u extract only the data you need, in the format you need it.
- Use Terminate Fold (x Z: y), with x e. _1 0, within u and/or v to suppress the creation of redundant result items or intermediate results. There is little reason to use Z: this way in a Single Fold.
- When you want to essentially do an insert, but the initial value for the iteration has a different type or shape than y's items.
- Use dyadic Fold, which avoids the expensive pointer creation and dereferencing incurred by the boxing/unboxing of, say, >u&.>/(<"_1 y),<x (equivalent to x ] F.: u y) .
- When you want to essentially do an insert or a scan, but you want to terminate the iteration before all items have been operated on.
- Use x Z: y, with x e. _2 1, within u and/or v to stop the fold iteration altogether when a given condition is reached.
Related Primitives
Insert (u/ y) , Prefix (u\ y), Suffix (u\. y)
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. 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".
Details
1. 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).
u F: v Fold Multiple Conjunction
u F. v Fold Single Conjunction
Rank Infinity -- operates on [x and] y as a whole -- WHY IS THIS IMPORTANT?
Unlimited Folds F: and F. successively apply the monadic recurrence relation v to the array y as a whole. In each iteration, v is applied to the v-result of the previous iteration.
These folds generate an underlying sequence of unlimited length.
Therefore you must call Terminate Fold (Z:) within the body of either u or v in order to halt the execution of an unlimited Fold.
Operand u , which is monadic, processes each v-result to build the returned result. If you don't need the returned result to differ from the underlying sequence generated by v then use u=:] .
In Fold Multiple, the u-results are collected, each becoming an item of the overall fold result.
In Fold Single, the result of the final application of u is itself the overall result of the fold; each u-result effectively replaces the previous one.
- The result of Fold Single is the same as taking the last item of the corresponding Fold Multiple, except that the latter may have framing fill.
When experimenting with F. or F:, it is wise to include (_3 Z: N) to force termination after a set number of iterations N.
x u F: v y is equivalent to u F:(x&v) y ; and similarly for x u F. v y. The x argument, if present, can be thought of as supplying unchanging control information to the unlimited Fold.
Common uses
1. Write a while loop without introducing special syntax or control words.
v=: {{
kbd=. 1!:1@1 y NB. get keyboard input (y is ignored)
_2 Z: 'quit' -: kbd NB. if user entered 'quit', then terminate fold, returning the u-results produced thus far
*: ". kbd NB. otherwise, convert character input to a number, and square it
}}
] F: v '' NB. square each keyboard input until user enters 'quit'
3
9
9
4
quit
9 81 81 16
2. Build a sequence from a single starting value until a given stop condition is reached.
NB. generate Fibonacci sequence while less than x:
v=: {{
a=. +/ _2{.y NB. generate next Fibonacci number from prior two
_2 Z: x<:a NB. terminate fold if next Fibonacci number exceeds x
y , a NB. else, append next Fib number to existing list
}}
y=: 0 1 NB. seed
100 ] F. v y NB. generate all Fibonacci numbers <100
0 1 1 2 3 5 8 13 21 34 55 89
Notes
- _2 Z: 1 causes termination of the Fold
- When a Single Fold is terminated, the latest u-result is returned.
- When a Multiple Fold is terminated, the u-results collected thus far are returned.
- y-argument of Z: must be a boolean.
- x Z: 0 is no-op.
Related Primitives
Power of Verb ([x] u^:v y)
More Information
1. F: and F. are similar to the constructs u^:v^:a: and u^:v^:_ respectively. However, unlike those constructs, the unlimited Folds do not stop iterating upon receiving the same input in two consecutive iterations. This means that they allow you to write any kind of loop (e.g., suitable for handling I/O interactions) in a compact notation without introducing special syntax or control words.