Iterate/Converge syntax Question

[QUser]

f:{x,+/-2#x}/[31;1 1]

Can someone explain to me the syntax rules governing the iterate expression? I understand that the function takes 1 argument, since x is the only arg being utilized, but how does the language, and the reader, know that the first argument is an iterator, and not some value to be passed to the function?

[TerryLynch]

The language knows that the function is monadic (takes a single variable as input), knows that you've passed two arguments and knows that you're iterating using over (/). Thus it will check the first input variable: if it's an integer/long it will run the iteration that many times, if it's a function/lambda/projection that produces a boolean output then it continues so long as the boolean is true. 

Similarly if you only input a single argument it knows to iterate until convergence (same result appears twice in a row). 

Terry

[SJT]

From a work in progress. Note that f is a unary map, i.e. a unary function or a list or dictionary. See following message for discussion. 

Iterate¶

The Iterate adverb repeatedly evaluates a unary map on first its argument, then successively on the results. It has three forms: Converge, Repeat, and While.

syntax	name	semantics
(f/)d, f/[d] (f\)d, f\[d]	Converge	apply f to d until result converges
n f/d, f/[n;d] n f\d, f\[n;d]	Repeat	apply f to d, n times
t f/d, f/[t;d] t f\d, f\[t;d]	While	apply f to d until t of the result is 0

Key

d: data               n: int atom ≥0        f: unary map          t: unary test map

Equivalent forms with / and \ perform exactly the same computation. Forms with / return the final result; forms with \ return a list of all the results.

If you want only the final result but don’t get the result you expect, replace / with \ to see the intermediate results. They are usually illuminating.

Set \P 0 to see the convergence of your original computation.

Converge¶

Are we there yet?

Apply a map until the result converges.

Syntax: (f/)d, f/[d]
Syntax: (f\)d, f\[d]

Where f is a unary map the derivatives f/ and f\ apply f repeatedly to d until either

• two successive results agree within comparison tolerance
• the result matches d

The latter will save you from some infinite cycles but not all.

q)(not/) 1b0bq)(not/) 42  /never returnsq)(neg\)11 -1q)(rotate[1]\)"abcd""abcd""bcda""cdab""dabc"q)({x*x}\)0.10.1 0.01 0.0001 1e-08 1e-16 1e-32 1e-64 1e-128 1e-256 0q){x*x}\[0.1]   / alternative syntax0.1 0.01 0.0001 1e-08 1e-16 1e-32 1e-64 1e-128 1e-256 0

Repeat¶

Apply a unary map n times.

Syntax: n f/d, f/[n;d]
Syntax: n f\d, f\[n;d]

Where

• f is a unary map
• n is an int atom ≥0
• d is data

the derivatives f/ and f\ return the result of n successive applications of f to d.

f f f … f f f d

q)dbl:2*q)3 dbl/540q)3 dbl\55 10 20 40/first 10+2 numbers of Fibonacci sequenceq)10{x,sum -2#x}/0 1             / derived binary applied infix0 1 1 2 3 5 8 13 21 34 55 89/first n+2 numbers of Fibonacci sequenceq)fibonacci:{x,sum -2#x}/[;0 1]  / projection of derived functionq)fibonacci 100 1 1 2 3 5 8 13 21 34 55 89q)gibonacci:{x,sum -2#x}\[;0 1]  / examine intermediate resultsq)gibonacci 100 10 1 10 1 1 20 1 1 2 30 1 1 2 3 50 1 1 2 3 5 80 1 1 2 3 5 8 130 1 1 2 3 5 8 13 210 1 1 2 3 5 8 13 21 340 1 1 2 3 5 8 13 21 34 550 1 1 2 3 5 8 13 21 34 55 89

Since the domain of n includes 0 you can use this as a form of conditional application.

q)0 dbl/55

While¶

Apply a unary map while a condition remains true.

Syntax: t f/d, f/[t;d]
Syntax: t f\d, f\[t;d]

Where

• f is a unary map
• t is a unary test map
• d is data

the derivatives f/ and f\ return the result of successive applications of f to d until tapplied to it returns zero.

q){x+x}/[{x<1000};2]   /prefix: f/[t;d]1024q){x<1000}{x+x}/2      /infix: t f/d1024q){x<1000}{x+x}\22 4 8 16 32 64 128 256 512 1024q)inc:1+q)inc\[105>;100]100 101 102 103 104 105q)inc\[105>sum@;84 20]84 2085 21

Stephen Taylor | Librarian | Kx | +44 7713 400852 | stephen@kx.com

[SJT]

Iterate¶

We shall not cease from exploration
And the end of all our exploring
Will be to arrive where we started
And know the place for the first time.
— T.S. Eliot, “Little Gidding”

With a unary map, / and \ are the Iterate adverb in its three forms: Converge, Repeat, and While. Iterate repeatedly applies the map, first to an argument, then to the result of the application.

syntax	semantics
(m/)y, m/[y] (m\)y, m\[y]	Converge
n m/y, m/y[n;y] n m\y, m\[n;y]	Repeat
t m/y, m/[t;y] t m\y, m\[t;y]	While

