QforMortals3/Functions on Lists 101

From Kx Wiki
Jump to: navigation, search

1.11 Functions on Lists 101

Because q is a vector language, most of the built-in operators work on lists out of the box. In q-speak, such functions are atomic, meaning they recursively burrow into a complex data structure until arriving at atoms and then perform their operation. In particular, an atomic function operates on lists by application to the individual items. For example, plain addition adds an atom to a list, a list to an atom or two lists of the same length.

q)42+100 200 300
142 242 342
q)100 200 300+42
_
q)100 200 300+1 2 3
_

Perhaps surprisingly, this is also true of equality and comparison operators. (Recall the notation for simple boolean lists).

q)100=99 100 101
010b
q)100 100 100=100 101 102
_
q)100<99 100 101
_

Suppose that instead of adding things pair-wise, we want to add all the items across a list. The way this is done in functional languages is with higher order functions, or as they are called in q, adverbs. Regardless of the terminology, the idea is to take the operation of a function and produce a closely related function having the same “essence” but applied in a different manner.

You met the concept of higher-order functions in elementary calculus, perhaps without being properly introduced. The derivative and integral are actually higher order functions that take a function and produce a related function. Behind all the delta-epsilon mumbo- jumbo, the derivative of a given function is a function that represents the instantaneous behavior of the original. The (indefinite) integral is the anti-derivative—i.e., a function whose instantaneous behavior is that of the given function.

In the case of adding the values in a list, we need a higher-order function that takes addition and turns it into a function that works across the list. In functional programming this is called a fold; in q it is “over.” The technique is to accumulate the result across the list recursively. (See Mathematical Refresher for more on recursion). Specifically, begin with an initial value in the accumulator and then sequentially add each list item into the previous value of the accumulator until the end the list. Upon completion, the accumulator holds the desired result.

If you are new to functional programming this may seem more complicated than just creating a for loop but that’s only because you have been brainwashed to think that constructing a for loop is “real” programming. Watch how easy it is to do in q. In words, we tell q to start with the initial value of 0 in the accumulator and then modify (+) with the adverb (/) so that it adds across the list.

q)0 +/ 1 2 3 4 5
15
q)0 +/ 1+til 100
_

There is nothing special about built-in operator (+)—we can use any operator or even our own function.

q)0 {x+y}/ 1 2 3 4 5
_
q)0 {x+y}/ 1+til 100
_

In this situation we don’t really need the flexibility to specify the initial value of the accumulator. It suffices to start with the first item of the list and proceed across the rest of the list. There is an even simpler form for this case.

q)(+/) 1 2 3 4 5
_
q)(+/) 1+til 100
_

If you are new to functional programming, you may think, “Big deal, I write for loops in my sleep.” Granted. But the advantage of the higher-order function approach is that there is no chance of being off by one in the loop counter or accidentally running off the end of a data structure. More importantly, you can focus on what you want done without the irrelevant scaffolding of how to set up control structures. This is called declarative programming.

What else can we do with our newfound adverb? Change addition to multiplication for factorial.

q)(*/) 1+til 100
3628800

The fun isn’t limited to arithmetic primitives. We introduce (|), which returns the larger of its operands and (&), which returns the smaller of its operands.

q)42|98
98
q)42&98
_

Use (|) or (&) with over and you have maximum or minimum.

q)(|/) 20 10 40 30
40
q)(&/) 20 10 40 30
_

Some applications of (/) are so common that they have their own names.

q)sum 1+til 10               / this is +/
55
q)prd 1+til 10                / this is */ -- note missing “o”
_
q)max 20 10 40 30       / this is |/
_
q)min 20 10 40 30       /this is &/
_

At this point the (/) pattern should be clear: it takes a given function and produces a new function that accumulates across the original list, producing a single result. In particular, (/) converts a dyadic function to a monadic aggregate function—i.e., one that collapses a list to an atom.

We record one more example of (/) for later reference. Recall from the previous section that applying the operator (#) to an atom produces a list of copies. Composing this with (*/) we get a multiplicative implementation of raising to a power without resorting to floating point exponential.

q)(*/) 2#1.4142135623730949 1.9999999999999996
q)n:5
q)(*/) n#10
100000

The higher-order function sibling to over is scan, written (\). The process of scan is the same as that of over with one difference: instead of returning only the final result of the accumulation, it returns all intermediate values.

q)(+\) 1+til 10
1 3 6 10 15 21 28 36 45 55 q)(*\) 1+til 10
_
q)(|\) 20 10 40 30
20 20 40 40
q)(&\) 20 10 40 30
_

Scan converts a dyadic function to a monadic uniform function—i.e., one that returns a list of the same length as the input.

As with over, common applications of scan have their own names.

q)sums 1+til 10          / this is +\        
_
q)prds 1+til 10          / this is *\    / note missing ‘o’
_
q)maxs 20 10 40 30       / this is *\  
_
q)mins 20 10 40 30       /  this is &\
_



Prev: Functions 101, Next: Example: Fibonacci Numbers

Reprinted with the author's permission from: q for Mortals Version 3, An Introduction to Q Programming by Jeffry A. Borror.

The book is available on Amazon. In the United Kingdom, it is available at Amazon UK.

©2015 Jeffry A. Borror/ q4m LLC

Personal tools
Namespaces
Variants
Actions
Navigation
Print/export
Toolbox