Skip to content

Instantly share code, notes, and snippets.

@chrispsn
Last active Aug 21, 2021
Embed
What would you like to do?
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?
  • 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))

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[0]}"hello"
"h"
 {x[0]}""
" "

at (@)

John Earnest:

 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)

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

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:

 {(,/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)

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)

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"

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 

TODO

Other languages

@icsa

This comment has been minimized.

Copy link

@icsa icsa commented Apr 13, 2020

N.B. Using k4/k7 syntax, atm

where &x

{,/x#''!#x}

iota !x

{&x#1}

group =x

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

@ktye

This comment has been minimized.

Copy link

@ktye ktye commented Apr 13, 2020

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

@chrispsn

This comment has been minimized.

Copy link
Owner Author

@chrispsn chrispsn commented Apr 13, 2020

@chrispsn

This comment has been minimized.

Copy link
Owner Author

@chrispsn chrispsn commented Apr 14, 2020

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

This comment has been minimized.

Copy link

@icsa 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.

@icsa

This comment has been minimized.

Copy link

@icsa icsa commented Apr 14, 2020

Implementations from my notes:

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

/ monadic

  : 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}
  < gradeup → core
  > gradedown → core
  = 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

/ dyadic

  : 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

@icsa

This comment has been minimized.

Copy link

@icsa icsa commented Apr 15, 2020

/ 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}

@chrispsn

This comment has been minimized.

Copy link
Owner Author

@chrispsn chrispsn commented Apr 16, 2020

/ 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!

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