defining trees, heaps in q

Community Support
1

ideas?

2

TGlzdCBvZiBsaXN0cywga2V5cyBhcyBhZGRyZXNzIC0gYWxsIHRoZSB0b29scyBhcmUgdGhlcmUg
dG8gInF1ZXJ5IiBhIG5lc3RlZCBsaXN0LCB0aG91Z2ggSSdtIG5vdCBzdXJlIG9mIHRoZSBsaW1p
dC4gT3IgZmxhdCBrZXllZCB0YWJsZS4NCg0KU2VudCB1c2luZyBCbGFja0JlcnJ5riBmcm9tIE9y
YW5nZQ0KDQotLS0tLU9yaWdpbmFsIE1lc3NhZ2UtLS0tLQ0KRnJvbTogImsub3MudGFvIiA8ay5v
cy50YW9AZ21haWwuY29tPg0KU2VuZGVyOiBwZXJzb25hbC1rZGJwbHVzQGdvb2dsZWdyb3Vwcy5j
b20NCkRhdGU6IEZyaSwgMyBEZWMgMjAxMCAxNDowMjowOCANClRvOiBLZGIrIFBlcnNvbmFsIERl
dmVsb3BlcnM8cGVyc29uYWwta2RicGx1c0Bnb29nbGVncm91cHMuY29tPg0KUmVwbHktVG86IHBl
cnNvbmFsLWtkYnBsdXNAZ29vZ2xlZ3JvdXBzLmNvbQ0KU3ViamVjdDogW3BlcnNvbmFsIGtkYitd
IGRlZmluaW5nIHRyZWVzLCBoZWFwcyBpbiBxDQoNCmlkZWFzPw0KDQotLSANCllvdSByZWNlaXZl
ZCB0aGlzIG1lc3NhZ2UgYmVjYXVzZSB5b3UgYXJlIHN1YnNjcmliZWQgdG8gdGhlIEdvb2dsZSBH
cm91cHMgIktkYisgUGVyc29uYWwgRGV2ZWxvcGVycyIgZ3JvdXAuDQpUbyBwb3N0IHRvIHRoaXMg
Z3JvdXAsIHNlbmQgZW1haWwgdG8gcGVyc29uYWwta2RicGx1c0Bnb29nbGVncm91cHMuY29tLg0K
VG8gdW5zdWJzY3JpYmUgZnJvbSB0aGlzIGdyb3VwLCBzZW5kIGVtYWlsIHRvIHBlcnNvbmFsLWtk
YnBsdXMrdW5zdWJzY3JpYmVAZ29vZ2xlZ3JvdXBzLmNvbS4NCkZvciBtb3JlIG9wdGlvbnMsIHZp
c2l0IHRoaXMgZ3JvdXAgYXQgaHR0cDovL2dyb3Vwcy5nb29nbGUuY29tL2dyb3VwL3BlcnNvbmFs
LWtkYnBsdXM/aGw9ZW4uDQoNCg==

3

to elaborate, i’m workng on a general recipe to convert trees totables and vice versa.On Dec 3, 5:12?pm, “Manish Patel” <manni.pa…> wrote:> List of lists, keys as address - all the tools are there to “query” a nested list, though I’m not sure of the limit. Or flat keyed table.>> Sent using BlackBerry? from Orange>> -----Original Message-----> From: “k.os.tao” <k.os…>>> Sender: personal-kdbplus@googlegroups.com> Date: Fri, 3 Dec 2010 14:02:08> To: Kdb+ Personal Developers> Reply-To: personal-kdbplus@googlegroups.com> Subject: [personal kdb+] defining trees, heaps in q>> ideas?>> –>

Submitted via Google Groups</k.os…></manni.pa…>

4

To: personal-kdbplus@googlegroups.com
X-Mailer: Apple Mail (2.1082)

links is one way to store a tree

q)t:(n:0 1 2 3 4;p:t!0N 0 0 1 1;v:abcde)
q)meta t

c t f a
n i
p i t
v s
q)select p.v from t
v

a
a
b
b
q)select p.p.v from t
v

a
a

5

To: personal-kdbplus@googlegroups.com
X-Mailer: Apple Mail (2.1081)

http://kx.com/q/tree.q
Attila
On 4 Dec 2010, at 00:56, Aaron Davies wrote:

