core/assocs/assocs-docs.factor

   1 ! Copyright (C) 2007, 2009 Daniel Ehrenberg, Slava Pestov, and Doug Coleman
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: help.markup help.syntax kernel sequences
   4 sequences.private namespaces math quotations assocs.private
   5 sets ;
   6 IN: assocs
   7
   8 ARTICLE: "alists" "Association lists"
   9 "An " { $emphasis "association list" } ", abbreviated " { $emphasis "alist" } ", is an association represented as a sequence where all elements are key/value pairs. The " { $link sequence } " mixin is an instance of the " { $link assoc } " mixin, hence all sequences support the " { $link "assocs-protocol" } " in this way."
  10 $nl
  11 "While not an association list, note that " { $link f } " also implements the associative mapping protocol in a trivial way; it is an immutable assoc with no entries."
  12 $nl
  13 "An alist is slower to search than a hashtable for a large set of associations. The main advantage of an association list is that the elements are ordered; also sometimes it is more convenient to construct an association list with sequence words than to construct a hashtable with association words. Much of the time, hashtables are more appropriate. See " { $link "hashtables" } "."
  14 $nl
  15 "There is no special syntax for literal alists since they are just sequences; in practice, literals look like so:"
  16 { $code "{" "    { key1 value1 }" "    { key2 value2 }" "}" }
  17 "To make an assoc into an alist:"
  18 { $subsections >alist } ;
  19
  20 ARTICLE: "enums" "Enumerations"
  21 "An enumeration provides a view of a sequence as an assoc mapping integer indices to elements:"
  22 { $subsections
  23     enum
  24     <enum>
  25 }
  26 "Inverting a permutation using enumerations:"
  27 { $example "IN: scratchpad" ": invert ( perm -- perm' )" "    <enum> sort-values keys ;" "{ 2 0 4 1 3 } invert ." "{ 1 3 0 4 2 }" } ;
  28
  29 HELP: enum
  30 { $class-description "An associative structure which wraps a sequence and maps integers to the corresponding elements of the sequence."
  31 $nl
  32 "Enumerations are mutable; note that deleting a key calls " { $link remove-nth! } ", which results in all subsequent elements being shifted down." } ;
  33
  34 HELP: <enum>
  35 { $values { "seq" sequence } { "enum" enum } }
  36 { $description "Creates a new enumeration." } ;
  37
  38 ARTICLE: "assocs-protocol" "Associative mapping protocol"
  39 "All associative mappings must be instances of a mixin class:"
  40 { $subsections
  41     assoc
  42     assoc?
  43 }
  44 "All associative mappings must implement methods on the following generic words:"
  45 { $subsections
  46     at*
  47     assoc-size
  48     >alist
  49 }
  50 "Mutable assocs should implement the following additional words:"
  51 { $subsections
  52     set-at
  53     delete-at
  54     clear-assoc
  55 }
  56 "The following three words are optional:"
  57 { $subsections
  58     value-at*
  59     new-assoc
  60     assoc-like
  61 }
  62 "Assocs should also implement methods on the " { $link clone } ", " { $link equal? } " and " { $link hashcode* } " generic words. Two utility words will help with the implementation of the last two:"
  63 { $subsections
  64     assoc=
  65     assoc-hashcode
  66 }
  67 "Finally, assoc classes should define a word for converting other types of assocs; conventionally, such words are named " { $snippet ">" { $emphasis "class" } } " where " { $snippet { $emphasis "class" } } " is the class name. Such a word can be implemented using a utility:"
  68 { $subsections assoc-clone-like } ;
  69
  70 ARTICLE: "assocs-lookup" "Lookup and querying of assocs"
  71 "Utility operations built up from the " { $link "assocs-protocol" } ":"
  72 { $subsections
  73     key?
  74     at
  75     ?at
  76     of
  77     ?of
  78     assoc-empty?
  79     keys
  80     values
  81     assoc-stack
  82 }
  83 { $see-also at* assoc-size } ;
  84
  85 ARTICLE: "assocs-values" "Transposed assoc operations"
  86 "Most assoc words take a key and find the corresponding value. The following words take a value and find the corresponding key:"
  87 { $subsections
  88     value-at
  89     value-at*
  90     value?
  91 }
  92 "With most assoc implementations, these words runs in linear time, proportional to the number of entries in the assoc. For fast value lookups, use " { $vocab-link "biassocs" } "." ;
  93
  94 ARTICLE: "assocs-sets" "Set-theoretic operations on assocs"
  95 "It is often useful to use the keys of an associative mapping as a set, exploiting the constant or logarithmic lookup time of most implementations (" { $link "alists" } " being a notable exception)."
  96 $nl
  97 "Set-theoretic operations:"
  98 { $subsections
  99     assoc-subset?
 100     assoc-intersect
 101     assoc-union
 102     assoc-diff
 103     substitute
 104     extract-keys
 105 }
 106 "Adding elements to sets:"
 107 { $subsections
 108     conjoin
 109     conjoin-at
 110 }
 111 "Destructive operations:"
 112 { $subsections
 113     assoc-union!
 114     assoc-diff!
 115 }
 116 { $see-also key? assoc-any? assoc-all? "sets" } ;
 117
 118 ARTICLE: "assocs-mutation" "Storing keys and values in assocs"
 119 "Utility operations built up from the " { $link "assocs-protocol" } ":"
 120 { $subsections
 121     delete-at*
 122     rename-at
 123     change-at
 124     at+
 125     inc-at
 126 }
 127 { $see-also set-at delete-at clear-assoc push-at } ;
 128
 129 ARTICLE: "assocs-conversions" "Associative mapping conversions"
 130 "Converting to other assocs:"
 131 { $subsections assoc-clone-like }
 132 "Combining a sequence of assocs into a single assoc:"
 133 { $subsections assoc-combine }
 134 "Creating an assoc from key/value sequences:"
 135 { $subsections zip zip-as }
 136 "Creating an assoc from key/value sequences and their indices:"
 137 { $subsections zip-index zip-index-as }
 138 "Creating key/value sequences from an assoc:"
 139 { $subsections unzip }
 140 ;
 141
 142 ARTICLE: "assocs-combinators" "Associative mapping combinators"
 143 "The following combinators can be used on any associative mapping."
 144 $nl
 145 "The " { $link assoc-find } " combinator is part of the " { $link "assocs-protocol" } " and must be implemented once for each class of assoc. All other combinators are implemented in terms of this combinator."
 146 $nl
 147 "The standard functional programming idioms:"
 148 { $subsections
 149     assoc-each
 150     assoc-find
 151     assoc-map
 152     assoc-filter
 153     assoc-filter-as
 154     assoc-reject
 155     assoc-reject-as
 156     assoc-partition
 157     assoc-any?
 158     assoc-all?
 159 }
 160 "Removing empty keys or values:"
 161 { $subsections
 162     sift-keys
 163     sift-values
 164     harvest-keys
 165     harvest-values
 166 }
 167 "Mapping between assocs and sequences:"
 168 { $subsections
 169     map>assoc
 170     map>alist
 171     assoc>map
 172     assoc-map-as
 173 }
 174 "Destructive combinators:"
 175 { $subsections
 176     assoc-filter!
 177     assoc-reject!
 178     cache
 179     2cache
 180 } ;
 181
 182 ARTICLE: "assocs" "Associative mapping operations"
 183 "An " { $emphasis "associative mapping" } ", abbreviated " { $emphasis "assoc" } ", is a collection of key/value pairs which provides efficient lookup and storage indexed by key."
 184 $nl
 185 "Words used for working with assocs are in the " { $vocab-link "assocs" } " vocabulary."
 186 $nl
 187 "Associative mappings implement a protocol:"
 188 { $subsections "assocs-protocol" }
 189 "A large set of utility words work on any object whose class implements the associative mapping protocol."
 190 { $subsections
 191     "assocs-lookup"
 192     "assocs-values"
 193     "assocs-mutation"
 194     "assocs-combinators"
 195     "assocs-sets"
 196     "assocs-conversions"
 197 } ;
 198
 199 ABOUT: "assocs"
 200
 201 HELP: assoc
 202 { $class-description "A mixin class whose instances are associative mappings. Custom implementations of the assoc protocol should be declared as instances of this mixin for all assoc functionality to work correctly:"
 203     { $code "INSTANCE: avl-tree assoc" }
 204 } ;
 205
 206 HELP: at*
 207 { $values { "key" "an object to look up in the assoc" } { "assoc" assoc } { "value/f" "the value associated to the key, or " { $link f } " if the key is not present in the assoc" } { "?" "a " { $link boolean } " indicating if the key was present" } }
 208 { $contract "Looks up the value associated with a key. The boolean flag can decide between the case of a missing value, and a value of " { $link f } "." } ;
 209
 210 HELP: set-at
 211 { $values { "value" "a value" } { "key" "a key to add" } { "assoc" assoc } }
 212 { $contract "Stores the key/value pair into the assoc." }
 213 { $side-effects "assoc" } ;
 214
 215 HELP: new-assoc
 216 { $values { "capacity" "a non-negative integer" } { "exemplar" assoc } { "newassoc" assoc } }
 217 { $contract "Creates a new assoc from an " { $snippet "exemplar" } " which can hold " { $snippet "capacity" } " entries before growing." } ;
 218
 219 HELP: assoc-find
 220 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } { "key" "the successful key, or f" } { "value" "the successful value, or f" } { "?" boolean } }
 221 { $description "Applies a predicate quotation to each entry in the assoc. Returns the key and value that the quotation succeeds on, or " { $link f } " for both if the quotation fails. It also returns a boolean describing whether there was anything found; this can be used to distinguish between a key and a value equal to " { $link f } ", or nothing being found." } ;
 222
 223 HELP: clear-assoc
 224 { $values { "assoc" assoc } }
 225 { $contract "Removes all entries from the assoc." }
 226 { $side-effects "assoc" } ;
 227
 228 HELP: delete-at
 229 { $values { "key" "a key" } { "assoc" assoc } }
 230 { $contract "Removes an entry from the assoc." }
 231 { $side-effects "assoc" } ;
 232
 233 HELP: assoc-size
 234 { $values { "assoc" assoc } { "n" "a non-negative integer" } }
 235 { $contract "Outputs the number of entries stored in the assoc." } ;
 236
 237 HELP: assoc-like
 238 { $values { "assoc" assoc } { "exemplar" assoc } { "newassoc" "a new assoc" } }
 239 { $contract "Creates a new assoc having the same entries as " { $snippet "assoc" } " and the same type as " { $snippet "exemplar" } "." } ;
 240
 241 HELP: assoc-empty?
 242 { $values { "assoc" assoc } { "?" boolean } }
 243 { $description "Tests if the assoc contains no entries." } ;
 244
 245 HELP: key?
 246 { $values { "key" object } { "assoc" assoc } { "?" boolean } }
 247 { $description "Tests if an assoc contains a key." } ;
 248
 249 { at at* key? ?at of ?of } related-words
 250
 251 HELP: at
 252 { $values { "key" object } { "assoc" assoc } { "value/f" "the value associated to the key, or " { $link f } " if the key is not present in the assoc" } }
 253 { $description "Looks up the value associated with a key. This word makes no distinction between a missing value and a value set to " { $link f } "; if the difference is important, use " { $link at* } "." } ;
 254
 255 HELP: ?at
 256 { $values { "key" object } { "assoc" assoc } { "value/key" "the value associated to the key, or the key if the key is not present in the assoc" } { "?" "a " { $link boolean } " indicating if the key was present" } }
 257 { $description "Looks up the value associated with a key. If the key was not present, an error can be thrown without extra stack shuffling. This word handles assocs that store " { $link f } "." } ;
 258
 259 HELP: of
 260 { $values { "assoc" assoc } { "key" object } { "value/f" "the value associated to the key, or " { $link f } " if the key is not present in the assoc" } }
 261 { $description "Looks up the value associated with a key. This word makes no distinction between a missing value and a value set to " { $link f } "; if the difference is important, use " { $link ?of } "." } ;
 262
 263 HELP: ?of
 264 { $values { "assoc" assoc } { "key" object } { "value/key" "the value associated to the key, or the key if the key is not present in the assoc" } { "?" "a " { $link boolean } " indicating if the key was present" } }
 265 { $description "Looks up the value associated with a key. If the key was not present, an error can be thrown without extra stack shuffling. This word handles assocs that store " { $link f } "." } ;
 266
 267 HELP: assoc-each
 268 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ) } } }
 269 { $description "Applies a quotation to each entry in the assoc." }
 270 { $examples
 271     { $example
 272         "USING: assocs kernel math prettyprint ;"
 273         "H{ { \"bananas\" 5 } { \"apples\" 42 } { \"pears\" 17 } }"
 274         "0 swap [ nip + ] assoc-each ."
 275         "64"
 276     }
 277 } ;
 278
 279 HELP: assoc-map
 280 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... newkey newvalue ) } } { "newassoc" "a new assoc" } }
 281 { $description "Applies the quotation to each entry in the input assoc and collects the results in a new assoc of the same type as the input." }
 282 { $examples
 283     { $unchecked-example
 284         ": discount ( prices n -- newprices )"
 285         "    [ - ] curry assoc-map ;"
 286         "H{ { \"bananas\" 5 } { \"apples\" 42 } { \"pears\" 17 } }"
 287         "2 discount ."
 288         "H{ { \"bananas\" 3 } { \"apples\" 40 } { \"pears\" 15 } }"
 289     }
 290 } ;
 291
 292 { assoc-map assoc-map-as } related-words
 293
 294 HELP: assoc-filter
 295 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } { "subassoc" "a new assoc" } }
 296 { $description "Outputs an assoc of the same type as " { $snippet "assoc" } " consisting of all entries for which the predicate quotation yields true." } ;
 297
 298 HELP: assoc-filter-as
 299 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } { "exemplar" assoc } { "subassoc" "a new assoc" } }
 300 { $description "Outputs an assoc of the same type as " { $snippet "exemplar" } " consisting of all entries for which the predicate quotation yields true." } ;
 301
 302 HELP: assoc-filter!
 303 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } }
 304 { $description "Removes all entries for which the predicate quotation yields true." }
 305 { $side-effects "assoc" } ;
 306
 307 { assoc-filter assoc-filter-as assoc-filter! } related-words
 308
 309 HELP: assoc-reject
 310 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } { "subassoc" "a new assoc" } }
 311 { $description "Outputs an assoc of the same type as " { $snippet "assoc" } " consisting of all entries for which the predicate quotation yields false." } ;
 312
 313 HELP: assoc-reject-as
 314 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } { "exemplar" assoc } { "subassoc" "a new assoc" } }
 315 { $description "Outputs an assoc of the same type as " { $snippet "exemplar" } " consisting of all entries for which the predicate quotation yields false." } ;
 316
 317 HELP: assoc-reject!
 318 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } }
 319 { $description "Removes all entries for which the predicate quotation yields false." }
 320 { $side-effects "assoc" } ;
 321
 322 { assoc-reject assoc-reject-as assoc-reject! } related-words
 323
 324 HELP: assoc-partition
 325 { $values
 326     { "assoc" assoc } { "quot" quotation }
 327     { "true-assoc" assoc } { "false-assoc" assoc }
 328 }
 329 { $description "Calls a predicate quotation on each key of the input assoc. If the test yields true, the key/value pair is added to " { $snippet "true-assoc" } "; if false, it's added to " { $snippet "false-assoc" } "." } ;
 330
 331 HELP: assoc-any?
 332 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } { "?" boolean } }
 333 { $description "Tests if the assoc contains an entry satisfying a predicate by applying the quotation to each entry in turn. Iteration stops if an entry is found for which the quotation outputs a true value." } ;
 334
 335 HELP: assoc-all?
 336 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... ? ) } } { "?" boolean } }
 337 { $description "Tests if all entries in the assoc satisfy a predicate by applying the quotation to each entry in turn. a predicate quotation to entry in the assoc. Iteration stops if an entry is found for which the quotation outputs " { $link f } ". If the assoc is empty, always outputs " { $link t } "." } ;
 338
 339 HELP: assoc-refine
 340 { $values { "seq" sequence } { "assoc" assoc } }
 341 { $description "Outputs the intersection of all the assocs of the assocs sequence " { $snippet "seq" } ", or " { $link f } " if " { $snippet "seq" } " is empty." } ;
 342
 343 HELP: assoc-subset?
 344 { $values { "assoc1" assoc } { "assoc2" assoc } { "?" boolean } }
 345 { $description "Tests if " { $snippet "assoc2" } " contains all key/value pairs of " { $snippet "assoc1" } "." } ;
 346
 347 HELP: sift-keys
 348 { $values { "assoc" assoc } { "assoc'" "a new assoc" } }
 349 { $description "Outputs an assoc removing keys that are " { $link f } "." }
 350 { $examples
 351     { $example "USING: prettyprint assocs hashtables ;"
 352         "H{ { 1 2 } { f 3 } } sift-keys ."
 353         "H{ { 1 2 } }" }
 354 } ;
 355
 356 HELP: sift-values
 357 { $values { "assoc" assoc } { "assoc'" "a new assoc" } }
 358 { $description "Outputs an assoc removing values that are " { $link f } "." }
 359 { $examples
 360     { $example "USING: prettyprint assocs hashtables ;"
 361         "H{ { 1 f } { 3 4 } } sift-values ."
 362         "H{ { 3 4 } }" }
 363 } ;
 364
 365 { sift-keys sift-values harvest-keys harvest-values } related-words
 366
 367 HELP: harvest-keys
 368 { $values { "assoc" assoc } { "assoc'" "a new assoc" } }
 369 { $description "Outputs an assoc removing keys that are empty sequences." }
 370 { $examples
 371     { $example "USING: prettyprint assocs hashtables ;"
 372         "H{ { { 2 } 1 } { { } 3 } } harvest-keys ."
 373         "H{ { { 2 } 1 } }" }
 374 } ;
 375
 376 HELP: harvest-values
 377 { $values { "assoc" assoc } { "assoc'" "a new assoc" } }
 378 { $description "Outputs an assoc removing values that are empty sequences." }
 379 { $examples
 380     { $example "USING: prettyprint assocs hashtables ;"
 381         "H{ { 1 { } } { 3 { 4 } } } harvest-values ."
 382         "H{ { 3 { 4 } } }" }
 383 } ;
 384
 385
 386 HELP: assoc=
 387 { $values { "assoc1" assoc } { "assoc2" assoc } { "?" boolean } }
 388 { $description "Tests if two assocs contain the same entries. Unlike " { $link = } ", the two assocs may be of different types." }
 389 { $notes "Assoc implementations should define a method for the " { $link equal? } " generic word which calls this word after checking that both inputs have the same type." } ;
 390
 391 HELP: assoc-hashcode
 392 { $values { "n" "a non-negative integer" } { "assoc" assoc } { "code" integer } }
 393 { $description "Computes a hashcode for an assoc, such that equal assocs will have the same hashcode." }
 394 { $notes "Custom assoc implementations should use this word to implement a method for the " { $link hashcode* } " generic word." } ;
 395
 396 HELP: assoc-stack
 397 { $values { "key" "a key" } { "seq" "a sequence of assocs" } { "value" { $maybe "a value" } } }
 398 { $description "Searches for the key in successive elements of the sequence, starting from the end. If an assoc containing the key is found, the associated value is output. If no assoc contains the key, outputs " { $link f } "." }
 399 { $notes "This word is used to implement abstractions such as nested scopes; if the sequence is a stack represented by a vector, then the most recently pushed assoc -- the innermost scope -- will be searched first." } ;
 400
 401 HELP: value-at*
 402 { $values { "value" object } { "assoc" assoc } { "key/f" { $maybe "the key associated to the value" } } { "?" boolean } }
 403 { $description "Looks up the key associated with a value. The boolean flag can decide between the case of a missing key, and a key of " { $link f } "." } ;
 404
 405 HELP: value-at
 406 { $values { "value" object } { "assoc" assoc } { "key/f" { $maybe "the key associated to the value" } } }
 407 { $description "Looks up the key associated with a value. No distinction is made between a missing key and a key set to " { $link f } "." } ;
 408
 409 HELP: value?
 410 { $values { "value" object } { "assoc" assoc } { "?" boolean } }
 411 { $description "Tests if an assoc contains at least one key with the given value." } ;
 412
 413 HELP: delete-at*
 414 { $values { "key" "a key" } { "assoc" assoc } { "old" { $maybe "the previous value" } } { "?" boolean } }
 415 { $description "Removes an entry from the assoc and outputs the previous value together with a boolean indicating whether it was present." }
 416 { $side-effects "assoc" } ;
 417
 418 HELP: rename-at
 419 { $values { "newkey" object } { "key" object } { "assoc" assoc } }
 420 { $description "Removes the values associated to " { $snippet "key" } " and re-adds it as " { $snippet "newkey" } ". Does nothing if the assoc does not contain " { $snippet "key" } "." }
 421 ;
 422
 423 HELP: keys
 424 { $values { "assoc" assoc } { "keys" "an array of keys" } }
 425 { $description "Outputs an array of all keys in the assoc." } ;
 426
 427 HELP: values
 428 { $values { "assoc" assoc } { "values" "an array of values" } }
 429 { $description "Outputs an array of all values in the assoc." } ;
 430
 431 { keys values } related-words
 432
 433 HELP: assoc-intersect
 434 { $values { "assoc1" assoc } { "assoc2" assoc } { "intersection" "a new assoc" } }
 435 { $description "Outputs an assoc consisting of all entries from " { $snippet "assoc2" } " such that the key is also present in " { $snippet "assoc1" } "." }
 436 { $notes "The values of the keys in " { $snippet "assoc1" } " are disregarded, so this word is usually used for set-theoretic calculations where the assoc in question either has dummy sentinels as values, or the values equal the keys." } ;
 437
 438 HELP: assoc-union!
 439 { $values { "assoc1" assoc } { "assoc2" assoc } }
 440 { $description "Adds all entries from " { $snippet "assoc2" } " to " { $snippet "assoc1" } "." }
 441 { $side-effects "assoc1" } ;
 442
 443 HELP: assoc-union
 444 { $values { "assoc1" assoc } { "assoc2" assoc } { "union" "a new assoc" } }
 445 { $description "Outputs a assoc consisting of all entries from " { $snippet "assoc1" } " and " { $snippet "assoc2" } ", with entries from " { $snippet "assoc2" } " taking precedence in case the corresponding values are not equal." } ;
 446
 447 HELP: assoc-diff
 448 { $values { "assoc1" assoc } { "assoc2" assoc } { "diff" "a new assoc" } }
 449 { $description "Outputs an assoc consisting of all entries from " { $snippet "assoc1" } " whose key is not contained in " { $snippet "assoc2" } "." }
 450 ;
 451
 452 HELP: assoc-diff!
 453 { $values { "assoc1" assoc } { "assoc2" assoc } }
 454 { $description "Removes all entries from " { $snippet "assoc1" } " whose key is contained in " { $snippet "assoc2" } "." }
 455 { $side-effects "assoc1" } ;
 456
 457 HELP: substitute
 458 { $values { "seq" sequence } { "assoc" assoc } { "newseq" sequence } }
 459 { $description "Creates a new sequence where elements of " { $snippet "seq" } " which appear as keys in " { $snippet "assoc" } " are replaced by the corresponding values, and all other elements are unchanged." } ;
 460
 461 HELP: cache
 462 { $values { "key" "a key" } { "assoc" assoc } { "quot" { $quotation ( ... key -- ... value ) } } { "value" "a previously-retained or freshly-computed value" } }
 463 { $description "If the key is present in the assoc, outputs the associated value, otherwise calls the quotation to produce a value and stores the key/value pair into the assoc. Returns a value either looked up or newly stored in the assoc." }
 464 { $side-effects "assoc" } ;
 465
 466 HELP: 2cache
 467 { $values { "key1" "a key" } { "key2" "a key" } { "assoc" assoc } { "quot" { $quotation ( ... key1 key2 -- ... value ) } } { "value" "a previously-retained or freshly-computed value" } }
 468 { $description "If a single key composed of the input keys is present in the assoc, outputs the associated value, otherwise calls the quotation to produce a value and stores the keys/value pair into the assoc. Returns the value stored in the assoc. Returns a value either looked up or newly stored in the assoc." }
 469 { $side-effects "assoc" } ;
 470
 471 HELP: map>assoc
 472 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... key value ) } } { "exemplar" assoc } { "assoc" "a new assoc" } }
 473 { $description "Applies the quotation to each element of the sequence, and collects the keys and values into a new assoc having the same type as " { $snippet "exemplar" } "." } ;
 474
 475 HELP: map>alist
 476 { $values { "seq" sequence } { "quot" { $quotation ( ... elt -- ... key value ) } } { "alist" "a new alist" } }
 477 { $description "Applies the quotation to each element of the sequence, and collects the keys and values into a new alist." } ;
 478
 479 { map>assoc map>alist } related-words
 480
 481 HELP: assoc>map
 482 { $values { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... elt ) } } { "exemplar" sequence } { "seq" "a new sequence" } }
 483 { $description "Applies the quotation to each entry of the assoc and collects the results into a new sequence of the same type as the exemplar." } ;
 484
 485 HELP: change-at
 486 { $values { "key" object } { "assoc" assoc } { "quot" { $quotation ( ..a value -- ..b newvalue ) } } }
 487 { $description "Applies the quotation to the value associated with " { $snippet "key" } ", storing the new value back in the assoc." }
 488 { $side-effects "assoc" } ;
 489
 490 { change-at change-nth change } related-words
 491
 492 HELP: at+
 493 { $values { "n" number } { "key" object } { "assoc" assoc } }
 494 { $description "Adds " { $snippet "n" } " to the value associated with " { $snippet "key" } "; if there is no value, stores " { $snippet "n" } ", thus behaving as if the value was 0." }
 495 { $side-effects "assoc" } ;
 496
 497 HELP: inc-at
 498 { $values { "key" object } { "assoc" assoc } }
 499 { $description "Adds 1 to the value associated with " { $snippet "key" } "; if there is no value, stores 1." }
 500 { $side-effects "assoc" } ;
 501
 502 HELP: >alist
 503 { $values { "assoc" assoc } { "newassoc" "an array of key/value pairs" } }
 504 { $contract "Converts an associative structure into an association list." } ;
 505
 506 HELP: assoc-clone-like
 507 { $values
 508      { "assoc" assoc } { "exemplar" assoc }
 509      { "newassoc" assoc } }
 510 { $description "Outputs a newly-allocated assoc with the same elements as " { $snippet "assoc" } "." }
 511 { $examples { $example "USING: prettyprint assocs hashtables ;" "H{ { 1 2 } { 3 4 } } { } assoc-clone-like ." "{ { 1 2 } { 3 4 } }" } } ;
 512
 513 HELP: assoc-combine
 514 { $values
 515      { "seq" "a sequence of assocs" }
 516      { "union" assoc } }
 517 { $description "Takes the union of all of the " { $snippet "assocs" } " in " { $snippet "seq" } "." }
 518 { $examples { $example "USING: prettyprint assocs ;" "{ H{ { 1 2 } } H{ { 3 4 } } } assoc-combine ." "H{ { 1 2 } { 3 4 } }" } } ;
 519
 520 HELP: assoc-map-as
 521 { $values
 522      { "assoc" assoc } { "quot" { $quotation ( ... key value -- ... newkey newvalue ) } } { "exemplar" assoc }
 523      { "newassoc" assoc } }
 524 { $description "Applies the quotation to each entry in the input assoc and collects the results in a new assoc of the same type as the exemplar." }
 525 { $examples { $example "USING: prettyprint assocs hashtables math ;" " H{ { 1 2 } { 3 4 } } [ sq ] { } assoc-map-as ." "{ { 1 4 } { 3 16 } }" } } ;
 526
 527 HELP: extract-keys
 528 { $values
 529      { "seq" sequence } { "assoc" assoc }
 530      { "subassoc" assoc } }
 531 { $description "Outputs an new " { $snippet "assoc" } " with key/value pairs whose keys match the elements in the input " { $snippet "seq" } "." }
 532 { $examples
 533     { $example "USING: prettyprint assocs ;"
 534                "{ 1 3 } { { 1 10 } { 2 20 } { 3 30 } } extract-keys ."
 535                "{ { 1 10 } { 3 30 } }"
 536     }
 537 } ;
 538
 539 HELP: push-at
 540 { $values
 541      { "value" object } { "key" object } { "assoc" assoc } }
 542 { $description "Pushes the " { $snippet "value" } " onto a " { $snippet "vector" } " stored at the " { $snippet "key" } " in the " { $snippet "assoc" } ". If the " { $snippet "key" } " does not yet exist, creates a new " { $snippet "vector" } " at that " { $snippet "key" } " and pushes the " { $snippet "value" } "." }
 543 { $examples { $example "USING: prettyprint assocs kernel ;"
 544 "H{ { \"cats\" V{ \"Mittens\" } } } \"Mew\" \"cats\" pick push-at ."
 545 "H{ { \"cats\" V{ \"Mittens\" \"Mew\" } } }"
 546 } } ;
 547
 548 HELP: search-alist
 549 { $values
 550      { "key" object } { "alist" "an array of key/value pairs" }
 551      { "pair/f" "a key/value pair" } { "i/f" integer } }
 552 { $description "Iterates over " { $snippet "alist" } " and stops when the key is matched or the end of the " { $snippet "alist" } " has been reached. If there is no match, both outputs are " { $link f } "." }
 553 { $notes "This word is used to implement " { $link at* } " and " { $link set-at } " on sequences, and should not be called directly." }
 554 { $examples { $example "USING: prettyprint assocs.private kernel ;"
 555                         "3 { { 1 2 } { 3 4 } } search-alist [ . ] bi@"
 556                        "{ 3 4 }\n1"
 557             } { $example "USING: prettyprint assocs.private kernel ;"
 558                        "6 { { 1 2 } { 3 4 } } search-alist [ . ] bi@"
 559                        "f\nf"
 560             }
 561 } ;
 562
 563 HELP: unzip
 564 { $values
 565      { "assoc" assoc }
 566      { "keys" sequence } { "values" sequence } }
 567 { $description "Outputs an array of keys and an array of values of the input " { $snippet "assoc" } "." }
 568 { $examples
 569     { $example "USING: prettyprint assocs kernel ;"
 570                "{ { 1 4 } { 2 5 } { 3 6 } } unzip [ . ] bi@"
 571                "{ 1 2 3 }\n{ 4 5 6 }"
 572     }
 573 } ;
 574
 575 HELP: zip
 576 { $values
 577      { "keys" sequence } { "values" sequence }
 578      { "alist" "an array of key/value pairs" } }
 579 { $description "Combines two sequences pairwise into a single sequence of key/value pairs." }
 580 { $examples
 581     { $example "USING: prettyprint assocs ;"
 582                "{ 1 2 3 } { 4 5 6 } zip ."
 583                "{ { 1 4 } { 2 5 } { 3 6 } }"
 584     }
 585 } ;
 586
 587 HELP: zip-as
 588 { $values
 589      { "keys" sequence } { "values" sequence } { "exemplar" sequence }
 590      { "assoc" "a sequence of key/value pairs of type " { $snippet "exemplar" } } }
 591 { $description "Combines two sequences pairwise into a single sequence of key/value pairs of type " { $snippet "exemplar" } "." }
 592 { $notes "Exemplar must be a sequence type; hashtables will not work yet." }
 593 { $examples
 594     { $example "USING: prettyprint assocs ;"
 595                "{ 1 2 3 } { 4 5 6 } V{ } zip-as ."
 596                "V{ { 1 4 } { 2 5 } { 3 6 } }"
 597     }
 598 } ;
 599
 600 HELP: zip-index
 601 { $values
 602     { "values" sequence }
 603     { "alist" "an array of key/value pairs" }
 604 }
 605 { $examples
 606     "Zip a sequnce with its indices:"
 607     { $example "USING: assocs prettyprint ;"
 608         "{ 100 200 300 } zip-index ."
 609         "{ { 100 0 } { 200 1 } { 300 2 } }"
 610     }
 611 }
 612 { $description "Zip a sequence with its index and return an associative list where the input sequence is the keys and the indices are the values." } ;
 613
 614 HELP: zip-index-as
 615 { $values
 616     { "values" sequence } { "exemplar" sequence }
 617     { "assoc" assoc }
 618 }
 619 { $examples
 620     "Zip a sequnce with its indices as a vector:"
 621     { $example "USING: assocs prettyprint ;"
 622         "{ 100 200 300 } V{ } zip-index-as ."
 623         "V{ { 100 0 } { 200 1 } { 300 2 } }"
 624     }
 625 }
 626 { $description "Zip a sequence with its index and return an associative list of type " { $snippet "exemplar" } " where the input sequence is the keys and the indices are the values." } ;
 627
 628 { unzip zip zip-as zip-index zip-index-as } related-words