A Strong Working Knowledge of K

Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu
http://cs.nyu.edu/cs/faculty/shasha/index.html

Unit 2: Conditionals, Adverbs, and String Manipulation

Like C, K has conditionals.
K also has loops, though programs usually run faster and are shorter if you avoid using them.
We discuss these features and the adverbs that often render loops unnecessary.
Strings are a good example.

Topics

conditionals
loops to go through arrays
each operator to avoid loops
exercise: VicePresident salary raises
each operator for listwise differences, counting upticks
exercise: delete blanks
functions, recursive functions, currying, lambda expressions

Conditionals

x: 5
y: 7
if[x < y
  min: x
  max: y
]
if[~ x < y
  min: y
  max: x
]

min: :[x < y; x; y] 
/ if statement follows condition and else statement comes after.
max: :[x < y; y; x]

Note: The second form of conditional returns a value.

While Loops

Apply f to the array members in order.

n: #arr
i:0
out:()
while[ i < n
	out,: f[arr[i]]
	i+: 1
]
out

Note: provided the f on arr[i] doesn't interfere with the f on arr[j], this entire loop can be done with f'arr This is read "f each arr".

Do Loops

Initialize arr from input.

input: 100 _draw 5
n: _ (#input) % 2
arr: n # 0 / initialize
i: 0
do[n
	arr[i]: input[i]
	i+: 1
]

Note: Could do this more efficiently as follows:

input: 100 _draw 5
n: _ (#input) % 2
arr: input[!n]

Even better:
```
arr: n # input
```

Each Operator

The each operator, symbolized by just a ' following immediately after some function f says "apply f to every member of the following list". This is like mapcar in Lisp if you happen to know that. Here we increase all salaries by a factor of 1.1.

sal: 200 250 220 100
f:{[x] x*1.1}
sal: f'sal

(Advanced note) In this case, because f is made up only of multiplication, we can apply it to the entire array of salaries just as multiplication can, so we could say simply:
```
sal: f[sal]
```

Exercise: VP Salary Raise

Create a table of employees with three ranks.

ranks: `pres `vicepres `dilbert
emp.rank: ranks[100 _draw 3]
emp.salary: 50000 + 100 _draw 950000

Want to raise all vice president salaries by 10% but all others by 5%.

VP Salary Raise, Solution 1

Define a function, then apply it to each rank-salary pair.

g:{[rank; salary]
	:[rank = `vicepres
		salary * 1.1
		salary*1.05]}

emp.salary: g'[emp.rank; emp.salary]

VP Salary Raise, Index Approach

f:{[i]
  :[emp.rank[i] = `vicepres
	emp.salary[i]*1.1
	emp.salary[i]*1.05]}

Note that the if-then-else will be the last statement, so will be the return value.
```
indexes: !#emp.salary
emp.salary: f'indexes
```
Some people like applying each on single arguments.

VP Salary Raise, Vector Approach

The most efficient way to do this query is to do it as a vector operation. In this strategy, we will locate all the vicepresidents, multiply them by 1.1 and multiply everyone else by 1.05.
```
i: & emp.rank = `vicepres / vice-presidents
j: & ~ emp.rank = `vicepres / non-vice presidents
emp.salary[i]*: 1.1
emp.salary[j]*: 1.05
```

An Idiom

Sometimes you want to get all the differences in a list. e.g. the differences in the list 3 17 11 12 are 14 -6 1.
There is an idiom for this that involves an advanced use of each. Let's say x is the list.
```
-': x
```
Read this "minus prior" x.
You can also do "ratio prior."
```
%': x
```

Example: Good stock

Suppose you have the prices of some stocks at the closing of a set of days. These are in the vector p. You want to find out whether the stock had more up or down days in p.

goodstock:{[p]
  diffs: -': p / day by day differences
  ups: diffs > 0 / 1 on day of increase, 0 otherwise
  downs: diffs < 0
  (+/ups) > (+/downs) }

Recursion and Cousins

Recursion in K works as you would expect: just put the function inside itself. Here is the factorial function: n! = 1 * 2 * 3 * ... * n

fact:{[n]
  if[n < 2
	:1
  ]
  :n*fact[n-1]
}

fact:{[n]
 :[n > 0
	n*fact[n-1] / the initial : is a return
	1] }

There is another form though in which you use the symbol _f for the recursive form. (Since the underbar is already overloaded in K, I don't like this so much.)
```
fact:{[n]
 :[n > 0
	n*_f[n-1]
	1] }
```

Currying

A curried function is a partially evaluated one. For example, suppose we have a function to compute the quadratic formula.

quad:{[a;b;c]
 x: ((-b) + _sqrt((b^2) - 4*a*c)) % (2*a)
 y: ((-b) - _sqrt((b^2) - 4*a*c)) % (2*a)
 :(x;y)}

Suppose the coefficient of the high order term (a) is always 1 in a setting we call "normalized". Then we can define

normquad: quad[1]
quad[1;4;2] = normquad[4;2]

Lambda Expressions

We don't need to give functions a name if we are using it just once. The following for example is a function for factorial applied to 5.
```
{[x] :[x>0; x*_f[x-1]; 1]} 5
```

Executing Strings

One of the many advantages of interpretation is that one can easily generate functions on the fly. The operation that does this is the simple period. For example the following yields 25.
```
f:{[x] x*x}
str: "f[5]"
. str
```

Exercises

Try to delete all blanks from a string.
Try to delete the initial blanks.
Write a string edit (sed) function that replaces all instances of string old by string new in a line.
Try to delete the trailing blanks.

Delete All Blanks

deleteallblanks:{[s]
  x: s = " " / gives binary 1 or zero saying whether s is blank or not.
  i: & ~ x / gives all indices that are not blank
  s[i]}

Delete Leading Blanks

deleteleadingblanks:{[s]
  x: s = " " / 1s whenever blank, 0s elsewhere
  (x ? 0) _ s} / drop up to first non-1.

Delete Trailing Blanks

Use the deleteleadingblanks function on the reversed string.
```
deletetrailingblanks:{[s]
  | deleteleadingblanks[|s]}
```

Find Most Consecutive Ones

Find the maximum number of consecutive ones in a zero-one vector.
```
f:{[x;y] :[y=0;0;x+y]}
|/ f\flags
```

The Road to Ruin

You are an insurance company. You have a revenue stream which you can predict and m possible payment streams whose values depend on the likelihoods of accidents and nature. Here are your initial conditions:


/ probability of ruin.
/ Given capital, a flow of revenue
/ and m possible payment scenarios that are equi-probable
/ what is the probability of ruin?
n: 200 / time periods
m: 100 / payment scenarios

capital: 1000
revenue: n _draw 2000

payments:(m;n) # ((m*n) _draw 2000)

Your job is to determine whether you will ever have a net negative capital, i.e. the sum of your capital plus your accumulated revenue is less than the sum of your payments. The solution follows. Don't look until you think about it.


/ the ruin function takes two flows (in and out)
/ and determines if the cumulative sum for out
/ is at any point greater than the cumulative sum for in
/ plus the capital.
/ If so, ruin returns 1, else 0.
ruin: {[in; out]
 in[0]+: capital / add in the capital as the initial value
 incum: +\ in
 outcum: +\ out
 |/outcum > incum}

numruins: +/ruin[revenue]'payments

("probability of ruin is"; numruins % m)