How to determine if a key exists in a <table>?
Author Message How to determine if a key exists in a <table>?

Is there a simple way to determine if a key exists in a table?  Of course
there is the direct approach:

define method has-key?(table :: <table>, key) => (yes :: <boolean>)
member?(key, key-sequence(table))
end method has-key?;

But this computes a sequence (a list in Harlequin Dylan) of all of the keys
and then searches the sequence.  Not very efficient if the table is large.
Another option is to use conditions (I am fiddling around with memoization):

define method fib(n :: <integer>) => (item :: <integer>)
block()
*fib-table*[n]
exception (except :: <simple-error>)
if (n < 3)
*fib-table*[n] := 1;
else
*fib-table*[n] := fib(n - 1) + fib(n - 2);
end if;
end block;
end method fib;

That eliminates the search, but I'm not sure this is efficient (depending on
the implementation of conditions), and using a handler here seems a bit
frightening -- in this case it is probably safe, but what if that first
expression were more involved and some other <simple-error> occurred?

Thanks for any suggestions!

Sun, 13 May 2001 03:00:00 GMT  How to determine if a key exists in a <table>?

Quote:

>Is there a simple way to determine if a key exists in a table?  Of course
>there is the direct approach:

>define method has-key?(table :: <table>, key) => (yes :: <boolean>)
>  member?(key, key-sequence(table))
>end method has-key?;

>But this computes a sequence (a list in Harlequin Dylan) of all of the keys
>and then searches the sequence.  Not very efficient if the table is large.
>Another option is to use conditions (I am fiddling around with memoization):

>define method fib(n :: <integer>) => (item :: <integer>)
>  block()
>    *fib-table*[n]
>  exception (except :: <simple-error>)
>    if (n < 3)
>      *fib-table*[n] := 1;
>    else
>      *fib-table*[n] := fib(n - 1) + fib(n - 2);
>    end if;
>  end block;
>end method fib;

>That eliminates the search, but I'm not sure this is efficient (depending on
>the implementation of conditions), and using a handler here seems a bit
>frightening -- in this case it is probably safe, but what if that first
>expression were more involved and some other <simple-error> occurred?

>Thanks for any suggestions!

define method fib(n :: <integer>) => (item :: <integer>)
element(*fib-table*, n, #f) |
(*fib-table*[n] := if (n < 3) 1 else fib(n - 1) + fib(n - 2) end if);
end method fib;

Remember [] is just a short-hand for element.

________________________________________________________________
Callitrope/The Art of Computing      <http://www.callitrope.com>

post:Callitrope/168 Old Sandwich Road/Plymouth/MA/02360-2507/USA

Sun, 13 May 2001 03:00:00 GMT  How to determine if a key exists in a <table>?

Quote:

>> define method fib(n :: <integer>) => (item :: <integer>)
>>   element(*fib-table*, n, default: #f) |
>>     (*fib-table*[n] := if (n < 3) 1 else fib(n - 1) + fib(n - 2) end if);
>> end method fib;

>> Remember [] is just a short-hand for element.

>and don't forget the "default:" keyword before the #f either... :-j

Duh.  Thanks.

Sun, 13 May 2001 03:00:00 GMT  How to determine if a key exists in a <table>?

Quote:

> define method fib(n :: <integer>) => (item :: <integer>)
>   element(*fib-table*, n, #f) |
>     (*fib-table*[n] := if (n < 3) 1 else fib(n - 1) + fib(n - 2) end if);
> end method fib;

> Remember [] is just a short-hand for element.

and don't forget the "default:" keyword before the #f either... :-j

__Jason

Sun, 13 May 2001 03:00:00 GMT  How to determine if a key exists in a <table>?

Quote:
>define method fib(n :: <integer>) => (item :: <integer>)
>  element(*fib-table*, n, #f) |
>    (*fib-table*[n] := if (n < 3) 1 else fib(n - 1) + fib(n - 2) end if);
>end method fib;

The second line should be

element(*fib-table*, n, default: #f) |

Quote:
>Remember [] is just a short-hand for element.

Indeed.

Sun, 13 May 2001 03:00:00 GMT  How to determine if a key exists in a <table>?

Quote:

>Is there a simple way to determine if a key exists in a table?

I use the element method explicitly passing it the 'default:' keyword like
follows:

define table \$my-table =
{
#"one" => 1,
#"two" => 2,
#"three" => 3

Quote:
};

Instead of \$my-table[#"two"] I use:

element(\$my-table, #"two", default: #f) which in this case will return 2.
element(\$my-table, #"nine", default: #f) will return #f, the default I
specified if the key does not exist in the table.

Using this your fib function could become something like:

define method fib(n :: <integer>) => (item :: <integer>)
local method compute-fib()
if(n < 3)
*fib-table*[n] := 1
else
*fib-table*[n] := fib(n - 1) + fib(n - 2)
end if;
end method compute-fib;

// Return the element in the table, if no element exists compute the fib,
// store it in the table and return it.
element(*fib-table*, n, default: #f) | compute-fib();

end method fib;

Chris.
--
http://www.cnd.co.nz/dylan

Mon, 14 May 2001 03:00:00 GMT  How to determine if a key exists in a <table>?

Quote:

> >Is there a simple way to determine if a key exists in a table?

> I use the element method explicitly passing it the 'default:' keyword ...};

> Instead of \$my-table[#"two"] I use:

> element(\$my-table, #"two", default: #f) which in this case will return 2.
> element(\$my-table, #"nine", default: #f) will return #f, the default I
> specified if the key does not exist in the table.
> ...
> Chris.

BTW, in case your table needs to contain #f (and in case it's not obvious
:-), you can invent some other unique object which you guarantee not to
store in your table.  For convenience and canonicality(?), Harlequin Dylan
gives you \$unfound and predicates like found?, but it's trivial to write
your own if need be.

Unfortunately, this makes the idiom

element(*fib-table*, n, default: #f) | compute-fib();

somewhat more verbose:

let fib-n = element(*fib-table*, n, default: \$unfound)
if (unfound?(fib-n)) compute-fib() else fib-n end;
// Instead of: element(*fib-table*, n, default: #f) | compute-fib();

I've often found myself wishing element had a "deferred-default:" keyword,
like "make(<class>, ...)" accepts a "deferred-type:" keyword for its
slot-specs.

Hugh G. Greene

Sat, 19 May 2001 03:00:00 GMT

 Page 1 of 1 [ 7 post ]

Relevant Pages

Powered by phpBB® Forum Software