/** * This module contains strategies for working on associative lists. * * Associative lists are on the form [(key1, value1), (key2, value2), ...] * Each key must be unique for the strategies in this module to operate * correctly. Any term can be used as key. * * The associative lists must be created correctly by the application code; * this module only contains strategies for searching associative lists. * * Keys may have annotations. These are considered to be part of the key, * so identical term with differing annotations are effectively different * keys. * * @author Eelco Visser <visser@acm.org> * @author Karl Trygve Kalleberg <karltk@strategoxt.org> - documentation * */ module collection/list/lookup imports collection/list/common strategies /** * Lookup the first value associated with a key in an associative * list. An associative list is a list of key-value pairs. * * Note: If multiple identical keys exist, only the value for the * first will be retrieved. * * Example: * <lookup> (2, [(1, "a"), (2, "b"), (3, "c")]) => "b" * * @type k * List(k * v) -> v */ lookup = rec x(Look1 <+ Look2 ; x) /** * Find first element of a list to which s applies. * The result is the application of s to this element. * * @type s a -> b * @type List(a) -> b */ getfirst(s) = rec x(Hd; s <+ Tl; x) /** * Faster version of lookup. * * The advantage over lookup is that lookup' does not construct * intermediate pairs. * * @type k * List(k * v) -> v * @internal */ lookup' = {x, xs: ?(x, xs) ; <getfirst({y: ?(x, y); !y})> xs} /** * Looks up the first value associated with a particular key * in an associative list, using keyeq to do key comparisons. * * @type k * List(k * v) -> v */ lookup(keyeq) = rec x((Look1'(keyeq) <+ Look2; x)) rules /** @internal */ Look1 : (x, [(x, y)|_]) -> y /** @internal */ Look2 : (x, [_|xs]) -> (x, xs) /** @internal */ Look1'(keyeq) : (x, [y|_]) -> y where <keyeq> (x, y)