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?

[Terry Lynch]

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

On Wed, May 16, 2018, 07:05 QUser <nathan....@gmail.com> wrote:

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?

--
You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbpl...@googlegroups.com.
To post to this group, send email to personal...@googlegroups.com.
Visit this group at https://groups.google.com/group/personal-kdbplus.
For more options, visit https://groups.google.com/d/optout.

[Stephen Taylor]

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/) 1b
0b
q)(not/) 42  /never returns
q)(neg\)1
1 -1
q)(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
q){x*x}\[0.1]   / alternative syntax
0.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/5
40
q)3 dbl\5
5 10 20 40
/first 10+2 numbers of Fibonacci sequence
q)10{x,sum -2#x}/0 1             / derived binary applied infix
0 1 1 2 3 5 8 13 21 34 55 89
/first n+2 numbers of Fibonacci sequence
q)fibonacci:{x,sum -2#x}/[;0 1]  / projection of derived function
q)fibonacci 10
0 1 1 2 3 5 8 13 21 34 55 89
q)gibonacci:{x,sum -2#x}\[;0 1]  / examine intermediate results
q)gibonacci 10
0 1
0 1 1
0 1 1 2
0 1 1 2 3
0 1 1 2 3 5
0 1 1 2 3 5 8
0 1 1 2 3 5 8 13
0 1 1 2 3 5 8 13 21
0 1 1 2 3 5 8 13 21 34
0 1 1 2 3 5 8 13 21 34 55
0 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/5
5

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]
1024
q){x<1000}{x+x}/2      /infix: t f/d
1024
q){x<1000}{x+x}\2
2 4 8 16 32 64 128 256 512 1024
q)inc:1+
q)inc\[105>;100]
100 101 102 103 104 105
q)inc\[105>sum@;84 20]
84 20
85 21

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

On 16 May 2018 at 12:24, Terry Lynch <tlyn...@gmail.com> wrote:

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

On Wed, May 16, 2018, 07:05 QUser <nathan....@gmail.com> wrote:

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?

--
You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
To post to this group, send email to personal-kdbplus@googlegroups.com.

Visit this group at https://groups.google.com/group/personal-kdbplus.
For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
To post to this group, send email to personal-kdbplus@googlegroups.com.

[Stephen Taylor]

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 map
n: integer ≥0
t: unary map with 0 in its range
y: 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]
512f
q)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 16
128 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 16
512  8
256  4
128  2

The binary derivative is often applied infix.

q)3 halve\1024 16
1024 16
512  8
256  4
128  2
q)10{x,sum -2#x}/0 1           / first 10+2 numbers of Fibonacci sequence
0 1 1 2 3 5 8 13 21 34 55 89

Lists and dictionaries are also unary maps.

q)show double:2*til 10
0 2 4 6 8 10 12 14 16 18
q)double double double 2 1
16 8
q)3 double/2 1
16 8
q)route                        / European tour route
Berlin  | London
Florence| Milan
London  | Paris
Paris   | Florence
Milan   | Vienna
Vienna  | Berlin
q)3 route\`London              / fly three stages, start London
`London`Paris`Florence`Milan
q)3 route\`London`Vienna       / start London - or Vienna
London   Vienna
Paris    Berlin
Florence London
Milan    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 5
1 4 7 10
q)<>[;`London] route\`Paris                 / start in Paris, stop in London
`Paris`Florence`Milan`Vienna`Berlin`London
q)<>[;`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 4
q)t (3+)\1
1 4 7 10
q)waypoints
Berlin  | 1
Florence| 1
Milan   | 1
Paris   | 1
Vienna  | 1
q)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\)1
1 -1
q)(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)a
1 8 5 6 0 3 6 4 2 9
q)10 a\1                / repeat
1 8 2 5 3 6 6 6 6 6 6
q)a\[1]                 / converge
1 8 2 5 3 6
q)route\[`London]       / stop when back in London
`London`Paris`Florence`Milan`Vienna`Berlin

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

[Jack Andrews]

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

[Attila Vrabecz]

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

> 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/) 1b
> 0b
>
> q
> )(not/) 42 /never returns
>
> q
> )(neg\)1
> 1 -1
>
> q

> )(rotate[1]\)"abcd"
> "abcd"
> "bcda"
> "cdab"
> "dabc"
>
> q

> To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbpl...@googlegroups.com.
> To post to this group, send email to personal...@googlegroups.com.

> Visit this group at https://groups.google.com/group/personal-kdbplus.
> For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbpl...@googlegroups.com.
> To post to this group, send email to personal...@googlegroups.com.

> Visit this group at https://groups.google.com/group/personal-kdbplus.
> For more options, visit https://groups.google.com/d/optout.
>
>
>
> --
> You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbpl...@googlegroups.com.
> To post to this group, send email to personal...@googlegroups.com.

[stevan apter]

this is a lovely thread. thanks guys.

[Stephen Taylor]

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 | ste...@kx.com

> To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
> To post to this group, send email to personal-kdbplus@googlegroups.com.

> Visit this group at https://groups.google.com/group/personal-kdbplus.
> For more options, visit https://groups.google.com/d/optout.
>
> --
> You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
> To post to this group, send email to personal-kdbplus@googlegroups.com.

> Visit this group at https://groups.google.com/group/personal-kdbplus.
> For more options, visit https://groups.google.com/d/optout.
>
>
>
> --
> You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
> To post to this group, send email to personal-kdbplus@googlegroups.com.

> Visit this group at https://groups.google.com/group/personal-kdbplus.
> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "Kdb+ Personal Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to personal-kdbplus+unsubscribe@googlegroups.com.
To post to this group, send email to personal-kdbplus@googlegroups.com.