{{ message }}

Instantly share code, notes, and snippets.

# chrispsn/k_tech_tree.md

Last active Aug 21, 2021
k tech tree

# k tech tree

Thought experiment:

Which k primitives can be implemented as k-strings, reasonably efficiently, with a handful of 'native' built-ins?

Not verified to be in dependency order yet... may depend on the choice of 'fundamental' primitives. Need to do speed tests too.

k9 syntax (download via Shakti). Got a better way to write one? Feel free to comment, you'll be credited!

`A` = any atom, `L` = list (generic or typed), `i` = int atom, `I` = int list, `M` = conforming list of lists.

You may also like @kcodetweets and the k tree chatroom.

## What should we assume?

• Numeric primitives `+-*%` - we'll see about whether they apply beyond atoms. `intdiv mod bar`?
• Bracket indexing?
• Compositions/projections/lambdas?

## Some strategies that could be useful

• Recursive functions (slow without tail recursion?)
• Mutually recursive functions, eg one that handles atoms, but relies on another function to handle lists/dicts
• Implement recursion via k-strings (ngn's y-c: `Y:{x x}{x{x[x]y}y}@` or recursive helper functions (example))

## range (`!i`)

Maybe something recursive could avoid the drop (`_`)? In many implementations drop-from-end (`-1_`) can be done in constant time.

`````` r:{-1_x(1+)\:0}  / doesn't work in k9 yet, but {-1_x(1+)\0} does in k7
r 5
0 1 2 3 4
r 0
!0
-1_(1+)\[;0]5    / tacit (again, k7):
0 1 2 3 4

{x(0,1+)/`i\$()}5 / another that works in k7 but not k9 yet
0 1 2 3 4
(0,1+)/[;`i\$()]5 / same but not a lambda. again, k7
0 1 2 3 4
``````

A couple from Traws 1, 2

``````{-1+\:x#1}
{(-1+0&x)+\x#1}      / chrispsn extending to negative range
{-1+\x(1,)/:`i\$()}
``````

`&&0,` richie - or `{&&(0;x)}` if we assume comma isn't available

`&~&` chrispsn, riffing off richie's answer above

`{&x#1}` icsa

## count (`#L`)

ngn/coltim

`````` c: {[x;y]x+1}/0,
c 2 1 3
3
c ()
0
c 7
1
``````

## first (`*L`)

`````` {x}"hello"
"h"
{x}""
" "
``````

## at (`@`)

`````` at: {x .,y}
at["hello";0 4 2 1]
"hole"
``````

## reverse (`|L`)

Needs a dict implementation.

`````` {x@(#x)-1+!#x}"hello"
"olleh"
``````

## take (`i#L`)

(idle thought: what if take generated indices instead, and we skipped the `x@`...)

Negative `i>#x` case needs correcting (or does it?).

Needs a dict implementation.

`````` {x@(#x)\\$[y<0; (y+#x)+!-y; !y]}["hello";3]
"hel"
{x@(#x)\\$[y<0; (y+#x)+!-y; !y]}["hello";-3]
"llo"
{x@(#x)\\$[y<0; (y+#x)+!-y; !y]}["hello";8]
"hellohel"
``````

## where (`&I`)

I feel like there's more to be done here - none of these get close to the builtin speed. Others are less sure...

icendoan/yiyus. Probably the most natural way to write it, and fast too.

`````` {,/\$[2=#\$@x;x[!x]#'!x;x#'!#x]}2 1 3
0 0 1 2 2 2
{,/\$[2=#\$@x;x[!x]#'!x;x#'!#x]}@ [a:1;b:0;c:3]
`a`c`c`c
``````

richie - avoids take. Minor tweak from chrispsn:

`````` {-1+,/l+!#l:-1<!',/,x}1 0 2
0 2 2
``````

Another from richie that assumes cat, count, range:

`````` {,/{:[;x]'!y}'[!#x;x]}
``````

A couple of rewrites of above by chrispsn (replace `&'` with `!'` if atom case of `&` isn't available):

`````` {,/ :\:'[&'x;!#x]}
,/(:\:').(&';!#)@\:
``````

ngn - avoids catenation:

`````` {+/~(+\x)>\!+/x|:0}1 0 2
0 2 2
``````

ngn, clever use of a step function:

``````{1+(`step(-1,+\x)!-1,!#x)@!+/x:0|\$[x~*x;,;]x}
``````

chrispsn, assumes `000b ~ &3` as base behaviour:

`````` {,/(!#x)+&'x}2 1 0 3
0 0 1 3 3 3

,/+/(&';!#)@\:  / tacit take on above

/ similar but each-less:
{,/(!#x)+(:':x)^&:/x:+\x} 2 1 0 3
0 0 1 3 3 3
``````

chrispsn - less nesting but currently broken for cases ending in `0`. Uses `(+/x)#0`, but could also recurse to the atom case of where (`&+/x`), which is currently (2020.04.17) a little slower:

``````{|\@[(:/v)#0; -1_v:+\x; :; 1_!#x]}
``````

Another, but more each-y:

``````{@[(:/v)#0; (-1_v:+\x)+1_!'x; :; 1_!#x]}
``````

If known to be boolean (and for all input in ngn/k) we can use filter:

`````` {:[;x]#!#x} 1 0 1 1 0
0 2 3
``````

BTW, where inverse from the Shakti Google Group...

## find (`L?L` or `L?A`)

Needs a dict implementation.

`````` {(&/(#x),&)'y~'\x}["abcd";"cbe"]
2 1 4
``````

ngn mentioned an optimisation that can apply if `x` is a list of non-negative atoms (chars; unsigned ints):

`````` / x is unique; show 0N for miss
{@[(1+|/x)#0N;x;:;!#x]y}

/ x is not necessarily unique; show #x for miss
{@[i#i:1+|/x;x;&;!#x]y}
``````

## unique (`?L`)

room to optimise further: https://chat.stackexchange.com/transcript/90748?m=53935363#53935363

`````` {x@&(!#x)=x?x} "abracadabra"
"abrcd"
"abrcd"
``````

chrispsn:

`````` {\$[x;x@i@<i@:&@[~~':x@i:<x;0;:;1];x]}
{\$[x;{@[(~':x@i)@<i:<x;0;:;0]}_x;x]}
*'-1_{x^*x}\  / assumes ^ as except; not well tested
``````

coltim's low-dependency approach:

`````` {(0#x){\$[0|/x~\:y;x;x,,y]}/x}
``````

coltim's dict merge approach with chrispsn tweak:

`````` {\$[x;!,/(,'x)!'x;x]}
``````

## group (`= map`)

chrispsn:

`````` {\$[x; {v:(a:&@[~~':x@i;0;:;1])_i:<x; x[*'v]!v@:<i@a}x; x!()]}
``````

Need one for dicts.

## cut (`L^L`)

`````` cut:{x{x@y+!z-y}[y]'1_x,#y}
cut[1 2 5;"gremlins"]
(,"r"
"eml"
"ins")
``````

## flip (`+M`)

ktye's, with tweaks from ngn:

`````` {(,/n#'x)(n*!#x)+/:!n:|/#'x}("ab";"c";"de")
acd
bce
``````

Or a much shorter, but sometimes much slower, one from Attila:

`````` ,'/("ab";"c";"de")
acd
bce
``````

## odometer (`I`)

`````` {x((*a)#&#)'1_a:|*\|x,1}2 1 4
0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0
0 1 2 3 0 1 2 3
``````

John Earnest / possibly early k5: https://chat.stackexchange.com/transcript/message/58561596#58561596

`````` f:{+x\'!*/x}
f 2 1 4
(0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0
0 1 2 3 0 1 2 3)
``````

## permutations `prm` (takes `i` as input)

`````` {?<'+!x#x}3   / brute - likely discovered by John Earnest: https://chat.stackexchange.com/transcript/message/54070438#54070438
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

o:(>,)/'+!1+!  / modify
o 3
1 0 2
1 2 0
2 1 0
0 1 2
0 2 1
2 0 1

p:{(,/@\)/,\(,<<)'(!x)=/!x}  / iterate (original had =i for identity matrix; here replaced with (!x)=/!x )
p 3
0 1 2
1 0 2
1 2 0
0 2 1
2 0 1
2 1 0
``````

phineas's conversion of "At play with J": https://code.jsoftware.com/wiki/Doc/Articles/Play121

`````` {y,'x+~x<y}/!1+!
0 1 2
1 0 2
2 0 1
0 2 1
1 2 0
2 1 0
``````
`````` p:{(,&y##*x),,/'+x+/x>/-1+!y}/(,0 1#0),1+!
p 3
0 0 1 1 2 2
1 2 0 2 0 1
2 1 2 0 1 0
``````

dzaima - super-fast, not in lexicographic order:

`````` p: {,/'@[;y,!y]\:x,,(#*x)#y}/(,0 1#0),!
p 3
0 1 1 0 2 2
2 2 0 1 1 0
1 0 2 2 0 1
``````

## rotate

Shakti mailing list ~2019-04-09:

Arthur:

`````` {\$[0<x;(x_y),x#y;(x#y),x_y]}[3;"hello"]
"lohel"
``````

Attila:

`````` {,/|(0;(#y)\x)^y}[3;"hello"]
"lohel"
``````

2021-08-04, chrispsn (dicey if `mod` doesn't work on negative numbers):

`````` {y L mod x+!L:#y}[3;"hello"]
"lohel"
{(l mod(l:#y)-x;{(:/x):':x})/:y}[3;"hello"]
"lohel"
``````

## shape

John Earnest (assumes rectangular):

`````` shape: -1_#'*\:
shape ("hello";"world")
2 5
``````

## split (on atom) (`c\C`)

chrispsn (note: more like a trimmed version of split, since it doesn't split twice on doubles):

`````` split:{y(-2{1<x-y}':)^&~x=y}
split[" "; "ab cd e"]
ab
cd
e
``````

## Other languages

### icsa commented Apr 13, 2020 • edited

N.B. Using k4/k7 syntax, atm

### where `&x`

`{,/x#''!#x}`

{&x#1}

### group `=x`

`{d!(d:?x)?/:x}`

### ktye commented Apr 13, 2020 • edited

 find: `{(&/(#x),&)'y~'\x}` how about `x=/y` instead of `y~'\x`?

### chrispsn commented Apr 13, 2020

 Doesn't it need to match for nested structures? I agree equal can be used for ints, strings etc … On Tue, 14 Apr 2020 at 6:19 am, ktye ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ find: {(&/(#x),&)'y~'\x} how about y=\x instead of y~'\x? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub , or unsubscribe .

### group `=x`

`{d!(d:?x)?/:x}`

I think I see what this one is getting at, but will the find (`?/:`) only get the first index, not all occurrences?

### where `&x`

`{,/x#''!#x}`

### iota `!x`

{&x#1}

Do these rely on each other?

### icsa commented Apr 14, 2020

 ?/: / find each right in k2, k3, k4 where and iota are self-referencing as it were. I making implementations of verbs in terms of other verbs. Then the minimal set of verbs can be determined based on frequency of use and likely performance.

### Implementations from my notes:

core => a builtin (i.e. compiled) implementation
tbd => to be determined

``````  : tbd
+ flip:{(m;n)#(x .|:)',/(!m:#*x),/:\:!n:#x}
- negate:{0-x}
* first:{\$[0<@x;x;0<#x;x@0;'`length]}
% reciprocal:{1%x}
! iota:{&x#1}
& where:{,/x#''!#x}
| reverse:{x@(-1+#x)-!#x}
= group:{d!(d:?x)?/:x}
~ not:{\$[x~0;1;0}
, enlist:{(),x}
^ tbd
# count → core
_ floor → core
\$ string → core
? distinct:{v@&0=~':v:x@<x}
@ type → core
. eval → core

``````

``````  : set:{.[x;nil;:;y]} / where x is a name/sym
+ plus → core
- minus:{x+-y}
* times → core
% divide → {x*%y}
! tbd
& min:{\$[x<y;x;y]
| max:{\$[x<y;y;x]
< less → core
> more:{y<x}
= equal → core
~ match:{\$[(@x)=@y;&/bits[x]=bits[y];0]}
, concat → core
^ tbd
# take:{y@(&x) mod (#x)}  / for x>0
_ cut:{y@!:'-':x,#y}      / for x within 0,#y
\$ cast → core
? find:{\$[0<#i:&x~\:y;*i;#y]}
@ apply → core
. applydeep → core

``````

### / built-in functions

``````sum:{+/x}
wsum:{+/x*y}
avg:{sum[x]%#x}
wavg:{wsum[x;y]%+/(#y)#x}
var:{avg x*x:x-avg x}
cov:{avg (x-avg x)*y-avg y}
dev:{sqrt var x}
dot:wsum
mmu:{+/x*\:/:y}
ceil:{-_-x}
signum:{(x>0)-x<0}
div:{ceil x%y}
mod:{x-y*x div y}
in:{(#y)>y?x}
union:{?x,y}
within:{(~x<*y)&x<y 1}
except:{x@&~x in y}

``````

### / built-in functions

``````sum:{+/x}
wsum:{+/x*y}
avg:{sum[x]%#x}
wavg:{wsum[x;y]%+/(#y)#x}
var:{avg x*x:x-avg x}
cov:{avg (x-avg x)*y-avg y}
dev:{sqrt var x}
mmu:{(+/)x*\:/:y}
dot:wsum
ceil:{-_-x}
signum:{(x>0)-x<0}
div:{ceil x%y}
mod:{x-y*x div y}
in:{(#y)>y?x}
union:{?x,y}
within:{(~x<*y)&x<y 1}
except:{x@&~x in y}
``````

Nice!