K Fragments

I recently reviewed and digitized my work notebooks from the last four years- about 900 handwritten pages. In the process, I collected a number of short K fragments which solve interesting problems or illustrate idioms. Most of these I personally "discovered", but in some cases I later found find prior art elsewhere on the internet. This provides a nice illustration of how crystalline K programs can be: presented with the same problem, two programmers are surprisingly likely to arrive at character-for-character identical solutions.

Since these were mostly composed at work, many are k3-based. I have annotated which fragments work in several dialects.

Accumulator Generator (oK only)

In oK, dyadic . of a function and a dictionary re-binds the dictionary as that function’s global scope. Conversely, monadic . of a function retrieves that function’s global scope as a dictionary. This feature breaks referential transparency of functions, but also allows you to slum it with Lisp weenies. Arthur doesn’t like it.

f: {{n+::x}.(,`n)!,x}

a: f[10]<br>a[2]<br>12<br>a[5]<br>17<br>a[5]<br>22

Pascal’s Triangle (oK, k3, k7)

A classic exercise demonstrating "for-scan".

5{(0,x)+x,0}\1<br>(1<br>1 1<br>1 2 1<br>1 3 3 1<br>1 4 6 4 1<br>1 5 10 10 5 1)

Dereplicated Map (oK, k3)

Map a function x over y without recomputing duplicate values.

f: {(x'y)(y:?y)?/:y}

f[{`0:,"f of ",$x;x+2};3 10 9 3 5 10]<br>f of 3<br>f of 10<br>f of 9<br>f of 5<br>5 12 11 5 7 12

2x2 Matrix Determinant (oK, k3, k7)

A nice use of dot-apply.

f: {-/x*|y}.

f (3 8;4 6)<br>-14

Adjacency Lists (oK only)

Build simple directed graphs of size n in an adjacency list format: a list of lists of the indices of destination nodes.

star: {(,1+!x),,:'&x}<br>total: {x^'!x}

star 4<br>(1 2 3 4<br>,0<br>,0<br>,0<br>,0)<br>total 4<br>(1 2 3<br>0 2 3<br>0 1 3<br>0 1 2)

Longest Cycle Count (k3, k7)

Iterating on a permutation vector, how many steps is the longest cycle?

f: |/#:'{x\'x}@

f 1 2 3 0<br>f 1 0 3 4 2<br>f 0 1 2 3 4

Rising Edge (oK, k3, k7)

"Number go up! Number good." -business man

0>': 3 3 4 5 4 6 9 / oK, k7<br>1 0 1 1 0 1 1<br>0>': 3 3 4 5 4 6 9 / k3<br>0 0 1 1 0 1 1

Sign (oK, k3, k7)

Iverson’s convention.

f: {(0

Find a Function’s Name (k3 only)

An everyday convenience function.

f: {$(t[0],_n)@(t:+..k)[1]?x}

boop: {x+1}<br>f {x+1}<br>"boop"

Is Inverleave? (k3 only)

Can you interleave x and y (merge without altering element orders) to arrive at z?

f: {y~z@&~':x{:[y~*x;1_ x;x]}\z}

f["don";"dogo";"dodongo"]<br>f["don";"dogo";"gododon"]

Merge Dictionaries (k3 only)

Turn a list of dictionaries into a dictionary of lists.

f:{.+(k;({x@&~_n~/:x}x@')'k:?,/!:'x)}

f (.,(`a;1);.,(`b;2);.((`a;3);(`b;4)))<br>.((`a<br>1 3)<br>(`b<br>2 4))

In oK, this can be expressed much more directly by taking advantage of the richer algebra for dictionaries and the "adverb form" of _:

f: {k!(^)_:'x@'/:k:!,/x};

f ([a:1];[b:2];[a:3;c:4])<br>[a:1 3;b:,2;c:,4]

Distinct Names (k3, k7)

Tag duplicates by order of appearance.

f:{x,'(,/($!#:)'t)@

Limit Run Length (oK, k3, k7)

Cap runs of char z in y to length x.

f: {y@&~x

Links

oK repl

k7 web build

back