Friday, October 16, 2015

A Combinatoric Combinator

I wrote this while I was playing around with using q on a hobby project, and I thought I’d share it in case anyone else might find it useful.

It takes a number `k`, a function `f`, and a list or dictionary `y` of count `n`, and runs `f` once for each of the k-combinations of `y`. The result is returned as a dictionary with the function outputs as its values and its keys determined by the type of `y`: if `y` is a list, its keys are the subsets of `y` that produced the outputs; if `y` is a dictionary, its keys are the subsets of the keys of `y` that index the subsets of `y` that produced the outputs.

``````eachc:{
c:(where reverse 0b vs)each c@:where((first x)=sum 0b vs)each c:til"j"\$2 xexp count y;
(last x)peach\$[99h=type y;(key each y)!y:y{((key x)y)#x}/:c;y!y:y@/:c]}
``````

Examples:

```q)eachc[(3;sum)]til 5
0 1 2| 3
0 1 3| 4
0 2 3| 5
1 2 3| 6
0 1 4| 5
0 2 4| 6
1 2 4| 7
0 3 4| 7
1 3 4| 8
2 3 4| 9
q)eachc[(3;sum)]`a`b`c`d`e!til 5
a b c| 3
a b d| 4
a c d| 5
b c d| 6
a b e| 5
a c e| 6
b c e| 7
a d e| 7
b d e| 8
c d e| 9
q)
```

Notes and caveats:

On little-endian machines (i.e. Sparc), the `reverse` will probably need to be removed.

The size of the result set gets very big very quickly—an `n` of thirty is probably infeasible for most machines.

I’ve written it to execute `f` on the combinations with `peach`, rather than `each`; this may or may not be appropriate, depending on the nature of any given `f` and `y`.

Monday, June 8, 2015

Riddle 3: not x~string`\$x

Here’s an easy one:

When will `{(10h=type x)&not x~string`\$x}` return true (`1b`)?

Slightly harder:

In cases where this is problematic, what can be done about it?

Labels:

Friday, April 24, 2015

Name! That! Function! (Pivot Table Edition)

What time is it, kids? That’s right, it’s time to play Name! That! Function!

Seriously though, I have a small, useful (IMAO) function I’ve been entering freehand in the console for something like two years now.

Normally, I’d put it in my personal library, but there’s a problem—I can’t think of a good name for it.

Here’s the function: `{((union)over key each x)#/:x}`.

And here it is in context, showing what it’s good for:

```q)t:([]id:1 1 2 2 3;k:`a`b`b`a`b;v:1 2 3 4 5)
q)t
id k v
------
1  a 1
1  b 2
2  b 3
2  a 4
3  b 5
q)exec k!v by id:id from t
id|
--| --------
1 | `a`b!1 2
2 | `b`a!3 4
3 | (,`b)!,5
q){((union)over key each x)#/:x}exec k!v by id:id from t
id| a b
--| ---
1 | 1 2
2 | 4 3
3 |   5
q)```

So, there it is—an easy way to fix up ad-hoc pivots1 when your data doesn’t have all keys present (and in the same order) on all ids.

Anyone have any ideas what to call it?

1. Note that for production pivots, particularly if they involve significant amounts of data, you should be using an optimized pivot function.

Monday, March 9, 2015

This is somewhat esoteric, and I wouldn’t be surprised if very few people had any idea what I was even asking. I discovered this largely by chance, while fiddling around with function bytecode, though I think it could be deduced from observation without that.

`::` is usually taught as a sui generis operator, called “global amend”, which has the specific behavior (when used as a verb inside a function) of setting a global variable (instead of the local one that `:` would set in the same place). No connection is typically drawn between it and any other operator (other than `:`).

However, I’m pretty sure this is inaccurate. While obviously I don’t know for certain, I strongly suspect that there is no code anywhere in the q binary saying that `::` is defined as “global amend”. Rather, it is a specific case of the dyadic “`f:`” pattern, where `f` is some dyadic function—e.g. dyadic `+:`, `-:`, `*:`, etc.

These all have the same behavior—`x f:y` is defined as `x:x f y`.

Additionally, when used inside functions on variables that have not been identified by the compiler as locals, they modify (and if necessary, create), global variables.

```q){a:1;a+:1;a}[]
2
q)a
'a
q){a+:1}[]
q)a
1
q)```

It follows that if `f` is `:`, then the operation involved is assignment, and so `x` gets `y` assigned to it, as a global variable if not identified as a local variable.

In fact, this can be seen in the same way:

```q){a:1;a::2;a}[]
2
q)a
'a
q){a::2}[]
q)a
2
q)```

Thus arises “global amend”.

If anything, the “create view” sense of `::` must be the special case, as ordinarily, dyadic `f:` verbs behave identically inside and outside functions.

Labels: , ,

Monday, January 19, 2015

Riddle 2: “:: is not a special case”

(I suppose it’s a good thing I only said I’d be posting riddles “occasionally”, as it’s now almost two years since I last posted one.)

Referring specifically to the “global amend” sense, I make the claim that `::` is not a special case.

What do I mean by this?

Labels:

Wednesday, October 9, 2013

I appear to have left Riddle 1 sitting out there without an official answer for almost seven months now. Sorry about that.

The answer given by Peter Byrne was valid, and essentially the one I was thinking of: while his example dealt with the untyped empty list `()`, I had the typed empty list ``boolean\$()` in mind.

The insight here is that `any` and `all` are forms of `min` and `max`; and that `min x,y`, the min of the concatenation of two lists, is equal to `min(min x;min y)`, the min of their separate `min`s (and mutatis mutandis for `max`). For this to work consistently for empty lists, the `min` of an empty list must be the maximum possible value for that data type (and mutatis mutandis for `max`).

Labels: , ,

Quick Tip: Intra-Statement Breakpoints

A statement referencing a non-existent variable is a common way to add a breakpoint to a `q` function.
`q)f:{x:x+1;break;x+2}`
While this is handy, it only lets you break between statements. A simple extension lets you break within statements, inspecting values at arbitrary points in the code, and continuing with execution once you’re done:
`q)f:{x:x+1;{break;x}x+2}`
Now, the break will occur after the portion of the statement to the right of the break function has executed, and `x` within the break function will have the value returned by that code. Since the break statement itself has no effects, and `x` contains the value returned by the code executed so far, typing `:` to continue will allow the rest of the break function to execute, returning `x` leftwards and allowing the rest of the statement to execute as if nothing had interrupted it.

Note that this is entirely legal inside `qsql` queries; I’ve often found it of particular utility there, since you can’t create new local variables inside a query. Unfortunately no specific examples come to mind at the moment; I’ll try to post one later to make it clearer how this technique works.

Labels: ,