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