cancel
Showing results for
Did you mean:

## Iterate/Converge syntax Question New Contributor
`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?
7 REPLIES 7 New Contributor II
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  Valued Contributor
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.

syntaxnamesemantics
`(f/)d`, `f/[d]`
`(f\)d`, `f\[d]`
Convergeapply `f` to `d` until result converges
`n f/d`, `f/[n;d]`
`n f\d`, `f\[n;d]`
Repeatapply `f` to `d`, `n` times
`t f/d`, `f/[t;d]`
`t f\d`, `f\[t;d]`
Whileapply `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¶

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

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

``q)(not/) 1b0bq)(not/) 42  /never returnsq)(neg\)11 -1q)(rotate\)"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 `t`applied 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  Valued Contributor

# 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.

syntaxsemantics
`(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)halve512fq)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 `t`returns 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\)"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\                 / 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 New Contributor

To: "[kdb+] [kdb+]"
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 =
as it's visual compared to something more arithmetic
to be fair there are a couple of examples like this already on the wiki

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 New Contributor

Message-Id:
X-Mailer: Apple Mail (2.3273)

this is a lovely thread. thanks guys.  Valued Contributor
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 New Contributor
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 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.

syntaxnamesemantics
`(f/)d`, `f/[d]`
`(f\)d`, `f\[d]`
Convergeapply `f` to `d` until result converges
`n f/d`, `f/[n;d]`
`n f\d`, `f\[n;d]`
Repeatapply `f` to `d`, `n` times
`t f/d`, `f/[t;d]`
`t f\d`, `f\[t;d]`
Whileapply `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¶

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

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

``q)(not/) 1b0bq)(not/) 42  /never returnsq)(neg\)11 -1q)(rotate\)"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 `t`applied 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 