/**
 * 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@cs.uu.nl> - 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)