Key

m: unary mapn: integer ≥0t: unary map with 0 in its rangey: object in the domain of m

The derivatives m/ and m\ are variadic. Applying them as

• unary functions give Converge
• binary functions give Repeat or While, according to the left argument

Repeat¶

Syntax: n m/y, m/[n;y]
Syntax: n m\y, m\[n;y]

Repeat applies m/ and m\ as binaries. It means apply the map n times.

q)halve:%[;2]q)halve[1024]512fq)halve/[3;1024 16]128 2f

The derivative’s right argument is the initial state; its domain, that of halve. The left argument is the number of times halve is evaluated.

q)halve halve halve 1024 16128 2f

Replace / with \ and the derivative returns not just the last, but the initial state and the results of all the applications.

q)halve\[3;1024 16]1024 16512  8256  4128  2

The binary derivative is often applied infix.

q)3 halve\1024 161024 16512  8256  4128  2q)10{x,sum -2#x}/0 1           / first 10+2 numbers of Fibonacci sequence0 1 1 2 3 5 8 13 21 34 55 89

Lists and dictionaries are also unary maps.

q)show double:2*til 100 2 4 6 8 10 12 14 16 18q)double double double 2 116 8q)3 double/2 116 8q)route                        / European tour routeBerlin  | LondonFlorence| MilanLondon  | ParisParis   | FlorenceMilan   | ViennaVienna  | Berlinq)3 route\`London              / fly three stages, start London`London`Paris`Florence`Milanq)3 route\`London`Vienna       / start London - or ViennaLondon   ViennaParis    BerlinFlorence LondonMilan    Paris

The dictionary route here represents a simple finite-state machine.

While¶

Syntax: t m/y, m/[t;y]
Syntax: t m\y, m\[t;y]

While is the other binary application of m/ and m\. Here t is a ‘test’ – a unary map that

• has 0 in its range
• has the range of m in its domain

The map t is applied to each successive application of m, to see Are we there yet?. When treturns 0, iteration ends.

q)mod[;5] +[3;]\1                           / add 3 until a multiple of 51 4 7 10q)<>[;`London] route\`Paris                 / start in Paris, stop in London`Paris`Florence`Milan`Vienna`Berlin`Londonq)<>[;`London] route\`Vienna                / start in Vienna, stop in London`Vienna`Berlin`London

In the above, the test map t is a unary function. It can also be a list or a dictionary.

q)show t:mod[til 20;5]0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4q)t (3+)\11 4 7 10q)waypointsBerlin  | 1Florence| 1Milan   | 1Paris   | 1Vienna  | 1q)waypoints route\`Paris              / start Paris, continue through waypoints`Paris`Florence`Milan`Vienna`Berlin`London

The tour ends in the first city that is not a waypoint.

Converge¶

Syntax: m/y, m/[y]
Syntax: m\y, m\[y]

Converge is the unary application of m/ and m\. Without a left argument to specify an endpoint, m is applied until the result matches either

• the initial value y
• the result of the previous application

q)(neg\)11 -1q)(rotate[1]\)"abcd""abcd""bcda""cdab""dabc"q){x*x}\[0.1]0.1 0.01 0.0001 1e-08 1e-16 1e-32 1e-64 1e-128 1e-256 0

The first two examples above terminated when they encountered the original value of y; the last when the result was indistinguishable from 0.

As always, lists and dictionaries are also maps.

q)a1 8 5 6 0 3 6 4 2 9q)10 a\1                / repeat1 8 2 5 3 6 6 6 6 6 6q)a\[1]                 / converge1 8 2 5 3 6q)route\[`London]       / stop when back in London`London`Paris`Florence`Milan`Vienna`Berlin

Stephen Taylor | Librarian | Kx | +44 7713 400852 | stephen@kx.com

[Attila]

To: "[kdb+] [kdb+]"
In-Reply-To:
Message-Id:
X-Mailer: Apple Mail (2.3445.6.18)

that looks nice

Do also might be a better name for Repeat as it emphasises the =
imperative analogs (k3 used this terminology for this reason i would =
think)

also i find that enlist / list-creation can be very enlightening about =
adverbs across the board
as it's visual compared to something more arithmetic
to be fair there are a couple of examples like this already on the wiki

Monadic scan/over
q)5 enlist\1
1
,1
,,1
,,,1
,,,,1
,,,,,1

q)5(`f;)\1
1
(`f;1)
(`f;(`f;1))
(`f;(`f;(`f;1)))
(`f;(`f;(`f;(`f;1))))
(`f;(`f;(`f;(`f;(`f;1)))))

Each-es
q)(`f;)each 1 2 3
`f 1
`f 2
`f 3
q)(`f;;)prior 1 2 3
`f 1 0N
`f 2 1
`f 3 2
q)1 2 3(;)/:"abc"
1 2 3 "a"
1 2 3 "b"
1 2 3 "c"
q)1 2 3(;)\:"abc"
1 "abc"
2 "abc"
3 "abc"
q)1 2 3(;)'"abc"
1 "a"
2 "b"
3 "c"
q)1 2 3(;)/:\:"abc"
1 "a" 1 "b" 1 "c"
2 "a" 2 "b" 2 "c"
3 "a" 3 "b" 3 "c"
q)1 2 3(;)\:/:"abc"
1 "a" 2 "a" 3 "a"
1 "b" 2 "b" 3 "b"
1 "c" 2 "c" 3 "c"

