Hi KDB gurus, can anyone please explain the meaning of the expression: x('[min;+])/: x, especially the function composition '[min;+] and its use with /:, here x is a matrix. TIA!
Hello Bhavya,
/: is the each-right operator, you can see the documentation at https://code.kx.com/q/ref/maps/#each-left-and-each-right
The ’ is the compose operator, hence you are composing a function over something.
Finally, we can read the function x('[min;+])/: x as "find the minimum element of x and add this to all elements in x.
Hope it helps, regards.
It only makes sense for square matrices. Here are some equivalents which I hope provide clarity:
x {min x+y}/: x
{min x+y}[x;] each x
(min +[x;]@) each x
(math)
r_{i,*} = min_j x_{i,j} + x_{j,*}
(python)
result =
for r in x:
candidates =
for i in range(len(r)):
candidates.append([v+r[i] for v in x[i]])
result.append(min(candidates)) # lexographical min
result
It’s the same as
{min each x+/:x}
Could possibly be an implementation of min-plus matrix multiplication? Not sure on that.
Terry
Thanks a lot for explaining with the alternate forms of the expression. It is indeed min plus matrix multiplication used in finding the shortest distance between nodes(ref: https://code.kx.com/q/kb/lp/).
I am more interested in understanding the idea behind the original expression, basically ‘[min;+] part in x(’[min;x])/: x, as in why and how it is expanding to “min each x +/: x”.
All help appreciated!
The usage of the single quote here is as the compose operator (https://code.kx.com/q/ref/compose/), which takes two functions and composes them into one, applying the second argument followed by the first.
In this specific case '[min;+] is a function of rank two (matching +), which sums the two inputs and returns the min of the result.
In fact, compositions have a special type in q: https://code.kx.com/q/basics/datatypes/
q)type ('[min;+])
105h