lisp如何实现字典数据结构

Question

古老lisp的语言一直被称为现代各种语言的始祖
看名字就知道是表处理语言, 处理动态的表当然是看家本领

当然现代的流行语言包括python, ruby, js 甚至 perl 和 php 都实现了两个基本上无敌的数据结构, list和dict
而据我所以lisp的最近流行方言clojure内置了丰富的数据结构, 对clojure当然不是问题

而古老的lisp语言, 一般是怎么处理dict这种数据结构的需求的呢?
或者从另外一个角度提问, 如何使用list这种简单的数据结构快速的构建出丰富的数据类型, 比如set, dict或者graph等等?

Answer 1

一般用 association list 或 property list 来模拟 dict 或 hash table。

association list:

 ((key1 . value1)
  (key2 . value2)
  (key3 . value3))

property list:

 (key1 value1
  key2 value2
  key3 value3)

对于 set 的话，要在插入函数上做文章，插入前遍历表来查看该对象是非已在表中。

图可以转化成树，树可以表达为 (root child1 child2 ...)，child1、child2 等再按照前面的形式递归定义下去。

建议楼主看 Structure and Interpretation of Compu...，里面有写到用表实现 tree, set, queue 等数据结构。

Answer 2

Common Lisp 中有內建的散列表，不知是不是你想要的？

(make-hash-table)
(defvar tbl *)
(gethash :key tbl) ;=>  NIL; NIL
(setf (gethash :key tbl) :value)
(gethash :key tbl) ;=> :VALUE; T
(maphash (lambda (k v) (format t "Key ~S Value ~S~%" k v)) tbl)

其實LOOP也內建支持散列表。

屬性列表和關聯列表都很不建議使用，他們在搜索上效率比散列表差得遠。

Answer 3

通過嵌套的列表來表示。

這是列表，或者叫做數組，或者叫做序列，或者愛叫什麼叫什麼。

[1 2 3 4 5 6 7 8 9]

一個「字典」就是一組鍵值對，以如下形式表示一個所謂的「字典」

[[@a 1] [@b 2] [@c 3]]

同時定義算子 (assoc) 如

(def assoc (lambda [x L] (cond
    [(eq (car (car L)) x) (car (cdr (car L)))]
    [#true (assoc x (cdr L))]
)))

然後你就可以 (assoc @a [[@a 1] [@b 2] [@c 3]]) == 1。這裡的 (assoc) 就是根據鍵來取值的方法，在其他的語言中，可能叫做 get 方法，或者使用 dict[key] 這種語法形式。本質上一樣的。

一種結構叫什麼，不重要。其如何表示，也不重要。重要的操作數據結構的方法，如果兩個數據結構的操作方法是一致的，那麼這兩個數據結構本質上就是相同的。LISP中，所有的數據結構都通過 「包含列表或原子的列表」 這一種形式來表示。而操作列表只需要三個正交的方法，即 car cdr cons，通過此，就可以定義出操作一切的、任意形式的列表組合的方法。這就是LISP的精髓之一。