Search code examples
kdbq-lang

q - recursion with /


In q, a common illustration for the over operator / is the implementation of fibonacci sequence

10 {x,sum -2#x}/ 1 1

This indeed prints the first 10 fibonacci numbers but doesn't make sense in regards of the definition of the over operator in this whitepaper (page 8)

With two arguments, the second one being a list, the function is called with the left argument as its first parameter and the first element of the right argument as the second parameter. Next, the function is called with the result of the previous iteration as the first parameter and the third element as the second parameter. The process continues in this way for the remaining elements of the list.

So in the fibonacci example above, at the first iteration the function would be called with [10;1] ("first parameter and first item of second parameter") which would already give an incorrect result.

My implementation is in line with the definition (and works)

1 1 {[l;c] l,sum -2#l}/til 10

but I don't like it because the parameter c is never used.

How can the first example be reconciled with the definition?

Thanks for the help


Solution

  • / has a number of forms, described here: https://code.kx.com/q/ref/adverbs

    The specific form being used here is "repeat" - https://code.kx.com/q/ref/adverbs/#converge-repeat

    The fibonacci function here is monadic i.e. takes one parameter (x)

    In this form, / will run the function with the supplied parameter (i.e. the list of 1 1), and then with the result of that call, and then again with the result of that call and so, until the number of iterations reaches 10 (the left argument to /)

    The definition you provide is true if the function is a dyadic function (i.e. takes two parameters)

    Hope this helps

    Jonathon

    AquaQ Analytics