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.
- 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.
- 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))
{y}
Leaving aside the obvious {x}:
/ ngn/k
:\ "hello"
"hello"
:\ "h"
"h"
:\ ""
""
::\ / ngn/k syntax
:\: / k9 syntax
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}
@[;0]"hello"
"h"
@[;0]""
" "
:/|:
chrispsn:
:/1#
{:/&(x,0#x)!~!#x}
(!0)# / reshape
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: {x .,y}
at["hello";0 4 2 1]
"hole"
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}
{-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
Assumes atoms have length 1.
{(a;b):#'(x;y)
@[(a+b)#x;a+!b;:;y]}["hello";"world"]
"helloworld"
{?[x;#x;y]} / splice as '?' triadic
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}
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
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...
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.
{(&/(#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".
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.
/ 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.
#'= / 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:{x{x@y+!z-y}[y]'1_x,#y}
cut[1 2 5;"gremlins"]
(,"r"
"eml"
"ins")
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
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)
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
/ 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
{?<'+!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.
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 !)
John Earnest (assumes rectangular):
shape: -1_#'*\:
shape ("hello";"world")
2 5
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
/ ngn/k syntax
+/'*\:
(+/*)\: / ngn: "more efficient as it takes much less tmp memory" https://matrix.to/#/!laJBzNwLcAOMAbAEeQ:matrix.org/$fcUpo3NDC6eduS8PtIIR_4KLmK_6gd049vd4HWXOIsc
- 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
- BQN: specification, first and current reference versions, how it works now + bootstrap source here and here
- Bel
- REBOL mezzanine