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^{1} into a composition:
'[f;g]
f
andg
are applicable valuesc:('[f;g])
is a compositionx
is a list of arguments tog
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 ('[;])
^{2} 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)
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 nonbinary 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*0x+y}
10+where 5< / (2) {10+where 5<x}
sum deltas neg floor :: / (3) {sum deltas neg floor x}
A nonunary 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 argumentstring
. 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+
and1 1*/
. It is a composition because the rightmost term follows the third pattern: a binary derived function*/
projected onto its left argument1 1
using infix syntax.In the parse tree we see Composeq)parse"1000 + 1 1 */" ' (+;1000) ((/;*);1 1)
'
with arguments1000+
and1 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 evaluatefoo
the derived function*/
is evaluated over the one argument in that parse tree; indistinguishable from*/[1 1]
; that is1
.The effect is as if
foo
had been defined as1000+ 1@
.Evaluating
q:foo "now is the time"
first applies1
to the string, printing the string to the console and returning itself as a result to be added to 1000 and assigned toq
. 
Use Kadane’s algorithm to solve the Maximum Subarray Problem. Write
ka
such thatq)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.
But of courseq)a 2 1 3 4 1 2 1 5 4 q)sums a 2 1 4 0 1 1 2 3 1
sums
is simply Add Scan.Now Kadane: zero any negative cumulated sum, and continue.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
But lambdaq){0x+y}\[a] 2 0 0 4 3 5 6 1 5 q)max{0x+y}\[a] 6
{0x+y}
is just0
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 listsk
andv
but your ! key is stuck. Make a composition you can use instead.Answer
Arthur Whitney explains that dictionaries are redundant.q)(k;v):(`a`b`c;1 2 3) / key; value q)d:k!v / dictionary q)d `c`a`b 3 1 2
Of course, compositionq)e:v k? / composition q)e `c`a`b 3 1 2
e
is immutable; dictionaryd
can be amended. 
While not a composition, the expression
v group k
returnsk!v
. Explain why that is so, with reference to rules given for indexing and grouping.Answer
Provided
k
contains no duplicates,group k
returnsk!til count k
.Indexing is rightatomic, so the result ofq)group k a 0 b 1 c 2
v@k!y
is a dictionaryk!v@y
.The value of
y
istil count k
sov@y
isv
, andk!v@y
isk!v
.
FIXME review the role of type in composition
Issue #22 in the GitHub repo.