在公共lisp中实现字典

Question

我正在尝试在Common Lisp中使用列表实现字典。程序应该获取一个单词列表，并创建一个单词直方图，其中包含每个唯一单词的频率。

程序如下:

(defparameter *histo* '())
(defun scanList (list)
  (loop for word in list
     do (if (assoc word histo)
            ((setf pair (assoc word histo))
             (remove pair histo)
             (setf f (+ 1 (second pair)))
             (setf pair ((car pair) f))
             (append histo pair))
            ((setf pair (word '1)) (append histo pair)))))

得到的错误是:(SETF PAIR (ASSOC WORD *HISTO*)) should be a lambda expression .

语法或语义错误究竟在哪里?

(defun scanList (list the fox jumped over the other fox))
(princ *histo*)

Answer 1

使用哈希表创建字典，然后转换为关联列表(list)按键或值排序。

(defun build-histo (l)
  (let ((dict (make-hash-table :test 'equal)))
    (loop for word in l
          do (incf (gethash word dict))
          finally (return dict))))
;; which was simplification (by @Renzo) of
;; (defun build-histo (l)
;;   (let ((dict (make-hash-table :test 'equal)))
;;     (loop for word in l
;;           for count = (1+ (gethash word dict 0))
;;           do (setf (gethash word dict) count)
;;           finally (return dict))))
(defparameter *histo* (build-histo '("a" "b" "c" "a" "a" "b" "b" "b")))
(defun hash-table-to-alist (ht)
  (maphash #'(lambda (k v) (cons k v)) ht))
;; which is the same like:
;; (defun hash-table-to-alist (ht)
;;   (loop for k being each hash-key of ht
;;         for v = (gethash k ht)
;;         collect (cons k v)))

;; sort the alist ascending by value
(sort (hash-table-to-alist *histo*) #'< :key #'cdr)
;; => (("c" . 1) ("a" . 3) ("b" . 4))
;; sort the alist descending by value
(sort (hash-table-to-alist *histo*) #'> :key #'cdr)
;; => (("b" . 4) ("a" . 3) ("c" . 1))
;; sort the alist ascending by key
(sort (hash-table-to-alist *histo*) #'string< :key #'car)
;; => (("a" . 3) ("b" . 4) ("c" . 1))
;; sort the alist descending by key
(sort (hash-table-to-alist *histo*) #'string> :eky #'car)
;; => (("c" . 1) ("b" . 4) ("a" . 3))

Answer 2

发布的代码有很多问题。报告的错误是由多余的括号引起的。在lisp中，不能在表达式中任意添加括号而不引起问题。在这种情况下，这些是有问题的表达式:

((setf pair (assoc word histo))
 (remove pair histo)
 (setf f (+ 1 (second pair)))
 (setf pair ((car pair) f)
 (append histo pair))
((setf pair (word '1)) (append histo pair))

在这两个表达式中，调用setf的结果被放在列表的函数位置，因此代码试图将该结果当作函数来调用，从而导致错误。

还有其他问题。看起来像OP代码正试图将表达式打包到if形式的怀抱中;这可能是上面提到的额外括号的来源。而if型在每只手臂上只能有一个表达。您可以在progn形式中包装多个表达式，或者使用cond代替(它允许在每个臂中包含多个表达式)。有一些拼写错误:*histo*在大多数代码中被错误地输入为histo;f和pair在任何地方都没有定义;(setf pair (word '1))不必要地引用1(这将工作，但在语义上是错误的)。

总的来说，这段代码看起来相当复杂。这可以变得更简单，仍然遵循相同的基本思想:

(defparameter *histo* '())
(defun build-histogram (words)
  (loop :for word :in words
        :if (assoc word *histo*)
          :do (incf (cdr (assoc word *histo*)))
        :else
          :do (push (cons word 1) *histo*)))

这段代码几乎不言自明。如果word已经被添加到*histo*，则增加其计数器。否则，添加一个新条目，计数器初始化为1。这段代码并不理想，因为它使用一个全局变量来存储频率计数。一个更好的解决方案是构造一个新的频率计数列表并返回:

(defun build-histogram (words)
  (let ((hist '()))
    (loop :for word :in words
          :if (assoc word hist)
            :do (incf (cdr (assoc word hist)))
          :else
            :do (push (cons word 1) hist))
    hist))

当然，你可以用其他各种方法来解决这个问题。