DEV Community: Ali Faizan Kazmi

Koping with KDB 002: More List Reversal

Ali Faizan Kazmi — Sat, 29 Dec 2018 19:00:36 +0000

Estimated reading time: 10 minutes

In the previous post we stopped short of applying recursion to reverse a list since we found a quirkier way to do it. Let's see if the use of recursion results in simpler code.

Give me your `ifs`, your `elses`...

Yes, it is possible to control a Q script's execution using conditional evaluation, although it is discouraged: restructuring your code to avoid conditional evaluation is preferred whenever possible.

Available to us is the if statement:

n: 1
if[n=1;message: "I don't think this is useful to us"]

message
-> "I don't think this is useful to us"

The if statement evaluates a given condition (n=1) and if the condition evaluates to a value greater than 0 (which represents the boolean false) then any statements following the condition are executed in order from left to right. In our case, we are assiging the string "I don't think this is useful to us" to the variable message.

As an aside, notice that the concept of scope doesn't apply here: the variable message is defined inside the if statement but continues to be accessible outside of it!

Yes, this doesn't fit our use case: if we are to use recursion, we also need an else clause - something like the following:

if base case reached
    return
else
    continue list reversal

...or just give me your ternaries

Q supports an equivalent of the ternary operator ? available in languages such as Java, JavaScript and C#:

$[1b;"Execute if true";"Execute if false"]
-> "Execute if true"

$[0b;"Execute if true";"Execute if false"]
-> "Execute if false"

The first expression given to the $ operator (1b or 0b) is the condition to evaluate. If the condition evaluates to true then the second expression is executed, otherwise the third one is. If you want to execute multiple expressions for one condition then you can encapsulate your expressions in square brackets:

$[1b;[a:2;b:3];c:4]
a
-> 2
b
-> 3

I think we know enough to proceed with reversing our list. Onward to recursion!

A simple(r) example

Before we apply recursion to our problem, we can try testing it on a simpler problem to make sure it works as expected. We can define a recursive function which keeps adding 1 to a given number until the number is equal to 6:

recur: {[number] $[number=6;"Done";recur[1 + number]]}

Looks like it works!

recur 1
-> "Done"

Can we be sure that recursion is taking place, though? Since I'm not aware of the equivalent of println in Q, one way to make sure that recursion is in fact happening is to pass a number greater than 6 to the function. In languages like Java this should generate a stack overflow since the recursive function would keep on calling itself until there was no more space on the stack. That's exactly what happens here, too:

recur 7
-> `stack
-> @
-> {[number] $[number=6;"Done";recur[1 + number]]}
-> 2008

No idea what the @ and 2008 mean. I'll probably come back to how Q displays exceptions later (Q exceptions prefer to be addressed as "signals").

Finally, recursion

No, wait. There's one more operation we need before we can construct our function: the join operator, used to join two lists. The operator is simply a comma:

1 2 3,4 5 6
-> 1 2 3 4 5 6

1,2 3 4
-> 1 2 3 4

Sorry, one more thing: we also need a way to reduce the size of the list with each recursive call until we're left with a list of one element. Enter the cut (_) operator:

list: 1 2 3

1 _ list
-> 2 3

-1 _ list
-> 1 2

At long last, here's our function:

reverseList: {[list] 
    $[1 = count list;
        list;
        reverseList[1 _ list],-1 _ list
    ]
}

reverseList 1
-> 1
reverseList 1 2
-> 2 1
reverseList 1 2 3
-> 3 2 1 2

Uh-oh, the last result is clearly wrong. Why? Let's do a dry run:

reverseList 1 2 3 -> call reverseList[2 3]
reverseList 2 3 -> call reverseList 3
reverseList 3 -> return 3
reverseList 2 3 -> return 3 joined with 2
reverseList 1 2 3 -> return 3 2 joined with 1 2

Therein lies the fault: it would've been more obvious if I had formulated a proper algorithm:

Given a list L
Its reverse is a reverse of the list t(L) 
    (where t denotes the tail - e.g., t(1 2 3) is 2 3) 
Joined with h(L) 
    (where h denotes the head - e.g., h(1 2 3) is 1)
The reverse of a list with one element is the list itself

In short, the last expression we passed to the $ operator is wrong. We should've used the take (#) operator:

list: 1 2 3
1#list
-> ,1

The comma before 1 is just a way of indicating that 1 is not a number: it is a single-item list.

Here goes nothing:

reverseList: {[list] 
    $[1 = count list;
        list;
        reverseList[1 _ list],1#list
    ]
}

reverseList 1
-> 1
reverseList 1 2
-> 2 1
reverseList 1 2 3
-> 3 2 1
reverseList "A string is a list of characters"
-> "sretcarahc fo tsil a si gnirts A"
reverseList "Sigh of relief"
-> "feiler fo hgiS"

Detour: Q's `reverse`

I mentioned earlier that Q already has a reverse function. What does it look like? We can type the function name in the Q prompt to find out:

reverse
-> |:

Is |: considered one operator? Is it two? Why isn't there an argument in the function body? Is |: meant to precede a list or succeed it? So many questions. We could answer the last one:

|: 1 2 3
-> `

