jack@cs.glasgow.ac.uk (Jack Campin) (08/08/90)
I've just been reading Geurts, Meertens and Pemberton's "ABC Programmer's Handbook" (Prentice-Hall, ISBN 0-13-000027-2). ABC has a useful type constructor called the "table", which allows associative access to values of any type based on keys of any type. There seems to be one rather important facility missing: a way to test if a key is present in a table. There IS a direct way to test if a <key, value> pair is present, but the only way the book describes to test for a key alone is by first constructing a sorted list of the keys (using a standard function "keys") and then testing the key's presence in the list. They don't describe the way "keys" works, but nothing suggests that it's lazy. If it isn't, this is unacceptably inefficient for an application that performs a long series of query-and-update transactions on a large persistent table. Workarounds? Do I have to run "keys" at the start of the application and then maintain an update log? Not very elegant. -- -- Jack Campin Computing Science Department, Glasgow University, 17 Lilybank Gardens, Glasgow G12 8QQ, Scotland 041 339 8855 x6044 work 041 556 1878 home JANET: jack@cs.glasgow.ac.uk BANG!net: via mcsun and ukc FAX: 041 330 4913 INTERNET: via nsfnet-relay.ac.uk BITNET: via UKACRL UUCP: jack@glasgow.uucp
steven@cwi.nl (Steven Pemberton) (08/10/90)
In article <5989@vanuata.cs.glasgow.ac.uk> jack@cs.glasgow.ac.uk (Jack Campin) writes: > ABC has a useful type constructor called the "table", which allows > associative access to values of any type based on keys of any type. > There seems to be one rather important facility missing: a way to test > if a key is present in a table. In fact there is a way (as he later points out indirectly); you just say; IF x in keys table: WRITE "whoopee!" > There IS a direct way to test if a <key, value> pair is present, In fact, there isn't such a way; you have to say: IF x in keys table AND table[x] = y: ... though you could write a predicate: HOW TO REPORT (key, value) within table: REPORT key in keys table AND table[key] = value and then write IF (x, y) within table: ... > the only way the book describes to test for a key alone is by first > constructing a sorted list of the keys (using a standard function > "keys") and then testing the key's presence in the list. They don't > describe the way "keys" works, but nothing suggests that it's lazy. On the other hand, the book doesn't say it's not lazy either. The truth of the matter is that the implementation performs exactly as you want it to in this case. 'Keys' is extremely lazy, and refuses to construct the list unless you PUT it somewhere and modify it. This means that "IF x in keys table:" costs O(log(#table)), since the keys of a table are already sorted. Tables (and lists, and texts) are implemented as b-trees, so the constant factor is relatively low. By the way, ranges are lazy too: IF i in {1..2**1000}: costs roughly the same as IF 1 <= i <= 2**1000: Steven Pemberton, CWI, Amsterdam; steven@cwi.nl Aministriviator of the ABC mailing list; to join send your email address to abc-list-request@cwi.nl