Estimated reading time: 10 minutes

In the previouspost 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 yourifs, yourelses...

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 theif statement:

n: 1if[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 booleanfalse) 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 variablemessage.

As an aside, notice that the concept of scope doesn't apply here: the variablemessage is defined inside theif 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 anelse clause - something like the following:

if base case reached    returnelse    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 or0b) 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-> 2b-> 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 ofprintln 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@ and2008 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: thejoin operator, used to join two lists. The operator is simply a comma:

1 2 3,4 5 6-> 1 2 3 4 5 61,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 thecut (_) operator:

list: 1 2 31 _ 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-> 1reverseList 1 2-> 2 1reverseList 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 3reverseList 3 -> return 3reverseList 2 3 -> return 3 joined with 2reverseList 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 LIts 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 thetake (#) operator:

list: 1 2 31#list-> ,1

The comma before1 is just a way of indicating that1 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-> 1reverseList 1 2-> 2 1reverseList 1 2 3-> 3 2 1reverseList "A string is a list of characters"-> "sretcarahc fo tsil a si gnirts A"reverseList "Sigh of relief"-> "feiler fo hgiS"

Detour: Q'sreverse

I mentioned earlier that Q already has areverse 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 fromk, 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'ttail-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 1reverseList 2 3 -> call reverseList 3 with accumulator set to 2 1reverseList 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 1reverseList[`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 1reverseList 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-> 1reverseList 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.