# QforMortals3/Example FIFO Allocation

## 1.14 Example: FIFO Allocation

In the Finance industry, one needs to fill a sell order from a list of matching buys in a FIFO fashion. Although we state this scenario in terms of buys and sells, it applies equally to general FIFO allocation. We begin with the buys represented as a (time-ordered) list of floats, and a single float sell.

```q)buys:2 1 4 3 5 4f
q)sell:12f
```

The objective is to draw successively from the buys until we have exactly filled the sell, then stop. In our case the result we are seeking is,

```q)allocation
2 1 4 3 2 0
```

The insight is to realize that the cumulative sum of the allocations reaches the sell amount and then levels off: this is an equivalent statement of what it means to do FIFO allocation.

￼￼
```q)sums allocation
2 3 7 10 12 12
```

We realize that the cumulative sum of buys is the total amount available for allocation at each step.

￼￼
```q)sums buys
2 3 7 10 15 19f```

To make this sequence level off at the sell amount, simply use (&).

```q)sell&sums buys
2 3 7 10 12 12f
```

Now that we have the cumulative allocation amounts, we need to unwind this to get the step-wise allocations. This entails subtracting successive items in the allocations list.

Wouldn’t it be nice if q had a built-in function that returned the successive differences of a numeric list? There is one (deltas) and— no surprise—it involves an adverb (called each-previous—more about that in Chapter 5). ￼

```￼q)deltas 1 2 3 4 5
11111
q)deltas 10 15 20
_
```

Observe in your console display that (deltas) returns the initial item untouched. This is just what we need.

Returning to our example of FIFO allocation, we apply (deltas) to the cumulative allocation list and we’re done.

```q)deltas sell&sums buys
_
```

Look ma, no loops!

Now fasten your seatbelts as we switch on warp drive. In real-world FIFO allocation problems, we actually want to allocate buys FIFO not just to a single sell, but to a sequence of sells. You say, surely this must require a loop. Please don’t call me Shirley. And no loopy code.

We take buys as before but now we have a list sells, which are to be allocated FIFO from buys. ￼

```q)buys:2 1 4 3 5 4f
q)sells:2 4 3 2
q)allocations
2 0 0 0 0 0
0 1 3 0 0 0
0 0 1 2 0 0
0 0 0 1 1 0
```

The idea is to extend the allocation of buys across multiple sells by considering both the cumulative amounts to be allocated as well as the cumulative amounts available for allocation.

```q)sums[buys]
2 3 7 10 15 19f
q)sums[sells]
2 6 9 11
￼```

The insight is to cap the cumulative buys with each cumulative sell.

```q)2&sums[buys] 2 2 2 2 2 2f
q)6&sums[buys] 2 3 6 6 6 6f
q)9&sums[buys] 2 3 7 9 9 9f
q)11&sums[buys] 2 3 7 10 11 11f
```

Contemplate this koan and you will realize that each line includes the allocations to all the buys preceding it. From this we can unwrap cumulatively along both the buy and sell axes to get the incremental allocations.

Our first task is to produce the above result as a list of lists.

```2 2 2 2 2 2
2 3 6 6 6 6
2 3 7 9 9 9
2 3 7 10 11 11
```

Adverbs to the rescue! Our first task requires an adverb that applies a dyadic function and a given right operand to each item of a list on the left. That adverb is called each left and it has the funky notation (\:). We use it to accomplish in a single operation the four individual (&) operations above.

```q)sums[sells] &\: sums[buys]
2 2 2 2 2 2
2 3 6 6 6 6
2 3 7 9 9 9
2 3 7 10 11 11
```

Now we apply (deltas) to unwind the allocation in the vertical direction.

```q)deltas sums[sells]&\:sums[buys]
2 2 2 2 2 2
0 1 4 4 4 4
0 0 1 3 3 3
0 0 0 1 2 2 ￼
```

For the final step, we need to unwind the allocation across the rows.

The adverb we need is called (each). As a higher-order function, it applies a given function to each item of a list (hence its name). For a simple example, the following nested list has count 2, since it has two items. Using (count each) gives the count of each item in the list.

```q)(1 2 3; 10 20)
_
q)count (1 2 3; 10 20)
_
q)count each (1 2 3; 10 20)
3 2
```

In the context of our allocation problem, we realize that (deltas each) is just the ticket to unwind the remaining cumulative allocation within each row.

```q)deltas each deltas sums[sells] &\: sums[buys]
2 0 0 0 0 0
0 1 3 0 0 0
0 0 1 2 0 0
0 0 0 1 1 0
```

Voila! The solution to our allocation problem in a single line of q. The power of higher order functions (adverbs) is breathtaking.

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