# 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
a
12
a
17
a
22
``````

## Pascal’s Triangle (oK, k3, k7)

A classic exercise demonstrating “for-scan”.

``````  5{(0,x)+x,0}\1
(1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
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]
f of 3
f of 10
f of 9
f of 5
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)
-14
``````

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}
total: {x^'!x}

star 4
(1 2 3 4
,0
,0
,0
,0)
total 4
(1 2 3
0 2 3
0 1 3
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
4
f 1 0 3 4 2
3
f 0 1 2 3 4
1
``````

## Rising Edge (oK, k3, k7)

“Number go up! Number good.” -business man

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

## Sign (oK, k3, k7)

Iverson’s convention.

``````  f: {(0<x)-x<0}

f 34 -99 0
1 -1 0
``````

## Find a Function’s Name (k3 only)

An everyday convenience function.

``````  f: {\$(t,_n)@(t:+..k)?x}

boop: {x+1}
f {x+1}
"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"]
1
f["don";"dogo";"gododon"]
0
``````

## 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)))
.((`a
1 3)
(`b
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])
[a:1 3;b:,2;c:,4]
``````

## Distinct Names (k3, k7)

Tag duplicates by order of appearance.

``````  f:{x,'(,/(\$!#:)'t)@<,/t:=x}

f ("foo";"bar";"foo";"quux";"zami";"bar")
("foo0"
"bar0"
"foo1"
"quux0"
"zami0"
"bar1")
``````

## Limit Run Length (oK, k3, k7)

Cap runs of char `z` in `y` to length `x`.

``````  f: {y@&~x<{y*x+y}\z=y}

f[2;"xxxxOOxOOxxxOOx";"x"]
"xxOOxOOxxOOx"
``````

back