~wklew/int-map

Efficient, purely functional integer maps for R7RS scheme
45de1cfe — Walter Lewis 1 year, 4 months ago
Refactor exception throwing code
a581f9ce — Walter Lewis 1 year, 4 months ago
Add size function
cdd24661 — Walter Lewis 1 year, 4 months ago
readme: Don't use question mark in header, so anchor works

refs

main
browse  log 

clone

read-only
https://git.sr.ht/~wklew/int-map
read/write
git@git.sr.ht:~wklew/int-map

You can also use your local clone with git send-email.

Efficient, purely functional integer-keyed maps for R7RS scheme.

To use, import the library file:

(import (int-map))

#Overview

This library implements a purely functional finite map structure of integer-value pairs. It supports fast retrieval and modification, as well as efficient merging of multiple maps.

The implementation is based on radix trees (AKA patricia trees), as described in:

Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps", Workshop on ML, September 1998, pages 77-86

#Key size

Radix trees are fast because they use bit masking, which requires us to have low-level access to the integer keys. R7RS leaves the implementation of integers unspecified, so we use fixnums as defined by SRFI-143, or an equivalent library such as Guile's R6RS fixnums.

This means there is a limit on the size of keys: all keys should be less than int-map-key-size, an implementation-dependent value exported by this library. This condition is not checked at run time.

#Collisions

Maps must preserve the invariant that keys are unique. Inserting a value at an existing key is called a collision. By default, collisions are resolved by overwriting the old value. In cases where this is not desirable, a resolution function can optionally be passed as the last argument to any function which modifies a mapping.

#API reference

The complexity of each function is given in big-O notation. These were mostly taken from the Haskell IntMap documentation.

#Constructors

#Empty

(int-map-empty) -> int-map

O(1). Construct an empty int-map.

#Single

(int-map-single key val) -> int-map

O(1). Construct a singleton int-map from an initial key-value binding.

#From Alist

(alist->int-map alist [resolve]) -> int-map

O(n*min(n,W)). Construct an int-map from alist, a list of key-value pairs. By default, elements on the left are replaced by elements on the right at the same key. If resolve is given, instead combine the old and new values by calling (resolve old val), where old is the old value.

#Syntax

(int-map (key val) ...) -> int-map

O(n*min(n,W)). Like alist->int-map but as syntax, to potentially avoid creating an intermediate list.

#Basic Queries

#Is empty

(int-map-empty? int-map) -> bool

O(1). Test whether int-map is empty. Use this before passing an int-map to a function which expects at least one binding, such as int-map-min. Otherwise an unspecified error is signaled.

#Size

(int-map-size int-map) -> integer

O(n). Return the size of int-map. This currently requires traversing the entire map.

#Min and Max

(int-map-min int-map) -> (values key val)
(int-map-max int-map) -> (values key val)

O(min(n,W)). Return the binding of the minimum or maximum key in int-map. The key and associated value are returned as two values.

Raise an unspecified error if int-map is empty. Call int-map-empty? first to check for this condition.

#Mapping functions

#Lookup

(int-map-lookup key int-map [default]) -> val

O(min(n,W)). Return the value bound to key in int-map. If key is not bound in int-map, either return default if it is provided or raise an exception satisfying int-map-unbound-error?.

#Insert

(int-map-insert key val int-map [resolve]) -> int-map

O(min(n,W)). Bind key to val in int-map. By default, old values are replaced by new values at the same key. If resolve is given, instead combine the old and new values by calling (resolve old val), where old is the old value.

#Delete

(int-map-delete key int-map) -> int-map

O(min(n,W)). Delete the binding for key in int-map, if it exists.

#Adjust

(int-map-adjust proc key int-map) -> int-map

O(log n). Adjust the value bound to key in int-map by calling proc on it. Modifies the value bound to key only, if it exists, without changing the structure of int-map.

If key is not bound in int-map, raise a continuable exception satisfying int-map-unbound-error?. If this exception is continued using with-exception-handler, the resulting value is bound in place to the missing key. You can use this to insert a binding without traversing the tree a second time:

(define (increment-or-zero key int-map)
  (with-exception-handler
      (lambda (e)
        (cond ((int-map-unbound-error? e)
               0)))
    (lambda ()
      (int-map-adjust (lambda (x) (+ x 1)) key int-map))))

(int-map->asc-alist (increment-or-zero 3 (int-map (3 10))))

;; => ((3 . 11))

(int-map->asc-alist (increment-or-zero 2 (int-map (3 10))))

;; => ((2 . 0) (3 . 10))

#Merging Maps

#Merge

(int-map-merge . int-maps) -> int-map
(int-map-merge-with resolve . int-maps) -> int-map
(int-map-merge-list int-maps [resolve]) -> int-map

O(n+int-map). Combine int-maps into one containing the union of their bindings. By default, elements on the left are replaced by elements on the right at the same key. If resolve is provided, instead combine the old and new values by calling (resolve old val), where old is the old value.

Multiple versions are provided to support different calling conventions.

#Iterators

#Map

(int-map-map proc int-map) -> int-map

O(n). Apply proc to each value bound in int-map. The keys of int-map are not changed, only the bound values.

#For-each

(int-map-for-each-asc proc int-map) -> unspecified
(int-map-for-each-desc proc int-map) -> unspecified

O(n). Iterate over values in int-map, in ascending or descending order, applying proc to each of them for side effects.

#Fold

(int-map-fold-asc insert accum int-map) -> accum
(int-map-fold-desc insert accum int-map) -> accum

O(n). Fold over values in int-map, in ascending or descending order. With accum as the base value, replace calls to int-map-insert with insert.

For example, below is a possible definition of int-map-filter:

(define (int-map-filter pred int-map)
  (int-map-fold-asc (lambda (i v int-map)
                      (if (pred v)
                          (int-map-insert i v alist)
                          int-map))
                    (int-map-empty)
                    int-map))

#Conversions

#To Alist

(int-map->asc-alist int-map) -> alist
(int-map->desc-alist int-map) -> alist

O(n). Convert int-map to an alist, in ascending or descending order.