chrispsn/k_tech_tree.md

## k_tech_tree.md

      
    Raw
  

              k_tech_tree.md
            
          
    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
The APL Farm's k chatroom (Matrix/Discord)
the k tree chatroom (defunct now, but archives are good).

What should we assume?


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

See also this Reddit thread.
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))

right (:)

 {y}

identity (::)

Leaving aside the obvious {x}:
 / ngn/k
 :\ "hello"
"hello"
 :\ "h"
"h"
 :\ ""
""

enlist (,:)

 ::\  / ngn/k syntax
 :\:  / k9 syntax

Or for lists:
(&1)_  / ngn/k syntax

count (#L)

ngn/coltim
 c: {[x;y]x+1}/0,   / needs a 'left' {y;x}
 c 2 1 3
3
 c ()
0
 c 7
1

chrispsn:
 0+/ :[;1]'
 {+/x!1}

first (*L)

 @[;0]"hello"
"h"
 @[;0]""
" "

DiscoDoug:
:/|:

chrispsn:
:/1#
{:/&(x,0#x)!~!#x}
(!0)#  / reshape

match (~)

Conversion of oK logic. May not work for function comparison:
{$[~(t:@x)=@y; 0
   `m=t; o[!x;!y]&o[. x;. y]
   t=_t; x=y          / assumes atoms (and only atoms) have lowercase type, except for dicts (`m)
   (#x)=#y; 1&/x o'y  / maybe more efficient for single-type lists by doing 1&/x=y? 
   0]}

Presumably less efficient due to serialisation via `k (maybe OK if raw memory?), but shorter and perhaps better coverage:
{$[~(@x)=@y; 0; (#x:`k x)=#y:`k y; 1&/x=y; 0]}

Could define based on sorting/grading? From the BQN docs 'Ordering functions' page:

...if one array doesn't come earlier or later than another array in the ordering then the two arrays match

at (@)

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

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

Extension to negative range: {(0&x)+!x|-x}
A couple from Traws 1, 2
{-1+\:x#1}
{(-1+0&x)+\x#1}      / chrispsn extending to negative range
{-1+\x(1,)/:`i$()}

A bunch that use where & in either atom and/or list case:
&&0, richie - or {&&(0;x)} if we assume comma isn't available
&~& chrispsn, riffing off richie's answer above
{&x#1} icsa
-1+\&0, chrispsn
-1+\~&: chrispsn
Some flat 'range each' variants, albeit using atomic range (chrispsn, but probably well-known to others).

{(!*|a)-(0 :':a:+\x)@&x} (equivalent of ,/!'). Maybe easier with an occurrence count primitive (oc@&x).
{(a@&x)-1+!*|a:+\x} (equivalent of ,/|'!')

cat (L,L,a,L,L,a)

Assumes atoms have length 1.
 {(a;b):#'(x;y)
  @[(a+b)#x;a+!b;:;y]}["hello";"world"]
"helloworld"

coltim:
{?[x;#x;y]}  / splice as '?' triadic

reverse (|L)

Needs a dict implementation.
May benefit from negative indexing (ie "hello"[-1] => "o").
 {x(#x)-1+!#x}"hello"
"olleh"
 {x@-1+-!-#x}  / ngn/k negative range
 {x(-!-#x)-1}  / identical

coltim (needs work for atoms):
{(0#x){(,y),x}/x}

Sort domain:
 {x@>!#x}

take (i#L)

Needs a dict implementation. Relies on negative range (-3 -2 -1 ~ !-3) and mod (i!).
 f:{y(#y)!!x}
 f[3;"hello"]
"hel"
 f[-3;"hello"]
"llo"
 f[8;"hello"]
"hellohel"
 f[-8;"hello"]
"llohello"

(Idle thought: what if take generated indices instead, and we skipped the x@... it might create complications for dicts.)
A few 'overcopy, then filter' approaches that avoid indexing:
{&y!x>!#y}                  / basic idea, but limited

{k:((-#y)!a:x|-x),[;y]/y    / handles -ve and overtake
 &k!(x<0)|:/a>!#k}          / could replace a>!#k with ~&1-[#k;]\a and probably can cut more if did that

 / could maybe 'square' and attach to self then whittle,
 / rather than appending original list? faster to build but maybe more memory usage... 

 / other sketches:

{copies:((-#y)!x)::\y
 &x>{x!!#x}@,/copies}       / boo, raze... overtakes but no -ve indexing
 
{n:(#y)+(0<)-[;#y]\x-#y
 :/+&explode n>n :\:y!!#y}  / assumes 'explode' from WAR ON RAZE, or else deep where for dicts

ngn/k's 'recurrence' extension may also help - need to explore further.
 {z;x}\[3]."abc"
"abcabc" 
 {[a;b;c;d]a}\[7]."abcd"
"abcdabcdabc"
 {{[a;b;c;d]a}\[x-#y].y}[7;"abcd"]    / hmm... what if 'right' took arbitrary numbers of arguments...
"abcdabc"

Also consider the 0N# case.
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. Decent speed!
{|\@[(:/v)#0; -1_v:+\x; :; 1_!#x]}
{|\@[(+/x)#0; 0 :':+\x; :; !#x]}    / similar

Another, but more each-y:
{@[(:/v)#0; (-1_v:+\x)+1_!'x; :; 1_!#x]}

Some more that aren't fast, but kept here for future reference:
{@[(:/x)#0;(0 :':x:+\x)+!'x;:;!#x]}
{{x,y#z}/[!0;x;!#x]}

If known to be boolean (and for all input in ngn/k, since # is replicate) we can use filter:
 {:[;x]#!#x} 1 0 1 1 0
0 2 3

...or grade (again, boolean only):
{(+/x)#>x}

Some ways to do duplicates of slices of a list: https://matrix.to/#/!laJBzNwLcAOMAbAEeQ:matrix.org/$GkPsw8ScEkRg3_LSFNVY68qudyQR0AdlcE_Nlq0hEcw?via=matrix.org
Also see Marshall's writeup of Implementation of Indices and Replicate.
Deep where (ish), chrispsn:
{while:{a:*|x; ~a~,/a}              / could do a shape check instead?
 next:{(I;x):x
       I:I@\:&L:#'x
       I,:,@[,/!'L;&t=_t:@'x;:;0N]  / could also do a 'flat ranges'
       (I;,/x)}
 *while next/(,!#x;x)}

where-inverse ie run-length encode ((&:)?; /⁼ in BQN)

I think the general case should generate a dict. Not sure about asc-sorted 0+ int lists (which could give an int list with zeroes for elements that don't appear); but I think the idiom to generate that is pretty easy to write.
chrispsn. !#x is to handle case where null is at start; could also do an amend to set zero at index &0<#x.
{x[i]!-':(1_i:&~(!#x)&~':x),(1&#x)##x}  / -':
{x[i]!#'(i:&~(!#x)&~':x)_x}             / cut
{(*'x)!#'x:(&~(!#x)&~':x)_x}            / cut

chrispsn, sum variations:
{:[;1_i,0]_x!1+{y*x+y}\i:(!#x)&~':x}         / force no-match at start with (!#x)&
{:[;1_i,0]_x!1+{y*x+y}\i:@[~':x;&0<#x;:;0]}  / force no-match at start with amend-to-zero

/ instead of 1_ to get left-shift, subtract 1 from where result
/ and where-inverse on the resulting ints
/ to get our bitmask of what to drop. (recursive call?)
{:[;@[i&0;0|-1+&i;:;1]]_x!1+{y*x+y}\i:@[~':x;&0<#x;:;0]}  

See also this from the Shakti Google Group and Matrix messages from here and here.
grade / sort

Lomuto's Comeback + HN notes may be helpful.
Some simple ones:
{$[2>#?x;x;,/o'x@&'~:\x<*1?x]}   / quicksort. from kcc https://github.com/kparc/kcc
{$[&/x=*x;x;,/o'x@&'~:\x<*1?x]}  / updated to remove ? dependency (thanks ngn!)

Insertion sort, Shell sort, merge sort via DiscoDoug.
Grade down:
{(-1+#x)-|<|x} (ngn)

find (L?L or L?A)

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

Very slow, but at least it short-circuits:
{{~(z=#x)|y~x z}[x;y](1+)/0}/:

Cheating?
{(x!!#x)y}  / chrispsn

coltim:
{(*'=x)y}

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}

Also see Roger Hui's "Index Of, A 30 Year Quest".
progressive find (BQN ⊒)

See 'Anatomy of An Idiom' by Bob Smith and BQN notes.
Assumes you want #x as the fill, but could also leave out (#x)^ to get 0N like a ngn/k find.
ngn/k:
{(#x)^?/(#x;#y)#'(<<)'(x,y;y,x)}             / translated and rearranged version of 'Anatomy of an Idiom' 
{@[y :'#x;(#'a)#'b;:;a:((=x)@'<'b:=y)^'0N]}  / chrispsn - bad

Easily modified to get presence instead of location. See also coltim's Speed of Lobsters golf and Bubbler's Wordle scoring golf.
mark firsts (BQN ∊)

{(!#x)=x?x}

See also the below definitions for unique.
unique (?L)

Lots of these can be simpler if we don't care about whether the remaining elements are in the same order as the input.
ngn's: https://chat.stackexchange.com/transcript/90748?m=53935244#53935244
room to optimise further: https://chat.stackexchange.com/transcript/90748?m=53935363#53935363
 {x@&(!#x)=x?x} "abracadabra"
"abrcd"
 {(!#x)=x?x}#   "abracadabra"
 {x@&@[&#x;x?x;:;1]} "abracadabra"   / much faster than {@[&#x;x?x;:;1]}#, at least in ngn/k @ 2022-05-15

coltim's here:
 {0N>':|\x?x}#

chrispsn:
 {x@i@<i@:&@[~~':x@i:<x;&1&#x;:;1]}
 @[~':x@i;&1&#x;:;0]@<i:<x}_     / shorter but slower - the second grade is on a longer vector

chrispsn:
*'-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]}

coltim had the idea of a primitive similar to unique that spits out a dict with keys as unique values and indices as their first positions. Could be implemented as:
{(x i)!i@:&@[~~':x@i:<x;&1&#x;:;1]}      / order not preserved
{(x i)!i@:<i@:&@[~~':x@i:<x;&1&#x;:;1]}  / order preserved
{!/(x@;::)@\:&(!#x)=x?x}
{k!x?k:?x}  / ngn (assumes unique is available): https://matrix.to/#/!laJBzNwLcAOMAbAEeQ:matrix.org/$JWYwp3-M8nqQu2XSnkU4Db1Zqk13xurbYdJuDBrcl_0
*'=

You could even skip the dict and just return the indices. Works for grade, after all.
group (= map)

 / ngn/k syntax: [chrispsn]
 {a!&'x~\:/:a:?x}
 {(x b)!&'a=/:b:?a:x?x}
 {$[x; [x[&u]!(&(u:a=!#a)b)_b:<a:x?x]; x!()]}
 / see also https://codeberg.org/ngn/k/src/commit/ba0e0ba340dc0c392c04037ef98ce36ae8078c14/o.c#L24
 {v:(a:&(!0),@[~~':x@i;&1&#x;:;1])_i:<x; x[*'v]!v@:<i@a}
 
 / k9 syntax [chrispsn]
 {u:a=!#a:x?x; x[&u]!(u@)^<a}  / left out the empty case handling. maybe a nice example where it matters what cut should output if told to cut at indices (!0)...
 
 / appendy - tweaked version of coltim
 / https://matrix.to/#/!laJBzNwLcAOMAbAEeQ:matrix.org/$PsxFctKKiqhnzGyXcRBxDm4UvSe7QRaOBXjIkiUbjqs
 {@[!'(?x)!0;x;,;!#x]}
 
 / preallocated - needs some work [chrispsn]
 {d:@[(?x)!0;x;+;1]
  .[;;:;]/[d;(+(k;,/d:!'d))@<k:&d;<x]}
  
 / preallocated without 'unique' - needs some work [chrispsn]
 {d:!/(x;c)@\:&0<c:@[&#x;x?x;+;1]
  .[;;:;]/[d;(+(k;,/d:!'d))@<k:&d;<x]}
  
 / some other 'build boolean lists then where-each' approaches - need work for empties [chrispsn]
 {t:&'(?x)!#x; &'t.[;;~:]/+(x;!#x)}
 {&'+(+&'(?x)!#x)@[;;~:]'x}
 
 / this might work in some implementations, but it depends heavily on what cat-each does with dict args...
 {((0#x)!0+()),'x!!#x}

Need one for dicts.
freq

 #'=                      / boooo, boring!
 (()!!0){x+(,y)!,1}/      / v slow
 {(()!!0)+/(,'x)!'1}      / similarly slow
 
 {a!@[&#a;(a:?x)?x;+;1]}                    / with uniq
 {!/(x;a)@\:&0<a:@[&#x;(!0),x?x;+;1]}       / w/o  uniq (fast!)
 {x[u]!-u-@[a;a;+;1]u:&(!0),(!#x)=a:x?x}    / may reuse a? (probs inferior but keeping a note)
 
 / TODO: maybe could find 'element switch' in sorted list faster than ~': via binary searches?
 {(x@&a)!1_-':,[;#x]@&a:@[~(!0),~':x@:<x;&1&#x;:;1]}
 {!/(x;1_-':,[;#x]@)@\:&@[~(!0),~':x@:<x;&1&#x;:;1]}}  / more tacit
 {u:(!0),@[~~':x@:<x;&1&#x;:;1]
   x[&u]!-1-':(!0),a'1+!0^*|a:+\u}     / ok-ish speed
 {u:(!0),@[~~':x@:<x;&1&#x;:;1]
   x[&u]!-':(!0),(#a)^a?2+!0^*|a:+\u}  / similar but swaps out bin for find; not as fast
 
 {!/(x;l)@\:&0<l:-1-':x'x@:<x}    / slow; sorted order

ungroup

Hard to restore a grouped dict in the same order...
If we assume a grouped list as input:
{(&#'x)@<,/x}           / chrispsn, ktye: https://chat.stackexchange.com/transcript/message/56455753#56455753
{@[&#'x;x;:;!x]}        / chrispsn
{@[(+/#'x)#!x;x;:;!x]}  / chrispsn

cut (L^L)

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

coltim: {y@.=&x}
flip (+M)

ktye's, with tweaks from ngn. Supports atoms and wrapping around short lists.

https://chat.stackexchange.com/transcript/message/53804578#53804578
https://bitbucket.org/ngn/k/src/7db03506176387ee019ca83b11d566a7e04bb160/v.c#lines-3

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

Or a much shorter, but sometimes much slower, one from Attila:
 ,'/("ab";"c";"de")
acd
bce

For a flat flip (that handles ragged input), try Bubbler's solution to 'interleave strings' here.
odometer (I)

ngn's (no floats!): https://bitbucket.org/ngn/k/src/7db03506176387ee019ca83b11d566a7e04bb160/v.c#lines-8
 {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)

occurrence count (BQN ⊒)

Naive k:
{@[x;g;:;!'#'g:=x]}  / can also do <' instead of !'#'

APL translated into k and refined by coltim:
{1+o-(m⌿o←⍋⍋⍵)[⍵⍳⍨⍵⌿⍨m←≠⍵]}Y   / original in aplcart.info
{i-(i:<<x)x?x}                      / coltim-refined

DiscoDoug's shootout.
Some bad ways:
{-1+(+\(,'x)!'1)@'x}
{(-1+\(0&=#x)@[;;~:]'x)@'x?:x}

average avg

/ Standard
 {(+/x)%#x} 1 2 3 4
2.5
/ Bubbler https://chat.stackexchange.com/transcript/message/59297576#59297576
 +/%/#:\ 1 2 3 4  / k6 syntax
2.5

power pwr

See some variants here.
permutations prm (takes i as input)

See ngn/k's current impl here.
kparc variants:
 {?<'+!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

ngn's: https://chat.stackexchange.com/transcript/message/54068373#54068373
 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

Arthur has some nice tweaks on these which I'll add once the Shakti downloads are updated.
See also APL Since 1978 "11.3 Permutations" and 'Symmetries of the Square'.
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"

Single rotate, one direction:
 {(:/x):':x}"rotate"
"erotat"

{y(#y)!x+!#y} (ngn/k syntax using k6 mod !)
shape

John Earnest (assumes rectangular):
 shape: -1_#'*\:
 shape ("hello";"world")
2 5

diagonals / antidiagonals / convolution

Flat antidiagonals (still needs a cut step), chrispsn:
{h:#x; w:#*x; (,/x)@<(&h#w)+(h*w)#|!w}

Diagonal lengths, chrispsn (haven't tested exhaustively):
{(a;b):(#x;#*x)
 (a&b)&/|:\1+!0|a+b-1}

Maybe the indices could be computed directly, without a sort?
See /. in J and some discussion on Matrix.
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 

matrix multiply

/ ngn/k syntax
+/'*\:
(+/*)\:  / ngn: "more efficient as it takes much less tmp memory" https://matrix.to/#/!laJBzNwLcAOMAbAEeQ:matrix.org/$fcUpo3NDC6eduS8PtIIR_4KLmK_6gd049vd4HWXOIsc

TODO


combinations from http://kparc.com/z/fun.k and ngn's code
k-strings from oK here and here
why rotate is useful, eg Alex's conway or https://news.ycombinator.com/item?id=22524751
"Minimal set of operators for APL/J like language"
all the stuff in the ispc performance guide

Other languages


BQN: specification, first and current reference versions, how it works now + bootstrap source here and here
Bel
REBOL mezzanine