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]
  a[2]
12
  a[5]
17
  a[5]
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

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}
  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[0],_n)@(t:+..k)[1]?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"

Links

back