scan/over with a function taking more than 2 parameters
q)(`f;;;)/[`x;0 1 2 3;"abcd"]
`f
(`f;(`f;(`f;`x;0;"a");1;"b");2;"c")
3
"d"

etc.

Cheers,
Attila

[sa1]

To: personal-kdbplus@googlegroups.com
In-Reply-To:
Message-Id:
X-Mailer: Apple Mail (2.3273)

this is a lovely thread. thanks guys.

[SJT]

Thanks for the excellent visual examples! 

Do appeals because we have While, so it would mirror the do and while keywords. I’ll give that some thought.

Stephen Taylor | Librarian | Kx | +44 7713 400852 | stephen@kx.com

[effbiae]

using () like
  ({x*x}\)0.1
almost encourages
  (+\)0 1
vs
  sums 0 1
...not that that's a bad thing

On 16 May 2018 at 22:29, Stephen Taylor <stephen@kx.com> wrote:

From a work in progress. Note that f is a unary map, i.e. a unary function or a list or dictionary. See following message for discussion. 

Iterate¶

The Iterate adverb repeatedly evaluates a unary map on first its argument, then successively on the results. It has three forms: Converge, Repeat, and While.

syntax	name	semantics
(f/)d, f/[d] (f\)d, f\[d]	Converge	apply f to d until result converges
n f/d, f/[n;d] n f\d, f\[n;d]	Repeat	apply f to d, n times
t f/d, f/[t;d] t f\d, f\[t;d]	While	apply f to d until t of the result is 0

Key

d: data               n: int atom ≥0        f: unary map          t: unary test map

Equivalent forms with / and \ perform exactly the same computation. Forms with / return the final result; forms with \ return a list of all the results.

If you want only the final result but don’t get the result you expect, replace / with \ to see the intermediate results. They are usually illuminating.

Set \P 0 to see the convergence of your original computation.

Converge¶

Are we there yet?

Apply a map until the result converges.

Syntax: (f/)d, f/[d]
Syntax: (f\)d, f\[d]

Where f is a unary map the derivatives f/ and f\ apply f repeatedly to d until either

• two successive results agree within comparison tolerance
• the result matches d

The latter will save you from some infinite cycles but not all.

q)(not/) 1b0bq)(not/) 42  /never returnsq)(neg\)11 -1q)(rotate[1]\)"abcd""abcd""bcda""cdab""dabc"q)({x*x}\)0.10.1 0.01 0.0001 1e-08 1e-16 1e-32 1e-64 1e-128 1e-256 0q){x*x}\[0.1]   / alternative syntax0.1 0.01 0.0001 1e-08 1e-16 1e-32 1e-64 1e-128 1e-256 0

Repeat¶

Apply a unary map n times.

Syntax: n f/d, f/[n;d]
Syntax: n f\d, f\[n;d]

Where

• f is a unary map
• n is an int atom ≥0
• d is data

the derivatives f/ and f\ return the result of n successive applications of f to d.

f f f … f f f d

q)dbl:2*q)3 dbl/540q)3 dbl\55 10 20 40/first 10+2 numbers of Fibonacci sequenceq)10{x,sum -2#x}/0 1             / derived binary applied infix0 1 1 2 3 5 8 13 21 34 55 89/first n+2 numbers of Fibonacci sequenceq)fibonacci:{x,sum -2#x}/[;0 1]  / projection of derived functionq)fibonacci 100 1 1 2 3 5 8 13 21 34 55 89q)gibonacci:{x,sum -2#x}\[;0 1]  / examine intermediate resultsq)gibonacci 100 10 1 10 1 1 20 1 1 2 30 1 1 2 3 50 1 1 2 3 5 80 1 1 2 3 5 8 130 1 1 2 3 5 8 13 210 1 1 2 3 5 8 13 21 340 1 1 2 3 5 8 13 21 34 550 1 1 2 3 5 8 13 21 34 55 89

Since the domain of n includes 0 you can use this as a form of conditional application.

q)0 dbl/55

While¶

Apply a unary map while a condition remains true.

Syntax: t f/d, f/[t;d]
Syntax: t f\d, f\[t;d]

Where

• f is a unary map
• t is a unary test map
• d is data

the derivatives f/ and f\ return the result of successive applications of f to d until tapplied to it returns zero.

q){x+x}/[{x<1000};2]   /prefix: f/[t;d]1024q){x<1000}{x+x}/2      /infix: t f/d1024q){x<1000}{x+x}\22 4 8 16 32 64 128 256 512 1024q)inc:1+q)inc\[105>;100]100 101 102 103 104 105q)inc\[105>sum@;84 20]84 2085 21

Stephen Taylor | Librarian | Kx | +44 7713 400852 | stephen@kx.com