Adverbs¶
K’s adverbs, like their namesakes in linguistics, determine how a verb is applied to its arguments. We can think of them as advanced functional looping constructs. If you’re familiar with filter, map or reduce from other languages, these would be examples of adverbs in k. The adverbs in k tend to be overloaded on argument types, meaning that some care is required when deciphering code.
In ngn/k, there is a ref-card for adverbs available as \'. The basic adverbs in most ks are each ', reduce /, scan \, each-prior /:, each-right /: and each-left \:, but many more are overloaded on the basic set depending on argument types and valence.
As types matter so much for this, we’ll adopt the following notation, variations of which most ks use in their ref-cards:
[c]har
[i]nt
[n]umber(int|float)
[s]ymbol
[a]tom
[d]ict
[f]unc(monad)
[F]unc(dyad)
[xyz]any
In other words, where we write f' we mean ' applying a monad.
Note
As a stylistic choice, we covered some items that are technically adverbs in the verbs chapter:
encode, decode
split, join
Whilst they’re overloaded on adverb characters, they don’t quite fit the linguistic definition of an adverb - something that affects how a verb is applied. Arguably, window and bin search belong in this group, too.
Each f'¶
Arguably the most fundamental of the adverbs is each, f'. This would be called map in other languages. It returns a vector of the results of applying f to every element in the right argument in turn. It follows that f'x will have the same length as x. For example, let’s count the length of each element in a nested list:
#'(1 2 3 4 5;1 2;7 6 5;,6)
5 2 3 1
Reduce F/, xF/¶
You’re most likely familiar with reduce, too. In k, it’s sometimes also called over, or fold. Reduce is also available in APL on the same symbol, but a huge advantage for k’s version is that it operates left to right, unlike APL’s version which operates right to left: k’s reduce is a so-called foldl. The left to right application of foldl is, for most people, the intuitive behaviour. Reduce is called “reduce” because it reduces the rank of the argument by 1. A list is reduced to a scalar. A matrix is reduced to a vector. A cuboid is reduced to a matrix, etc.
One way to think of reduce is that it interjects its dyadic verb into the gaps between elements in a list. For example, the sum-reduction
+/1 2 3 4 5 6 7 8
36
is equivalent to
1+2+3+4+5+6+7+8
36
or – to be precise – although there is no difference in this case:
(((((((1+2)+3)+4)+5)+6)+7)+8) / foldL
36
K’s reduce also allows you to seed the accumulator, that is, to start from a different value than the first element:
+/!10 / unseeded reduce, accumulator starts set to the first value
99+/!10 / seeded reduce
45
144
Another way to think of the seeding is that its prepending the seed to the list before applying the unseeded version:
+/99,!10
144
Scan F\, xF\¶
Scan is reduce’s brattier little sister. If we think back to reduce we just discussed, scan does the same thing, but instead of returning the final value, it returns the sequence of every intermediate application of F. In other words, the last value returned by scan would be the value returned by reduce if applied to the same data. If you’re familiar with Python’s NumPy, it has a sum-scan primitive built in, called numpy.cumsum. In k, we’d say
+/1+!10 / sum-reduce
+\1+!10 / sum-scan: note that the last element is the sum-reduction
55
1 3 6 10 15 21 28 36 45 55
The elements in the sum-scan +\x is simply x[0], x[0]+x[1], x[0]+x[1]+x[2],…etc. The good news is that in k, a scan is as efficient as a reduce, which isn’t the case in APL.
As with reductions, we can also seed scans in the same way by providing the initial value:
99+\!10 / seeded scan
99 100 102 105 109 114 120 127 135 144
Each-prior F':, xF':¶
If you think back to each above, it applies a monad to every element in turn. Each-prior applies a dyad to every neighbour pairing.
+':1 2 3 4 5 6 7 8 9 / pair-wise sums
1 3 5 7 9 11 13 15 17
The eagle-eyed reader may have spotted that the first element is 1, and that the number of elements in the result is the same as the original argument. Perhaps you would have guessed that it should have started with 3 and have one fewer elements, like the number of panels required for n fence-posts? You’re not alone.
The first element is assumed to be the dyad applied to the prototypal element and the first element; a sort of initial “overhang”. In other words, in the example above, the sequence is
(0+1;1+2;2+3;3+4;4+5;5+6;6+7;7+8;8+9)
1 3 5 7 9 11 13 15 17
Each-prior is an example of a windowed reduction. In other words, in this case, we reduce each pairing to an atom.
As with reduce and scan, each-prior can also be given a seed value, which would be taken as the left argument of the first application (in place of the prototypal element):
9+':1 2 3 4 5 6 7 8 9
10 3 5 7 9 11 13 15 17
Each-left, each-right F\:, F/:¶
K lacks APL’s elegant rank operator, ⍤, but between them, each-left and each_right can do many of the same things. If we have a vector to the left and a vector to the right, each-left allows us to call a dyad with each of the elements to the left, with the whole of the right vector,
1 2 3 4+\:9 9
(10 10
11 11
12 12
13 13)
In other words, each of the elements to the left, plus the whole of the right, like
(1+9 9;2+9 9;3+9 9;4+9 9)
(10 10
11 11
12 12
13 13)
Each-right does the same thing, but in the opposite direction. With each-left and each-right you can approximate APL’s outer product operator, for example, building a “times table” to teach multiplication:
(!11)*\:!11
(0 0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9 10
0 2 4 6 8 10 12 14 16 18 20
0 3 6 9 12 15 18 21 24 27 30
0 4 8 12 16 20 24 28 32 36 40
0 5 10 15 20 25 30 35 40 45 50
0 6 12 18 24 30 36 42 48 54 60
0 7 14 21 28 35 42 49 56 63 70
0 8 16 24 32 40 48 56 64 72 80
0 9 18 27 36 45 54 63 72 81 90
0 10 20 30 40 50 60 70 80 90 100)
Sometimes you even see each-left-each-right /:\:. Here’s a partial example from Advent of Code, 2021, day 2. Let’s say we have a vector that lists a sequence of pairs representing direction and magnitude: [try it]
:d:(("forward";5);("down";5);("forward";8);("up";3);("down";8);("forward";2))
(("forward";5)
("down";5)
("forward";8)
("up";3)
("down";8)
("forward";2))
We want to convert this to a matrix of magnitudes for each step, with separate rows for the three directions. One way we could do this is:
:m:(("forward";"down";"up")~/:\:d[;0])*\:d[;1]
(5 0 8 0 0 2
0 5 0 0 8 0
0 0 0 3 0 0)
The match-each-right-each-left ~/:\: matches each element to the left with each element to the right, as if we’d done the following:
"forward"~/:d[;0]
"down"~/:d[;0]
"up"~/:d[;0]
1 0 1 0 0 1
0 1 0 0 1 0
0 0 0 1 0 0
In the matrix m above, each column represents a move with a magnitude, where the rows are forward, down and up respectively. The problem now asks us to answer the following:
Calculate the horizontal position and depth you would have after following the planned course. What do you get if you multiply your final horizontal position by your final depth?
We can translate that readily to k:
s:+/'m / sum each row
s[0]*s[1]-s[2] / forward sum * (down sum - up sum)
150
For i f/, i f\¶
K has a rich set of functional looping constructs. Perhaps the simplest one is the for loop (APL’s power ⍣i), which calls a monad repeatedly on its own result a set number of times.
5 {x*2}/1 / starting with 1, multiply by 2, 5 times: 2*2*2*2*2*1
32
In naive Python, perhaps you’d written that as
def power(f, v, count):
for i in range(count):
v = f(v)
return v
Flip the slash to a backslash, and (as you may have suspected already) you’ll get the full sequence of intermediate results:
5 {x*2}\1
1 2 4 8 16 32
While f f/, f f\¶
Pass a predicate verb to the left of f/ and we instead have a while loop. It will repeatedly call the monad on its own result as long as the left argument verb, called on the result, returns non-zero.
In Python:
def whileg(f, v, g):
while g(v):
v = f(v)
return v
{x<10}{x*2}/1 / starting with 1, multiply by 2 while the value < 10
16
As with for above, we can get the intermediate values by flipping the slash:
{x<10}{x*2}\1
1 2 4 8 16
Converge f/, f\¶
If we supply no left argument to f/ we end up with converge. This repeatedly applies the monad f to its result until the result is either the starting value, or the previous value. Note that it’s not a good idea to call converge with a function that does not converge.
{1+1.0%x}/1 / the golden mean
1.618033988749895
Converge, with a backslash, returns the intermediates, too:
10#{1+1.0%x}\1 / first 10 values only
(1
2.0
1.5
1.6666666666666665
1.6
1.625
1.6153846153846154
1.619047619047619
1.6176470588235294
1.6181818181818182)
Window i':x¶
Window produces a sliding window of the specified size, returning a vector of shape (1-i-#x;i):
3':!10
(0 1 2
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9)
This can be handy for doing windowed reductions. The sliding sum length 3 from 0-19:
+/'3':!10
3 6 9 12 15 18 21 24
What happens if you use a length 0 window? Well, the result still follows the rule that the shape is (1-i-#X;i):
0':1 2 3 4
0':"hello"
0':(1 2 3;4 5 6;7 8 9)
0':2 3 5#5
(!0
!0
!0
!0
!0)
(""
""
""
""
""
"")
(()
()
()
())
(()
()
())
Stencil i f':¶
Stencil is similar to window, but it applies the monad to the window. We did a sliding windowed sum above as
+/'3':!10 / window, then sum
3 6 9 12 15 18 21 24
This can be more efficiently expressed as a stenciled sum:
3+/':!10 / stencil sum
3 6 9 12 15 18 21 24
The stencil version avoids having to first generate the windows, and then applying the monad to each of them.
Bin search X'¶
Bin search is a binning algorithm – given a set of ranged bins, it picks the bin corresponding to the arguments. This is what an APLer or NumPyer would call interval index. Here’s how it works:
1 3 5 7 9'8 9 0 / bin 8, 9 and 0 over the intervals 1 3 5 7 9
3 4 -1
Consider the gaps between the elements to the left. The first interval is then [1, 3), the second is [3, 5), the third is [5, 7) etc. An element belongs to the bin where it is greater than or equal to the lower end, and less than the upper end.
1 3 5 7 9'5 / elements on on boundary goes in the higher bin
2
Elements smaller than the first bin goes in the -1 bin, which is assumed to cover every number lower than the first bin. Similarly, elements greater than the last bin will end up with a bin number equal to the number of elements (note: not the number of bins) to the left:
3 5 7 9'0 100
-1 3
It works for other types, too:
"AEIOU"'"HELLO WORLD"
1 1 2 2 3 -1 4 3 3 2 0
In other words, “H” comes on or after “E” but not after “I”, “E” is on or after “E” etc.
Typical use cases for bin search involves various kinds of classification. For example, in the UK, alcoholic beverages are taxed based on their alcohol by volume (abv) percentage. Let’s consider cider and perry:
Class or description |
Tax type code |
Rate of excise duty/hl |
|---|---|---|
abv does not exceed 1.2% |
431 |
£0 |
abv exceeding 1.2% but less than 6.9% |
481 |
£40.38 |
abv at least 6.9% but not exceeding 7.5% |
487 |
£50.71 |
abv at least 7.5% but not exceeding 8.5% |
483 |
£61.04 |
Given the following ciders with the associated abv, what are their respective tax code and tax rate per hecto-litre? [try it]
ciders: ("Kopparberg Sparkling Rose";"Bulmers Original";"Crispin the Jacket";"Old Mout Cherries & Berries")
abv: 7.0 4.5 8.3 0.0
Let’s encode the table above into a set of vectors first:
code:431 481 487 486
rate:0 40.38 50.71 61.04
limits:1.2 6.9 7.5 8.5
Let’s find the bins from the limits, and add one to capture the -1 bin appropriately:
:bin:1+limits'abv
2 1 3 0
Now we can lay out a nice table:
+(ciders;rate bin;code bin)
(("Kopparberg Sparkling Rose";50.71;487)
("Bulmers Original";40.38;481)
("Crispin the Jacket";61.04;486)
("Old Mout Cherries & Berries";0.0;431))
\h
: SET RETURN ' each|slide|bin
+ add flip / fold|join |dec
- subtract negate \ scan|split|enc
* multiply first ': eachprior
% divide sqrt /: eachright
! mod|dict enum|key \: eachleft
& min|and where
| max|or reverse
< less ascend 0: lines i/o
> more descend 1: bytes i/o
= equal group
~ match not
, concat enlist
^ without null
# reshape length
_ drop|cut floor
$ cast string $[c;t;f] COND
? find|rnd uniq
@ apply(1) type @[x;i;[f;]y] amend
. apply(n) eval .[x;i;[f;]y] drill
grammar: E:E;e|e e:nve|te| t:n|v v:tA|V n:t[E]|(E)|{E}|N
\
\ help \\ exit
\a license(AGPLv3) \l file.k load
\0 types \t:n expr time(elapsed milliseconds after n runs)
\+ verbs \v variables
\: I/O verbs \f functions
\' adverbs \cd path change directory
\` symbols \other command(through /bin/sh)
\h summary
\:
I/O verbs
0:x read lines
x 0:y write lines
1:x read bytes
x 1:y write bytes
<s open fd:<`"file.txt"
>i close >fd
x can be a file descriptor (int) or symbol or string such as
"file.txt"
"/path/to/file"
"host:port"
":port" /host defaults to 127.0.0.1
\`
Special symbols:
`@x serialize ` 7 8 9 -> 0x020300000000000000070809
`?C deserialize `?0x020300000000000000070809 -> 7 8 9
`j?C parse json `j?"{\"a\":1,\"b\":[true,\"c\"]}" -> `a`b!(1.0;(1;,"c"))
`k@x pretty-print `k("ab";2 3) -> "(\"ab\";2 3)"
`p@C parse k
`hex@C hexadecimal `hex"ab" -> "6162"
`x@x fork-exec `x(("/bin/wc";"-l");"a\nbc\nd\n") -> "3\n"
`t[] current time (microseconds)
`argv[] list of cmd line args
`env[] dict of env variables
`prng[] `prng@I get/set pseudo-random number generator internal state
s:`prng[];r:9?0;`prng s;r~9?0 -> 1
`prng@0 use current time to set state
`err@C throw error
Special symbols available only in an interpreter built with "make k-libc":
`sin@N trigonometry `sin 12.34 -> -0.22444212919135995
`exp@N exponential `exp 1 -> 2.7182818284590455
`ln@N logarithm `ln 2 -> 0.6931471805599453
\'
Adverbs: ' / \ ': /: \:
f' each1 #'("abc";3 4 5 6) -> 3 4
x F' each2 2 3#'"ab" -> ("aa";"bbb")
X' binsearch 1 3 5 7 9'8 9 0 -> 3 4 -1
F/ fold +/1 2 3 -> 6
F\ scan +\1 2 3 -> 1 3 6
x F/ seeded / 10+/1 2 3 -> 16
x F\ seeded \ 10+\1 2 3 -> 11 13 16
i f/ n-do 5(2*)/1 -> 32
i f\ n-dos 5(2*)\1 -> 1 2 4 8 16 32
f f/ while (1<){$[2!x;1+3*x;-2!x]}/3 -> 1
f f\ whiles (1<){$[2!x;1+3*x;-2!x]}\3 -> 3 10 5 16 8 4 2 1
f/ converge {1+1.0%x}/1 -> 1.618033988749895
f\ converges (-2!)\100 -> 100 50 25 12 6 3 1 0
C/ join "ra"/("ab";"cadab";"") -> "abracadabra"
C\ split "ra"\"abracadabra" -> ("ab";"cadab";"")
I/ decode 24 60 60/1 2 3 -> 3723 2/1 1 0 1 -> 13
I\ encode 24 60 60\3723 -> 1 2 3 2\13 -> 1 1 0 1
i': window 3'"abcdef" -> ("abc";"bcd";"cde";"def")
i f': stencil 3{x,"."}':"abcde" -> ("abc.";"bcd.";"cde.")
F': eachprior -':12 13 11 17 14 -> 12 1 -2 6 -3
x F': seeded ': 10-':12 13 11 17 14 -> 2 1 -2 6 -3
x F/: eachright 1 2*/:3 4 -> (3 6;4 8)
x F\: eachleft 1 2*\:3 4 -> (3 4;6 8)
\+
Verbs: : + - * % ! & | < > = ~ , ^ # _ $ ? @ . 0: 1:
notation: [c]har [i]nt [n]umber(int|float) [s]ymbol [a]tom [d]ict
[f]unc(monad) [F]unc(dyad) [xyz]any
special: var:y set a:1;a -> 1
(v;..):y unpack (b;(c;d)):(2 3;4 5);c -> 4
:x return {:x+1;2}[3] -> 4
$[x;y;..] cond $[0;`a;"\0";`b;`;`c;();`d;`e] -> `e
o[..] recur {$[x<2;x;+/o'x-1 2]}9 -> 34
[..] progn [0;1;2;3] -> 3
:: self ::12 -> 12
: right 1 :2 -> 2 "abc":'"d" -> "ddd"
+x flip +("ab";"cd") -> ("ac";"bd")
N+N add 1 2+3 -> 4 5
-N negate - 1 2 -> -1 -2
N-N subtract 1-2 3 -> -1 -2
*x first *`a`b -> `a *(0 1;"cd") -> 0 1
N*N multiply 1 2*3 4 -> 3 8
%N sqrt %25 -> 5.0 %-1 -> 0n
N%N divide 4 3%2 -> 2 1 4 3%2.0 -> 2.0 1.5
!i enum !3 -> 0 1 2 !-3 -> -3 -2 -1
!I odometer !2 3 -> (0 0 0 1 1 1;0 1 2 0 1 2)
!d keys !`a`b!0 1 -> `a`b
!S ns keys a.b.c:1;a.b.d:2;!`a`b -> ``c`d
x!y dict `a`b!1 2 -> `a`b!1 2
i!I div -10!1234 567 -> 123 56
i!I mod 10!1234 567 -> 4 7
&I where &3 -> 0 0 0 &1 0 1 4 2 -> 0 2 3 3 3 3 4 4
&x deepwhere &(0 1 0;1 0 0;1 1 1) -> (0 1 2 2 2;1 0 0 1 2)
N&N min/and 2&-1 3 -> -1 2 0 0 1 1&0 1 0 1 -> 0 0 0 1
|x reverse |"abc" -> "cba" |12 -> 12
N|N max/or 2|-1 3 -> 2 3 0 0 1 1|0 1 0 1 -> 0 1 1 1
<X ascend <"abacus" -> 0 2 1 3 5 4
>X descend >"abacus" -> 4 5 3 1 0 2
<s open fd:<`"/path/to/file.txt"
>i close >fd
N<N less 0 2<1 -> 1 0
N>N more 0 1>0 2 -> 0 0
=X group ="abracadabra" -> "abrcd"!(0 3 5 7 10;1 8;2 9;,4;,6)
=i unitmat =3 -> (1 0 0;0 1 0;0 0 1)
N=N equal 0 1 2=0 1 3 -> 1 1 0
~x not ~(0 2;``a;"a \0";::;{}) -> (1 0;1 0;0 0 1;1;0)
x~y match 2 3~2 3 -> 1 "4"~4 -> 0 0~0.0 -> 0
,x enlist ,0 -> ,0 ,0 1 -> ,0 1 ,`a!1 -> +(,`a)!,,1
x,y concat 0,1 2 -> 0 1 2 "a",1 -> ("a";1)
^x null ^(" a";0 1 0N;``a;0.0 0n) -> (1 0;0 0 1;1 0;0 1)
a^y fill 1^0 0N 2 3 0N -> 0 1 2 3 1 "b"^" " -> "b"
X^y without "abracadabra"^"bc" -> "araadara"
#x length #"abc" -> 3 #4 -> 1 #`a`b`c!0 1 0 -> 3
i#y reshape 3#2 -> 2 2 2
I#y reshape 2 3#` -> (```;```)
f#y replicate (3>#:')#(0;2 1 3;5 4) -> (0;5 4) {2}#"ab" -> "aabb"
x#d take `c`d`f#`a`b`c`d!1 2 3 4 -> `c`d`f!3 4 0N
_n floor _12.34 -12.34 -> 12 -13
_c lowercase _"Ab" -> "ab"
i_Y drop 2_"abcde" -> "cde" `b_`a`b`c!0 1 2 -> `a`c!0 2
I_Y cut 2 4 4_"abcde" -> ("cd";"";,"e")
f_Y weed out (3>#:')_(0;2 1 3;5 4) -> ,2 1 3
X_i delete "abcde"_2 -> "abde"
$x string $(12;"ab";`cd;+) -> ("12";(,"a";,"b");"cd";,"+")
i$C pad 5$"abc" -> "abc " -3$"a" -> " a"
s$y cast `c$97 -> "a" `i$-1.2 -> -1 `$"a" -> `a
s$y int `I$"-12" -> -12
?x uniq ?"abacus" -> "abcus"
X?y find "abcde"?"bfe" -> 1 0N 4
i?x roll 3?1000 -> 11 398 293 1?0 -> ,-8164324247243690787
i?x deal -3?1000 -> 11 398 293 /guaranteed distinct
@x type @1 -> `b @"ab" -> `C @() -> `A @(@) -> `v
x@y apply(1) {x+1}@2 -> 3 "abc"@1 -> "b" (`a`b!0 1)@`b -> 1
.S get a:1;.`a -> 1 b.c:2;.`b`c -> 2
.C eval ."1+2" -> 3
.d values .`a`b!0 1 -> 0 1
x.y apply(n) {x*y+1}. 2 3 -> 8 (`a`b`c;`d`e`f). 1 0 -> `d
@[x;y;f] amend @["ABC";1;_:] -> "AbC" @[2 3;1;{-x}] -> 2 -3
@[x;y;F;z] amend @["abc";1;:;"x"] -> "axc" @[2 3;0;+;4] -> 6 3
.[x;y;f] drill .[("AB";"CD");1 0;_:] -> ("AB";"cD")
.[x;y;F;z] drill .[("ab";"cd");1 0;:;"x"] -> ("ab";"xd")
.[f;y;f] try .[+;1 2;"E:",] -> 3 .[+;1,`2;"E:",] -> "E:typ"
?[x;y;z] splice ?["abcd";1 3;"xyz"] -> "axyzd"