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)
Copy to clipboard
5 2 3 1
Copy to clipboard

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
Copy to clipboard
36
Copy to clipboard

is equivalent to

1+2+3+4+5+6+7+8
Copy to clipboard
36
Copy to clipboard

or – to be precise – although there is no difference in this case:

(((((((1+2)+3)+4)+5)+6)+7)+8)    / foldL
Copy to clipboard
36
Copy to clipboard

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
Copy to clipboard
45
144
Copy to clipboard

Another way to think of the seeding is that its prepending the seed to the list before applying the unseeded version:

+/99,!10
Copy to clipboard
144
Copy to clipboard

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
Copy to clipboard
55
1 3 6 10 15 21 28 36 45 55
Copy to clipboard

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
Copy to clipboard
99 100 102 105 109 114 120 127 135 144
Copy to clipboard

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
Copy to clipboard
1 3 5 7 9 11 13 15 17
Copy to clipboard

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)
Copy to clipboard
1 3 5 7 9 11 13 15 17
Copy to clipboard

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
Copy to clipboard
10 3 5 7 9 11 13 15 17
Copy to clipboard

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
Copy to clipboard
(10 10
 11 11
 12 12
 13 13)
Copy to clipboard

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)
Copy to clipboard
(10 10
 11 11
 12 12
 13 13)
Copy to clipboard

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
Copy to clipboard
(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)
Copy to clipboard

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]

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:

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:

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:

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
Copy to clipboard
32
Copy to clipboard

In naive Python, perhaps you’d written that as

def power(f, v, count):
    for i in range(count):
        v = f(v)
    return v
Copy to clipboard

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
Copy to clipboard
1 2 4 8 16 32
Copy to clipboard

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
Copy to clipboard
{x<10}{x*2}/1  / starting with 1, multiply by 2 while the value < 10
Copy to clipboard
16
Copy to clipboard

As with for above, we can get the intermediate values by flipping the slash:

{x<10}{x*2}\1 
Copy to clipboard
1 2 4 8 16
Copy to clipboard

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
Copy to clipboard
1.618033988749895
Copy to clipboard

Converge, with a backslash, returns the intermediates, too:

10#{1+1.0%x}\1    / first 10 values only              
Copy to clipboard
(1
 2.0
 1.5
 1.6666666666666665
 1.6
 1.625
 1.6153846153846154
 1.619047619047619
 1.6176470588235294
 1.6181818181818182)
Copy to clipboard

Window i':x

Window produces a sliding window of the specified size, returning a vector of shape (1-i-#x;i):

3':!10
Copy to clipboard
(0 1 2
 1 2 3
 2 3 4
 3 4 5
 4 5 6
 5 6 7
 6 7 8
 7 8 9)
Copy to clipboard

This can be handy for doing windowed reductions. The sliding sum length 3 from 0-19:

+/'3':!10
Copy to clipboard
3 6 9 12 15 18 21 24
Copy to clipboard

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
Copy to clipboard
(!0
 !0
 !0
 !0
 !0)
(""
 ""
 ""
 ""
 ""
 "")
(()
 ()
 ()
 ())
(()
 ()
 ())
Copy to clipboard

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
Copy to clipboard
3 6 9 12 15 18 21 24
Copy to clipboard

This can be more efficiently expressed as a stenciled sum:

3+/':!10    / stencil sum
Copy to clipboard
3 6 9 12 15 18 21 24
Copy to clipboard

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
Copy to clipboard
3 4 -1
Copy to clipboard

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
Copy to clipboard
2
Copy to clipboard

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
Copy to clipboard
-1 3
Copy to clipboard

It works for other types, too:

"AEIOU"'"HELLO WORLD"
Copy to clipboard
1 1 2 2 3 -1 4 3 3 2 0
Copy to clipboard

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]

Let’s encode the table above into a set of vectors first:

Let’s find the bins from the limits, and add one to capture the -1 bin appropriately:

Now we can lay out a nice table:

\h
Copy to clipboard
: 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
Copy to clipboard
\
Copy to clipboard
\   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
Copy to clipboard
\:
Copy to clipboard
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
Copy to clipboard
\`
Copy to clipboard
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
Copy to clipboard
\'
Copy to clipboard
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)
Copy to clipboard
\+
Copy to clipboard
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"
Copy to clipboard