cancel
Showing results for 
Search instead for 
Did you mean: 

Iterate/Converge syntax Question

QUser
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

TerryLynch
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


SJT
Valued Contributor
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

St Patrick driving the snakes out of IrelandAre 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

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




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





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

this is a lovely thread. thanks guys.

SJT
Valued Contributor
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

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

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

St Patrick driving the snakes out of IrelandAre 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

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