Implementing multidimensional associative arrays in Common Lisp

Question

I'm looking for the best way to implement multidimensional associative arrays in Common Lisp. I'm using SBCL.

For example in MATLAB, I can create a struct array like this, eg. with some geographical data:

my_array.Finland.capital = 'Helsinki';
my_array.Finland.northernmost_municipality = 'Utsjoki';
my_array.Norway.capital = 'Oslo';

And then refer to it using dynamic field names:

country = 'Finland';
city_status = 'capital';

my_array.(country).(city_status)

would give the string 'Helsinki' as a result.

So, what would be the best way to implement multidimensional (n-dimensional) associative arrays in Common Lisp? (as in the above example in MATLAB)

I found a working solution based on converting the values/keys (given as strings) to numeric addresses using a hash table, and then passing those numeric address to aref as indices to a multidimensional array. But I wonder is there some better way to do it? I need to convert strings to other strings, strings to lists and strings to numbers (as in the example below).

My solution is this (with an example data to convert numbers written in English to their numeric representation):

Function list-to-3d-array below is a minimally modified version of Rainer Joswig's answer to Common Lisp: convert between lists and arrays .

;;; functions.
(defun list-to-3d-array (my-list)
  (make-array (list (length my-list)
                    (length (first my-list))
                    (length (first (first my-list))))
              :initial-contents my-list))

(defun prepare-hash-table (my-hash-table factor-name factor-values-list)
  "This function stores values from 0 to n for the keys created by concatenating the factor-name and the values given in a list."
  (loop for i from 0 to (1- (length factor-values-list))
        do (setf (gethash (concatenate 'string factor-name "-" (nth i factor-values-list)) my-hash-table) i)))

(defun return-value-from-assoc-array (my-array my-hash-table hundreds tens ones)
  (aref my-array
        (gethash (concatenate 'string "hundreds-" hundreds) my-hash-table)
        (gethash (concatenate 'string "tens-" tens) my-hash-table)
        (gethash (concatenate 'string "ones-" ones) my-hash-table)))
;;; functions end here.

;;; some example data.
(defparameter *array-contents*
  (list 
    (list
      (list 111 112 113)
      (list 121 122 123)
      (list 131 132 133))
    (list
      (list 211 212 213)
      (list 221 222 223)
      (list 231 232 233))
    (list
      (list 311 312 313)
      (list 321 322 323)
      (list 331 332 333))))

(defparameter *hundreds-in-english* (list "hundred" "twohundred" "threehundred"))
(defparameter *tens-in-english* (list "ten" "twenty" "thirty"))
(defparameter *ones-in-english* (list "one" "two" "three"))

(defparameter *my-hash-table* (make-hash-table :test 'equal))
;;; example parameters end here.

;;; prepare the array.
(defparameter *my-array* (list-to-3d-array *array-contents*))

;;;; prepare the hash table.
(prepare-hash-table *my-hash-table* "hundreds" *hundreds-in-english*)
(prepare-hash-table *my-hash-table* "tens" *tens-in-english*)
(prepare-hash-table *my-hash-table* "ones" *ones-in-english*)

Then eg. (return-value-from-assoc-array *my-array* *my-hash-table* "hundred" "ten" "two") outputs:

112

Answer 1

I disagree with the design and implementation of get-nested-hash given above. (get-nested-hash 1) should not return 1, and (get-nested-hash 1 2) should not return nil. Not passing two arguments should be an error. Multiple values should be returned in order to distinguish intentional nils, like gethash. The loop is messy and cumbersome. A correctable error should not be issued via check-type because data loss could result.

Here is an improved solution:

(defun rec-hash (rec-hash key &rest more-keys)
  (if more-keys
      (apply #'rec-hash (gethash key rec-hash) more-keys)
      (gethash key rec-hash)))

(defun auto-vivify (rec-hash key)
  (multiple-value-bind (child exist) (gethash key rec-hash)
    (if exist
        child
        (setf (gethash key rec-hash)
              (make-hash-table :test (hash-table-test rec-hash))))))

(defun (setf rec-hash) (value rec-hash key &rest more-keys)
  (if more-keys
      (apply #'(setf rec-hash) value (auto-vivify rec-hash key) more-keys)
      (setf (gethash key rec-hash) value)))

Answer 2

You can also use a Prolog implementation in Lisp. Prolog provides relations and the possibility to assert facts and one can use logic rules.

Here a simple relation in LispWorks:

==> (defrel capital ((capital finland helsinki)))
YES.
OK.

==> (capital finland ?city)

?CITY = HELSINKI
OK.

==> (and (= ?country finland) (capital ?country ?city))

?COUNTRY = FINLAND
?CITY = HELSINKI
OK.

Typically such a Prolog in Lisp then also provides access between Lisp and the embedded Prolog.