Changes between Version 12 and Version 13 of ImmutableDataStructuresWortman


Ignore:
Timestamp:
06/18/13 23:34:39 (4 years ago)
Author:
cowan
Comment:

Moved draft 2 of imap-update into place

Legend:

Unmodified
Added
Removed
Modified
  • ImmutableDataStructuresWortman

    v12 v13  
    328328 
    329329{{{#!scheme 
    330 (imap-update set key present-proc absent-proc) 
    331 }}} 
    332  
    333 A continuation-based universal update procedure. Attempts to find a key {{{key-match}}} equal to {{{key}}} in {{{set}}}. When such a {{{key-match}}} is found, calls 
    334 {{{#!scheme 
    335 (present-proc key-match value update remove) 
    336 }}} 
    337 which must either tail-call 
    338 {{{#!scheme 
    339 (update new-key new-value ret) 
    340 }}} 
    341 to replace {{{key}}} with {{{new-key}}} and the corresponding value with {{{new-value}}}, or tail-call 
    342 {{{#!scheme 
    343 (remove ret) 
    344 }}} 
    345 to remove the assocition from {{{map}}}. In either case {{{ret}}} will be one of the values returned from the enclosing {{{imap-update}}} call. 
    346  
    347 When no such {{{key-match}}} is found, {{{imap-update}}} calls 
    348 {{{#!scheme 
    349 (absent-proc insert ignore) 
    350 }}} 
    351 which should either tail-call 
    352 {{{#!scheme 
    353 (insert new-key value ret) 
    354 }}} 
    355 to insert {{{new-key}}} and {{{value}}} into {{{map}}}, or else tail-call 
    356 {{{#!scheme 
    357 (ignore ret) 
    358 }}} 
    359 to leave {{{map}}} unchanged. Again, {{{ret}}} will be returned from the enclosing {{{imap-update}}} call. 
    360  
    361 In any case, {{{imap-update}}} returns 
    362 {{{#!scheme 
    363 (values new-map ret) 
    364 }}} 
    365 where {{{new-map}}} is a new map reflecting the indicated modification, if any; and {{{ret}}} is the return value produced by one of the continuations. O(log n) time. 
    366  
     330(imap-update map key absent-proc present-proc) 
     331}}} 
     332 
     333A continuation-based universal update procedure. Attempts to find a key {{{key-match}}} equal to {{{key}}} in {{{map}}}, and its associated {{{value}}}. When such no such {{{key-match}}} is found, returns the result of calling 
     334{{{#!scheme 
     335(absent-proc insert) 
     336}}} 
     337. {{{insert}}} is a procedure such that 
     338{{{#!scheme 
     339(insert new-value) 
     340}}} 
     341returns a version of {{{map}}} in which {{{key}}} is associated with {{{new-value}}}. 
     342 
     343When {{{key-match}}} exists, returns the result of calling 
     344{{{#!scheme 
     345(present-proc key-match value replace remove) 
     346}}} 
     347. {{{replace}}} is a procedure such that 
     348{{{#!scheme 
     349(replace new-value) 
     350}}} 
     351returns a new version of {{{map}}} in which the {{{key}}} maps to {{{new-value}}} instead of {{{value}}}. 
     352 
     353{{{remove}}} is a thunk such that 
     354{{{#!scheme 
     355(remove) 
     356}}} 
     357returns a new version of {{{map}}} with no association for {{{key}}}.  
     358 
     359The {{{imap-update}}}, {{{insert}}}, {{{replace}}}, and {{{remove}}} procedures may take O(log n) time each. Thus if {{{absent-proc}}} and {{{present-proc}}} take constant (or even O(log n)) time and call their passed-in continuations at most once (or even any constant number of times), the entire update process takes O(log n) time. 
    367360{{{#!scheme 
    368361(imap-find map key [absent-thunk]) 
     
    509502 
    510503I don't think the imap/IMAP naming conflict is important at all. 
    511  
    512 === Update procedure draft 2 === 
    513  
    514 {{{#!scheme 
    515 (imap-update map key absent-proc present-proc) 
    516 }}} 
    517  
    518 A continuation-based universal update procedure. Attempts to find a key {{{key-match}}} equal to {{{key}}} in {{{map}}}, and its associated {{{value}}}. When such no such {{{key-match}}} is found, returns the result of calling 
    519 {{{#!scheme 
    520 (absent-proc insert) 
    521 }}} 
    522 . {{{insert}}} is a procedure such that 
    523 {{{#!scheme 
    524 (insert new-value) 
    525 }}} 
    526 returns a version of {{{map}}} in which {{{key}}} is associated with {{{new-value}}}. 
    527  
    528 When {{{key-match}}} exists, returns the result of calling 
    529 {{{#!scheme 
    530 (present-proc key-match value replace remove) 
    531 }}} 
    532 . {{{replace}}} is a procedure such that 
    533 {{{#!scheme 
    534 (replace new-value) 
    535 }}} 
    536 returns a new version of {{{map}}} in which the {{{key}}} maps to {{{new-value}}} instead of {{{value}}}. 
    537  
    538 {{{remove}}} is a thunk such that 
    539 {{{#!scheme 
    540 (remove) 
    541 }}} 
    542 returns a new version of {{{map}}} with no association for {{{key}}}.  
    543  
    544 The {{{imap-update}}}, {{{insert}}}, {{{replace}}}, and {{{remove}}} procedures may take O(log n) time each. Thus if {{{absent-proc}}} and {{{present-proc}}} take constant (or even O(log n)) time and call their passed-in continuations at most once (or even any constant number of times), the entire update process takes O(log n) time.