Search code examples
schemelispguile

Scheme dict operations


I am looking to understanding some hashmap code in lisp, and am using python as a reference.

Are the following two roughly the same? And if so, how can I see what my dict object looks like?

# create dict
>>> my_dict = dict()                
> (define my_dict (make-hash-table))

# add keys
>>> my_dict['a'] = 1
>>> my_dict['b'] = 2
> (hash-set! my_dict 'a 1)
> (hash-set! my_dict 'b 2)

# get values
>>> my_dict.get('a')
> (hash-ref my_dict 'a)

# print the values?
print (my_dict)
> ??? How can I see what my hashmap contains in scheme?

Solution

  • Are the following two roughly the same?

    Sure, but I'd be wary of learning Scheme or any Lisp by referring back to Python.

    Note that R6RS Scheme has hash tables and hash table procedures as part of the Standard Libraries; this wasn't the case with R5RS Scheme. Consequently, earlier Scheme implementations usually had their own hash table implementations. Guile Scheme does support R6RS hash tables and procedures, but seems to maintain support for the older procedures, too. This is also the case for the Scheme that I am most familiar with, Chez Scheme. The Chez Scheme User's Guide says that the old-style procedures are included primarily for the sake of compatibility with older Chez Scheme implementations, but that support for them may be dropped in a future release. I don't know what Guile's stance is on this, but I would suggest using Standard Scheme procedures when possible for maximum portability and to guard against such future changes in your implementation.

    Guile is up to v3.0.2 at the time of this writing; OP version is v2.0.9, which is currently about 5 years old as far as I can tell. Guile 2.0.14 supports R6RS hashtables, so I suspect that Guile 2.0.9 does as well. In any case, I will answer using R6RS Standard Scheme; adjusting to the old Guile implementation should be trivial if necessary.

    The R6RS Standard Library does not have make-hash-table, but instead has make-hashtable, make-eq-hashtable, and make-eqv-hashtable. The make-hashtable procedure requires a procedure for testing equivalence of keys, while make-eq-hashtable tests for equivalence with eq?, and make-eqv-hashtable tests with eqv?.

    Instead of hash-set!, the Standard Library has hashtable-set!, which takes the same arguments as OP has for hash-set!.

    Instead of hash-ref, the Standard Library has hashtable-ref. This differs from OP hash-ref in that it requires a third argument to specify a default return value for when a key is not found.

    Following in OP footsteps, a hash table can be created and queried:

    Chez Scheme Version 9.5
    Copyright 1984-2017 Cisco Systems, Inc.
    
    > (define my-dict (make-eq-hashtable))
    > (hashtable-set! my-dict 'a 1)
    > (hashtable-set! my-dict 'b 2)
    > (hashtable-set! my-dict 'c 3)
    > (hashtable-set! my-dict 'd 5)
    > (hashtable-set! my-dict 'e 7)
    > (hashtable-set! my-dict 'f 11)
    > (hashtable-set! my-dict 'g 13)
    > (hashtable-ref my-dict 'e #f)
    7
    > (hashtable-ref my-dict 'h #f)
    #f
    > my-dict
    #<eq hashtable>
    

    How can I see what my hashmap contains in scheme?

    Possibly the simplest thing to do would be to create an association list from the hash table. There is no Standard procedure in R6RS that does this, but there was an old SRFI (SRFI-69) that included exactly such a procedure: hash-table->alist. It is possible that OP implementation of Guile includes such a procedure, but it is simple to implement one using R6RS Standard Scheme:

    (define (hashtable->alist ht)
      (let-values (((ks vs) (hashtable-entries ht)))
        (vector->list (vector-map cons ks vs))))
    

    Here, the hashtable-entries procedure takes a hash table and returns two values: a vector of keys, and a vector of corresponding values; let-values is used to bind the two return values so that they can be used. vector-map returns a vector formed from combining the elements of ks and vs with cons, and vector->list creates a list from this vector.

    > (hashtable->alist my-dict)
    ((f . 11) (e . 7) (c . 3) (b . 2) (a . 1) (g . 13) (d . 5))
    

    Guile: For the Sake of Completeness

    The above solution will work in Guile, but many R6RS procedures are not recognized in Guile by default. To make the above solution work in Guile, one first needs something like:

    (import (rnrs hashtables (6))         ; for R6RS hash tables
            (rnrs base (6)))              ; for R6RS let-values
    

    After reviewing the Guile 2.0.14 Reference Manual, another nonportable solution is apparent. There is no hash-table->alist procedure described in the manual, but the documentation describes how to create an association list from a hash table by using the hash-map->list procedure:

    (hash-map->list cons my-dict)
    

    This can only be expected to work on hash tables created with Guile's implementation-specific hash table constructors (e.g. make-hash-table), and may not work on hash tables created with the R6RS constructors (e.g. make-eq-hashtable). Note again that this solution should work in Guile (without any imports), but is not portable.