1 2 3 |:
-> 3 2 1

Since |: 1 2 3 returns a signal, looks like the correct way to use |: is definitely the second one. A cursory look at the various Q operators doesn't yield any answers as to how |: is interpreted. Maybe it's an operator (or two operators) coming from k, a language upon which Q is based. I have no difficulty putting this off for later (apologies if you do!).

Tail Recursion

Our recursive function isn't tail-recursive. Let's try to change it into one. We need some sort of an accumulator which will keep a running state of the reversed sublist. Once we get to a list of one element, we will simply join that element with the reversed sublist and make it the new head of the list. The following is a dry-run to demonstrate what I mean:

reverseList 1 2 3 -> call reverseList[2 3] with accumulator set to 1
reverseList 2 3 -> call reverseList 3 with accumulator set to 2 1
reverseList 3 -> end of list, return 3 joined with accumulator

Here's our tail-recursive function:

reverseList: {[list;acc] 
    $[1 = count list;
        list,acc;
        reverseList[1 _ list;(1#list),acc]
    ]
}

Tail recursion makes the function slightly more difficult to follow, but it does go easy on the stack.

reverseList[1 2 3;()]
-> 3 2 1
reverseList[`a`b`c`d;()]
-> `d`c`b`a

Notice the ugly () that we need to pass as the initial value of the accumulator - () denotes an empty list. We can clean up the function by hiding the () in an inner function:

reverseList: {[list] reverseListInner[list;()]}
reverseListInner: {[list;acc] 
    $[1 = count list;
        list,acc;
        reverseListInner[1 _ list;(1#list),acc]
    ]
}

Our solution obviously isn't as succinct as Q's, but we did learn the $, _, and # operators along the way.

reverseList 1 2 3
-> 3 2 1
reverseList 1
-> ,1

Ugh, looks like our function returns a list of one item when it's passed that item as an argument. Not really what we want. We could handle that case in our outer function:

reverseList: {[list] 
    $[1 = count list;
        list;
        reverseListInner[list;()]
    ]
}

reverseList 1
-> 1
reverseList 1 2 3
-> 3 2 1

To sum up, here's our solution:

reverseList: {[list] 
    $[1 = count list;
        list;
        reverseListInner[list;()]
    ]
}
reverseListInner: {[list;acc] 
    $[1 = count list;
        list,acc;
        reverseListInner[1 _ list;(1#list),acc]
    ]
}

It's ugly to make the same check (1 = count list) in two places for different purposes, but I'll call it a day at this point.

Koping with KDB 001: List Reversal

Ali Faizan Kazmi — Mon, 24 Dec 2018 16:39:54 +0000

Estimated reading time: 10 minutes

Preface: Hi y'all (and Merry Christmas)! Welcome to the first of a series of posts about kdb+ - a high-performance columnar database which, coupled with its query language Q, is used extensively in some areas of FinTech. More recently, kdb+ has also been applied to machine learning outside of FinTech.

My narrative technique can be non-linear at times: e.g., a section's title may not make sense unless you've read some or all of the section; it may not be obvious from a code snippet as to what I'm trying to achieve; or I may build up to a solution only to discard it in the next instant. This is by design. If this causes any inconvenience to you while reading then let me know and I'll be happy to go for a more linear approach.

Lastly, there is an inbuilt function in Q to reverse a given list but we're not gonna use it. We'll come up with our own solution instead and learn a few things along the way.

One of the first rules I learned when studying Q/kdb+ was that the Q/kdb+ interpreter evaluates expressions from right to left, even though expressions are typed left-to-right. For instance, the result of the following expression:

2*3+3

is 12, since the addition operator and its operands are evaluated first and the result of the addition in turn becomes the second operand for the * operator.

Sound simple enough? I certainly thought so, until my forehead landed on my palm a few minutes later.

Recursion?

I was attempting to define a simple function that would return true if it were passed a list as its argument:

isList: {[object] type object = 7h}

A breakdown of the above follows for the uninitiated:

: is the assignment operator
A function definition is encapsulated in curly brackets
A function's parameters are encapsulated in square brackets inside the function definition
= is the equality operator (since : takes care of assignment)
Each datatype in kdb is represented by a special 16-bit integer. In this case, we want the integer that represents the list datatype - 7h (well, not exactly)
Generally, a non-niladic function in kdb is invoked by passing it one or more arguments within square brackets. This is optional for monadic functions, though - as seen above in case of the type function

Back to our function definition. If, like me, you didn't immediately notice what was wrong then here it is: the expression

type object = 7h

is evaluated right-to-left, which means the expression is not performing the intended type check at all! From right to left, this expression contains two inner expressions evaluated in the following order:

type (object = 7h)

So, object = 7h evaluates to a boolean value (0b or 1b) which is then served as the argument to the type function. No wonder, then, that we get the following result when we invoke our function with a list of numbers:

isList 1 2 3
-> -1h

-1h is the numerical representation of the boolean datatype.

As an aside, lists in kdb are typically enclosed in round brackets and a semi-colon is used to separate list items. However, round brackets and semi-colons can be dropped for a list of atoms (known as primitives in languages like Java) where each atom is of the same datatype.

Here is the corrected version of the function:

isList: {[object] 7h = type object}

Which gives us the expected result when invoked with a list of numbers:

isList 1 2 3
-> 1b

Why do I want such a function, you ask? Because I would like to ultimately define a function that takes a list as an argument and returns another list with its elements in the reverse order. One way we could achieve a list reversal is via recursion and for recursion to work (or, more precisely, to stop!) we need a base case. In this example, the base case would be the point where we have reduced the provided list to its last element.

Really? Recursion?

Wait, do we really need recursion? Given that Q is an array programming language (among other things), could we not just pass a list of indices as an argument to our list in order to obtain a new reversed list? Of course, we'll need to make sure the list of indices is in reverse, too. But that shouldn't be difficult. To generate a list of indices, we can make use of the til function:

til 3
-> 0 1 2

The function can be used to obtain a list of valid indices for a list by using the count function:

list: 1 2 3
til count list
-> 0 1 2

Now, if we could reverse the list of indices then our problem should be solved:

list 2 1 0
-> 3 2 1

The following is one strategy to reverse this list:

The maximum valid index is -1 + count list (Am I the only one who came up with count list - 1 first?)
Subtracting a list of indices that is sorted in ascending order from the maximum valid index will yield a list that contains the same indices in reverse

In our case:

indices: til count list
2 - indices
-> 2 1 0

Great, now we need to wrap all of this into a function. We can't name our function reverse since that name is already reserved (for a function the definition of which I'm too scared to find out just yet). Here's the function:

reverseList: {
    [list] list (-1 + count list) - til count list
}

This seems to work correctly:

reverseList 1 2 3
-> 3 2 1

reverseList "level"
-> "level"
reverseList 1 0 1
-> 1 0 1
reverseList "Eva, can I stab bats in a cave?"
-> "?evac a ni stab bats I nac ,avE"

Apologies, I got carried away with palindromes.

reverseList 110b /List of booleans (incidentally, this is a comment)

-> 011b

reverseList 2018.09.23 2018.09.22 2018.09.21

-> 2018.09.21 2018.09.22 2018.09.23

Is our solution good enough?

Hardly. Why should we have to create a new list (i.e., the list of indices in reverse) in order to reverse a given list? Also, I don't like having to use parantheses to force the evaluation of an expression first - a sign that I'm still wet behind the ears vis-à-vis Q's right-to-left evaluation. Perhaps I should take a stab at recursion after all, or find a better solution as I continue to study Q and slowly shed the yoke of imperative/non-array programming paradigms.

DEV Community: Ali Faizan Kazmi

Koping with KDB 002: More List Reversal

Estimated reading time: 10 minutes

Give me your ifs, your elses...

...or just give me your ternaries

A simple(r) example

Finally, recursion

Detour: Q's reverse

Tail Recursion

Koping with KDB 001: List Reversal

Estimated reading time: 10 minutes

Recursion?

Really? Recursion?

Is our solution good enough?

Give me your `ifs`, your `elses`...

Detour: Q's `reverse`