Composition

DRAFT

A sequence of operations doesn’t need a lambda to be a function.

Accumulator iterators derive functions that apply a function $f$ repeatedly to its result: $f(f(f(x)))$.

A composition is a pipeline of (mostly) unary functions $f$, $g$, $h$, etc., in which each function evaluates the result of the next: $f(g(h(x)))$.

In mathematics, function composition is an operation $f \circ g$ that takes two functions $f$ and $g$, and produces a function $h = g \circ f$ such that $h(x) = g(f(x))$. — Wikipedia

A q composition has type 105h.

q)tc:('[til;count])  / Compose til and count
q)type[tc]           / composition
105h
q)tc "abc"
0 1 2

Composing two values

The binary Compose operator ' has only bracket syntax. It binds two applicable values¹ into a composition:

'[f;g]

Where

f and g are applicable values
c:('[f;g]) is a composition
x is a list of arguments to g

then c has the same rank as g and c . x returns the result of f[g . x].

A composition can include data

Notice from the above definitions that compositions can include data structures, not just functions, and not just as projected arguments.

This is possible because Apply and Index have the same syntax and notation.

When f is not a unary

If f is not a unary, then the result of f[g . x] is a projection.

q)type('[+;*])        / composition
105h
q)'[+;*][2;3]         / projection
+[6]
q)'[+;*][2;3] 1000    / +[6] 1000
1006

Composing three or more values

Iterating ('[;])² over a list of applicable values (f;g;h;..;n) returns a composition that similarly returns f g h .. n . x.

cc:('[;]) over (f;g;h;...;n)

Above, cc has the same rank as n and cc . x is the same as f g h ... n . x.

q)cc:('[;])over({x*x};{x+1};+)
q)cc
{x*x}{x+1}+
q)cc[3;4]
64

The composition has the rank of its rightmost term. Above, cc has rank 2.

Syntactic sugar

Where f and g are applicable values and g is either

a binary operator, keyword, or derived function
a binary operator, keyword, or derived function projected on a left argument with infix syntax
a non-binary followed by the Identity operator ::

then

(f g)       <==>   ('[f;g])
(f g) . x   <==>   f[g . x]

Some examples:

composition          syntax rank
-----------------------------------
0| +                   1    binary
" #" 5<                2    unary
deltas 10 20*/:        2    unary
deltas {x*x} @         2    unary
deltas {x*x} each      2    unary
deltas {x*x} ::        3    unary
10+ {x*y+z} ::         3    ternary

Any of these patterns may be preceded by an arbitrary number of applicable values: the entire sequence is composed. The following are all compositions.

10*0|+                    / (1) {10*0|x+y}
10+where 5<               / (2) {10+where 5<x}
sum deltas neg floor ::   / (3) {sum deltas neg floor x}

A non-unary is useful only as the rightmost term in a composition.

The following is a composition but does nothing useful.

q)type({x*y+z}{x*y+z}{x*y+z}::)
105h

Exercises

No peeking.

Attempt each exercise before looking at its answer.

The exercises clarify your thinking. Reading answers does not.

Where
```
sentence:`The`quick`brown`fox`jumps`over`the`lazy`dog 
parts:`article`adj`adj`noun`verb`preposition`article`adj`noun 
```
Write an expression that uses a composition to put parentheses around the adjectives in sentence.
Answer
```
q)@[;where parts=`adj;`$"(",,[;")"]string@]sentence
`The`(quick)`(brown)`fox`jumps`over`the`(lazy)`dog
```
The third argument of Amend At @ is a composition because it follows the third pattern: it ends with a binary operator Apply At @ projected infix onto its left argument string. That is, the composition is
```
`$
"(",
,[;")"]
string@
```
Explain:
```
q)foo:1000 + 1 -1 */
q)q:foo "now is the time"
now is the time
q)q
999
```
Answer

foo is a composed of two unary projections: 1000+ and 1 -1*/. It is a composition because the rightmost term follows the third pattern: a binary derived function */ projected onto its left argument 1 -1 using infix syntax.
```
q)parse"1000 + 1 -1 */"
'
(+;1000)
((/;*);1 -1)
```
In the parse tree we see Compose ' with arguments 1000+ and 1 -1*/ represented by their parse trees.

Derived function */ is represented by its parse tree (/;*), reminding us that the iterator / takes a single argument *. The function */ it derives is variadic and has infix syntax. When we evaluate foo the derived function */ is evaluated over the one argument in that parse tree; indistinguishable from */[1 -1]; that is -1.

The effect is as if foo had been defined as 1000+ -1@.

Evaluating q:foo "now is the time" first applies -1 to the string, printing the string to the console and returning itself as a result to be added to 1000 and assigned to q.
Use Kadane’s algorithm to solve the Maximum Subarray Problem. Write ka such that
```
q)ka -2 1 -3 4 -1 2 1 -5 4
6
```
Answer

Kadane’s insight is that no subarray with a negative total can begin or extend a candidate subarray. Thus wherever the cumulative sum is negative, reset it to zero and start cumulating again.
```
q)a
-2 1 -3 4 -1 2 1 -5 4
q)sums a
-2 -1 -4 0 -1 1 2 -3 1
```
But of course sums is simply Add Scan.
```
q)sums
+\
q)+\[a]
-2 -1 -4 0 -1 1 2 -3 1
q){x+y}\[a]
-2 -1 -4 0 -1 1 2 -3 1
```
Now Kadane: zero any negative cumulated sum, and continue.
```
q){0|x+y}\[a]
-2 0 0 4 3 5 6 1 5
q)max{0|x+y}\[a]
6
```
But lambda {0|x+y} is just 0| composed with Add.
```
q)max(0|+)\[a]
6
q)ka:{max(0|+)\[x]}     / Kadane's algorithm
```
Express your solution to the previous exercise as a composition.
Answer

Above we see the lambda has two parts: max and (0|+)\. The former is a unary; the latter is variadic but, parenthesise it and you have a noun you can apply as a unary. So they can be composed:
```
ka: max ((0|+)\) ::   / iterator applied postfix
ka: max (\[0|+]) ::   / iterator applied with bracket notation
```
You want to make a dictionary k!v from lists k and v but your ! key is stuck. Make a composition you can use instead.
Answer
```
q)(k;v):(`a`b`c;1 2 3)  / key; value
q)d:k!v                 / dictionary
q)d `c`a`b
3 1 2
```
Arthur Whitney explains that dictionaries are redundant.
```
q)e:v k?                / composition
q)e `c`a`b
3 1 2
```
Of course, composition e is immutable; dictionary d can be amended.
While not a composition, the expression v group k returns k!v. Explain why that is so, with reference to rules given for indexing and grouping.
Answer

Provided k contains no duplicates, group k returns k!til count k.
```
q)group k
a| 0
b| 1
c| 2
```
Indexing is right-atomic, so the result of v@k!y is a dictionary k!v@y.

The value of y is til count k so v@y is v, and k!v@y is k!v.

FIXME review the role of type in composition

Issue #22 in the GitHub repo.

A function, list, dictionary or handle; i.e.any valid left argument to Apply. ↩
Quote is overloaded by rank, so it is necessary to write '[;] to distinguish (binary) Compose from (unary) Each. ↩