Skip to content

Instantly share code, notes, and snippets.

@kevinlawler

kevinlawler/k_tech_tree.md

Forked from chrispsn/k_tech_tree.md
Created June 28, 2022 14:28
Show Gist options
  • Save kevinlawler/47c3e071a12881bc10363ec21db62bdb to your computer and use it in GitHub Desktop.
Save kevinlawler/47c3e071a12881bc10363ec21db62bdb to your computer and use it in GitHub Desktop.
Download ZIP
k tech tree
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 and the k tree chatroom.

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

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:

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

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

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

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

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

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

Insertion sort, Shell sort, merge sort via DiscoDoug.

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".

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

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}

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

cut (L^L)

John Earnest:

 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. Supports atoms and wrapping around short lists.

 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

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.

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

permutations prm (takes i as input)

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.

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

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

Other languages

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment