Containers library

One question for you /prog/!

Suppose you have a brand new language, which doesn't have any library yet. Which kind of basic containers / data structure would you expect?

>>32
If the language supports reader macros ( CL has them portably ) or some other way of extending syntax, you can just add 2 macro characters for { and }, and have it expand to that upon READ. Not only that, but it would be fairly trivial to implement(less than half a page of code). Even with such read-time features, if {} don't come built in, the users of the language may shy away from wasting precious macro characters (such as {}) and just use the long form (which doesn't look tedious to write at all to me - maybe some elisp script could even speed it up).

>>32
To show how easy it is to implement this, I just quickly hacked up an implementation to do what you proposed:
(defun open-brace-reader (stream char)
  (declare (ignore char))
  (labels ((read-pair ()            
             (let ((key #1=(read stream t nil t))
                   (value #1#))
               `(make-hash-pair ,key ,value))))
    `(make-hash
      ,@(loop
           do (loop while (char= (peek-char nil stream) #\ ) do (read-char stream))
           if (char= (peek-char nil stream) #\,) do (read-char stream)
           else if (char= (peek-char nil stream) #\}) do (progn (read-char stream) (return pairs))
           do (peek-char nil stream)
           collect (read-pair) into pairs))))

(defun close-brace-reader (stream char)
  (declare (ignore char stream))
  (error "unmatched close brace"))

;;; Test:
;(with-input-from-string (i "\"abc\" 12 ,\"dfg\" 23 }")
;  (open-brace-reader i #\{)) => (MAKE-HASH (MAKE-HASH-PAIR "abc" 12) (MAKE-HASH-PAIR "dfg" 23))

;;; There is no make-hash/make-hash-pair in CL, and I should have written the
;;; reader function to use the proper hashtable functions, however, in this case
;;; I'll just reimplement them through the standard hashtable functions:

(defun make-hash-pair (key value) (list key value))

(defun make-hash (&rest pairs)
  (let ((ht (make-hash-table :test #'equal)))
    (dolist (pair pairs ht)
      (destructuring-bind (key value) pair
          (setf (gethash key ht) value)))))

;;; This implementation isn't very efficient. One could change the call to make-hash
;;; to use multiple-value-call and make-hash-pair to use values for some performance improvements

;;; Test:
;CL-USER> (MAKE-HASH (MAKE-HASH-PAIR "abc" 12) (MAKE-HASH-PAIR "dfg" 23))
;#<HASH-TABLE :TEST EQUAL :COUNT 2 {24A2B2A9}>
;CL-USER> (maphash #'(lambda (key value) (format t "key: ~s, value: ~s~&" key value)) *)
;key: "abc", value: 12
;key: "dfg", value: 23


;;; Now let's install the new syntax (in a real-world scenario, you'd want to use one of those
;;; wonderful readtable managers, as you might want to define per-file syntaxes),
;;; but this is enough for simple toys like this:

(set-macro-character #\{ #'open-brace-reader)
(set-macro-character #\} #'close-brace-reader)

;;; Test:
;CL-USER> (maphash #'(lambda (key value) (format t "key: ~S, value: ~S~&" key value)) {"abc" 12  , "dfg" 23, #\Space 'lolwut, :is-this-worth-it 'not-really! })
;key: "abc", value: 12
;key: "dfg", value: 23
;key: #\ , value: LOLWUT
;key: :IS-THIS-WORTH-IT, value: NOT-REALLY!