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 等数据结构。