古老lisp的语言一直被称为现代各种语言的始祖
看名字就知道是表处理语言, 处理动态的表当然是看家本领
当然现代的流行语言包括python, ruby, js 甚至 perl 和 php 都实现了两个基本上无敌的数据结构, list和dict
而据我所以lisp的最近流行方言clojure内置了丰富的数据结构, 对clojure当然不是问题
而古老的lisp语言, 一般是怎么处理dict这种数据结构的需求的呢?
或者从另外一个角度提问, 如何使用list这种简单的数据结构快速的构建出丰富的数据类型, 比如set, dict或者graph等等?
通過嵌套的列表來表示。
這是列表,或者叫做數組,或者叫做序列,或者愛叫什麼叫什麼。
[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的精髓之一。
一般用 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 等数据结构。
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
也內建支持散列表。
屬性列表和關聯列表都很不建議使用,他們在搜索上效率比散列表差得遠。