Vocabulary/fcap

From J Wiki
Jump to: navigation, search

>> <<   Back to: Vocabulary

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



Fold generates a sequence defined by a recurrence relation.

Fold is the collective name given to the six primitives  F.. F.: F. F:. F:: F:

Information.png All members of the Fold family are best understood as variants of one master conjunction: Fold Multiple Forward (F:.). Therefore we will focus on this conjunction and base our code samples on it.


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 and v to implement your recurrence relation.


How should I define u and v?

The operands u and v together specify the recurrence relation that generates the result.

  • Operand u implements the mathematical recurrence relation, building a notional underlying sequence to which v does not contribute.
  • Operand v 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 u then set: v=:]

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: Nuvoc-fold-diagram.jpg

  • y0, y1, y2, y3 — the items of list y
  • u (ringed) — the mappings defined by each call of verb u
  • v (ringed) — the mappings defined by each call of verb v
  • u0, u1, u2, u3 — the notional underlying sequence, comprising the values returned by each call of verb u applied to x and items y0, y1, y2, y3
  • v0, v1, v2, v3 — the list that actually gets returned, comprising the values returned by each call of verb: v applied to u0, u1, u2, u3 .


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… not Fold Multiple…
  • 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 don't abort Fold itself, but only halt individual iterations to return an abbreviated but still valid result.
  • For many purposes,  v=:] will suffice. This returns the underlying sequence unchanged, viz. the list of intermediate values passed from each call of u to the next. But if you don't need this list as it stands, design v 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.

How should I specify y?

Limited vs unlimited

The Fold Forward and Fold Reverse primitives treat y as a list of candidate arguments for u, and generate an underlying sequence with one fewer item than y

One element of the sequence is produced for each application of u. The first application of u 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 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 v produces a v-result. If you need only the last of the v-results, use a Single Fold. If you need all the v-results, use a Multiple Fold. Each v-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?

Once you supply (F:.) with operands u and v, the resulting verb (u F:.v) (call it myFold) is Monad-Dyad. This raises the question: how should Dyad be used, if at all?

x in unlimited folds

In unlimited Folds (F. and F:) the x argument (if present) is applied to every execution of u . Think of it as supplying unchanging control information to the 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 u.

In other words, it provides an initial value for the whole series of iterations.

Each subsequent call of u takes the output of the previous call for its y-argument. If x is absent then Monad myFold uses the first item of y instead, which then stops being logically part of y.

The upshot is that these two phrases always return the same result – provided both are valid:

   x u F:. v y     NB. Dyad
     u F:. v x,y   NB. Monad

where F:. can be replaced by any Fold primitive.

The disadvantage of the second phrase, Monad, is that the types 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

   u=: dyad define
z=. y + 0.01
z [smoutput x ; 'u' ; y ; '-->' ; z
)

   v=: monad define
z=. -y
z [smoutput '    v' ; 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│u│100│-->│100.01│
└───┴─┴───┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│100.01│-->│_100.01│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│1.1│u│100.01│-->│100.02│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│100.02│-->│_100.02│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│2.1│u│100.02│-->│100.03│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│100.03│-->│_100.03│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│3.1│u│100.03│-->│100.04│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│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│u│100│-->│100.01│
└───┴─┴───┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│100.01│-->│_100.01│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│1.1│u│100.01│-->│100.02│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│100.02│-->│_100.02│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│2.1│u│100.02│-->│100.03│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│100.03│-->│_100.03│
└─────┴──────┴───┴───────┘
┌───┬─┬──────┬───┬──────┐
│3.1│u│100.03│-->│100.04│
└───┴─┴──────┴───┴──────┘
┌─────┬──────┬───┬───────┐
│    v│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 u are the underlying sequence. Observe they are the same as in 1.
  • Likewise the boxed entries generated by v 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

   u=: 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 '   u' ; y ; '-->' ; z
)

   v=: monad define
z=. -y
z [smoutput '   v' ; y ; '-->' ; z
)

   y=: 100

   u F: v y
┌────┬───┬───┬───┐
│   u│100│-->│101│
└────┴───┴───┴───┘
┌────┬───┬───┬────┐
│   v│101│-->│_101│
└────┴───┴───┴────┘
┌────┬───┬───┬───┐
│   u│101│-->│102│
└────┴───┴───┴───┘
┌────┬───┬───┬────┐
│   v│102│-->│_102│
└────┴───┴───┴────┘
┌────┬───┬───┬───┐
│   u│102│-->│103│
└────┴───┴───┴───┘
┌────┬───┬───┬────┐
│   v│103│-->│_103│
└────┴───┴───┴────┘
┌────┬───┬───┬───┐
│   u│103│-->│104│
└────┴───┴───┴───┘
┌────┬───┬───┬────┐
│   v│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

trajectory=: monad : 'u F: v y'

u=: 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.
)

v=: monad : 'S'

plot trajectory U
+++ LANDED: T=4.6

Plot-trajectory-Fold.jpg

Notes

  • The underlying series is computed iteratively by operand: u
  • Verb u returns current velocity V . But we want S trajectory, not V trajectory. Use operand v to return the current value of S
  • Original model assumes motion is vertical. But the fomulas 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 result.
  • 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 same right-operand as the previous iteration. The result is unchanged.
  • 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 result of u as the right-operand. The result is unchanged.
  • If (0 Z: 1) is executed, execution proceeds normally, but when v completes the result is unchanged.
  • If (1 Z: 1) is executed, execution proceeds normally, but stops before the next iteration, returning the result incumbent at that time.

When v completes, whether it contributes to the result depends on whether (0 Z: 1) was executed. Z:left-arguments of _2 and _1 cause v not to be completed for that iteration. When the next iteration is ready to start, execution terminates if (1 Z: 1) was executed.

2. For Forward and Reverse Folds, the maximum number of iterations is (((#y)-1) plus 1 if x is specified). If this value is _1 or 0, there are not enough items to apply u even once. In this case v@(u/) will be applied to a empty array (taken from x if x is given, otherwise from y) to produce the neutral for u: the result of Fold Single will be that neutral, while the result of Fold Multiple will be an empty array of 0 items of that neutral.

3. Except when a fill-cell has been used, if no execution of v has contributed to the final result, domain error is returned.

4. If the v-results do not have the same shape, the individual v-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.