> links is one way to store a tree
>
> q)t:(n:0 1 2 3 4;p:t!0N 0 0 1 1;v:abcde)
> q)meta t
> c| t f a
> -| -----
> n| i
> p| i t
> v| s
> q)select p.v from t
> v
> -
>
> a
> a
> b
> b
> q)select p.p.v from t
> v
> -
>
>
>
> a
> a
>
> On Dec 3, 2010, at 5:58 PM, k.os.tao wrote:
>
>> to elaborate, i’m workng on a general recipe to convert trees to
>> tables and vice versa.
>>
>> On Dec 3, 5:12 pm, “Manish Patel” <manni.pa…> wrote:
>>> List of lists, keys as address - all the tools are there to “query” =
a nested list, though I’m not sure of the limit. Or flat keyed table.
>>>
>>> Sent using BlackBerry=AE from Orange
>>>
>>> -----Original Message-----
>>> From: “k.os.tao” <k.os…>
>>>
>>> Sender: personal-kdbplus@googlegroups.com
>>> Date: Fri, 3 Dec 2010 14:02:08
>>> To: Kdb+ Personal Developers
>>> Reply-To: personal-kdbplus@googlegroups.com
>>> Subject: [personal kdb+] defining trees, heaps in q
>>>
>>> ideas?
>>>
>>> –
>>> You received this message because you are subscribed to the Google =
Groups “Kdb+ Personal Developers” group.
>>> To post to this group, send email to =
personal-kdbplus@googlegroups.com.
>>> To unsubscribe from this group, send email to =
personal-kdbplus+unsubscribe@googlegroups.com.
>>> For more options, visit this group =
athttp://groups.google.com/group/personal-kdbplus?hl=en.
>>
>> –
>> You received this message because you are subscribed to the Google =
Groups “Kdb+ Personal Developers” group.
>> To post to this group, send email to =
personal-kdbplus@googlegroups.com.
>> To unsubscribe from this group, send email to =
personal-kdbplus+unsubscribe@googlegroups.com.
>> For more options, visit this group at =
http://groups.google.com/group/personal-kdbplus?hl=en.
>>
>
> –
> Aaron Davies
> aaron.davies@gmail.com
>
> –
> You received this message because you are subscribed to the Google =
Groups “Kdb+ Personal Developers” group.
> To post to this group, send email to =
personal-kdbplus@googlegroups.com.
> To unsubscribe from this group, send email to =
personal-kdbplus+unsubscribe@googlegroups.com.
> For more options, visit this group at =
http://groups.google.com/group/personal-kdbplus?hl=en.
>


</k.os…></manni.pa…>

6

https://github.com/KxSystems/kdb/blob/master/tree.qhttps://github.com/KxSystems/kdb/blob/master/tree.q

v:“abcde” / some values with weights 1 2 3 4 5
d:v!(0 1 0;0 1 1;0 0;1 0;1 1) / huffman write tree

t:(6 7;6 7;6 7;6 7;6 7;0 1;2 5;3 4;6 7) / huffman read matrix

bd:{raze d x} / bits from data

db:{v x where count[v]>x:0 t\x} / data from bits
db bd v

Could someone explain what  “0 t\x” does? why doesn’t “t\x” work?

q)v

“abcde”

q)d

a| 0 1 0

b| 0 1 1

c| 0 0

d| 1 0

e| 1 1

q)0 t(raze d v)

6 5 0 6 5 1 6 2 7 3 7 4

q)t(raze d v)

'</font>

[0] t(raze d v)

^

q)

Thanks!

-Anuj

7

> Could someone explain what  “0 t\x” does? why doesn’t “t\x” work?

q’s syntax parsing is getting in the way. you have two options:

use ‘scan’ - which is defined as {x\y} in k

q)t scan raze d v
0 7 3 6 5 1 6 2 7 3 7 4

or force monadic evaluation:

q)t[raze d v]
0 7 3 6 5 1 6 2 7 3 7 4

the same hold for ‘over’:

q)t over raze d v
4
q)t/[raze d v]
4

8

Q parsing – to expand on what Nick wrote:

Scan and over are adverbs applied postfix. In the familiar plus over (i.e. sum) / takes one argument, the + function. The result is a derived function or derivative, +/. In your example t</font> is a derivative.


These (and other) derivatives are ambivalent, i.e. they can be applied to one or two arguments.


q)+/[10;2 3 4]   / argument list has two items

19

q)+/[2 3 4] / argument list has one item

9

The ambivalence means the derivative can be evaluated on one argument without forming a projection, which a binary function normally would. To project an ambivalent derivative, make the projection explicit by including the semicolon separator – always a good practice for projections. 

q)+/[;2 3 4] 10 / argument list omits first item

19

Ambivalent derivatives can also be applied infix.

q)10 +/2 3 4 / applied infix

19

q)0 t\raze d v
6 5 0 6 5 1 6 2 7 3 7 4

Unary functions can be applied by juxtaposition. 

q)count 2 3 4

3

To apply an ambivalent derivative by juxtaposition, we need to select its unary form. Parentheses do that.

q)(+/)2 3 4
9
q)(t)raze d v
0 7 3 6 5 1 6 2 7 3 7 4

HTH
Stephen






Stephen Taylor | Librarian | Kx | +44 7713 400852 | stephen@kx.com