Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uunet!mcsun!hp4nl!charon!steven
From: steven@cwi.nl (Steven Pemberton)
Newsgroups: comp.lang.misc
Subject: Re: testing whether a key is present in an ABC table
Message-ID: <1952@charon.cwi.nl>
Date: 10 Aug 90 12:55:33 GMT
References: <5989@vanuata.cs.glasgow.ac.uk>
Sender: news@cwi.nl
Organization: CWI, Amsterdam
Lines: 52

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