12

i heard that clojure does not have cons cells as of most lisp languages.

does that mean a clojure list does not end with an empty list?

could anyone explain what that exactly means?

4

4 回答 4

26

Lisp 提供了一个原始的 cons 数据结构和它的符号。

参见John McCarthy，符号表达式的递归函数及其机器计算，第一部分，1960 年，第 3 章，符号表达式的递归函数。

该章介绍：

  • 由原子组成的符号表达式和使用点符号编写的符号表达式对：( a . b )
  • 缩写某些符号表达式的列表符号(a b c)
  • nil终止列表的原子符号
  • 原始函数car, cdr, cons,eq和atom
  • 其他几个功能：ff, subst, equal, null, cadr, caddr, null, append, among, pair, assoc, sublis, apply, eval, ...

在 Lisp 的早期，添加了改变 cons 单元的函数：（rplaca表示替换 car）和rplacd（表示替换 cdr）。请参阅John McCarthy 等人的 LISP 1.5 Programmer's Manual。从 1962 年开始。这些函数允许我们编写破坏性函数，还允许我们创建基于循环 cons 的数据结构，如循环列表。

通用 Lisp

通常，Lisp 方言实现了大部分。Common Lisp 也不例外，Common Lisp 标准中描述了此功能：Conses。使用上述功能的示例：

; pair two lists into a list of cons cells.
; the function pair is called pairlis in Common Lisp.
CL-USER 17 > (pairlis '(john mary eva) '(34 29 40))
((EVA . 40) (MARY . 29) (JOHN . 34))

; find a cons cell in a list of cons cells,
; based on the content of the car of those cons cells
CL-USER 18 > (assoc 'eva (pairlis '(john mary eva)
                                  '(34 29 40)))
(EVA . 40)

; create a tree out of cons cells and atoms
CL-USER 19 > (cons (cons 10 20) (cons 30 40))
((10 . 20) 30 . 40)

; a cons cell is not an atom
CL-USER 20 > (atom (cons 1 2))
NIL

; a cons cell is not nil
CL-USER 21 > (null (cons 1 2))
NIL

; substitute an item with a new one in a tree
CL-USER 22 > (subst 30                          ; new
                    'bar                        ; old
                    '((10 . 20) . (bar . 40)))  ; tree
((10 . 20) 30 . 40)   ; also written as  ((10 . 20) . (30 . 40))

; substitute several items in a tree, using an assoc list
; to describe the substitutions
CL-USER 23 > (sublis '((a . 10) (d . 40))      ; substitutions
                     '((a . b) . (c . d)))     ; tree
((10 . B) C . 40)

列表是符号表达式的一种特殊情况。它们通常不带点书写：

CL-USER 24 > '(a . (b . nil))
(A B)

Common Lisp 也支持变异操作rplaca和rplacdLisp 1.5：

CL-USER 25 > (let ((c (cons 0 1)))              ; create a cons
               (print c)                        ; print it
               (print (rplaca c 'foo))          ; replace the car
               (print (rplacd c 'bar))          ; replace the cdr
               (print (eq c (rplaca c 'baz)))   ; identical ?
               (values))
(0 . 1)      ; the cons cell
(FOO . 1)    ; car replaced
(FOO . BAR)  ; cdr replaced
T            ; still the same object

Emacs Lisp

Emacs Lisp 也实现了上述功能：

ELISP> (sublis '((a . 10) (d . 40))                                             
               '((a . b) . (c . d)))
((10 . b) c . 40)

Clojure

Clojure不支持John McCarthy 所描述的这些符号表达式。它没有 cons 单元格，没有点表示法，并且不提供上述接口。例如atom 在 Clojure 中意味着完全不同的东西。cons不会创建一个缺点单元格。列表不是由 cons 单元格组成的。

在 Clojure 中，点只是另一个符号：

user=> (count '(1 . 2))
3

有一个构造列表的原始函数：

user=> (list 1 2 3)
(1 2 3)

结果应该是一个列表：

user=> (list? (list 1 2 3))
true

有一个函数叫做cons：

user=> (cons 0 (list 1 2 3))
(0 1 2 3)

不知何故，这不是一个列表：

user=> (list? (cons 0 (list 1 2 3)))
false

基本上，Clojure 确实使用不同的数据结构（->序列，逻辑列表），它们有自己的命名和语义。即使名称与 Lisp 名称相似，也不要期望它们的作用相同。

方案

编程语言Scheme还提供了与上述类似的 cons 单元。它缺少一些功能，但它们可以很容易地实现。例如sublis可以在 Scheme 中这样实现（参见initdr.scm）：

(define (sublis alist tree)
  (if (pair? tree)
      (cons (sublis alist (car tree))
            (sublis alist (cdr tree)))
      (if (assv tree alist)
          (cdr (assv tree alist))
          tree)))
于 2015-12-18T07:31:11.157 回答
7

根据clojure.org 的这个页面：

cons，first和rest操作序列抽象，而不是具体的 cons 单元

Clojure 列表不会以空列表结尾，它们也不是传统的 cons 单元格。它们是实现排序的数据结构。 这个关于编程到抽象的页面解释了 Clojure 对“seqable”结构的方法，包括列表：

通常，抽象编程通过让您在不同数据结构上使用函数库而赋予您强大的功能，而不管这些数据结构是如何实现的。

所以 Clojure 列表就像 cons 单元，因为它们实现了cons, first， rest但这仅意味着它们共享一个公共接口。它们的底层实现不同，但它们都是“可序列化的”。

于 2015-12-18T04:07:27.890 回答
7
  • Clojure 确实有一个缺点结构：clojure.lang.Cons.
  • 它用于cons调用结果
  • ...没有别的：既不是列表，也不是向量，也不是任何类型的惰性序列。
  • 它也不能用于一般的对象对：tail/ rest/cdr 是一个序列，而不是一个Object.
  • 如果您将cons某些内容放入列表、向量或惰性序列中，您会得到一个Cons.
  • 但是，正如其他答案所表明的那样，没有处理Conses 的函数。一般来说，它们都按顺序处理。

另一种用途：conjing 到一个不确定的序列（既不是向量列表也不是集合也不是映射...）产生一个Cons.

于 2015-12-18T12:54:48.757 回答
1

在 Common Lisp 中，列表是一系列 cons 单元格。每个 cons 单元有两个插槽或指针，称为“car”和“cdr”。汽车指向（或持有）某物——任何东西。cdr 通常指向另一个 cons 单元格或nil. nil算作列表的末尾。Clojure 为您提供了与其列表大致相同的功能，但底层表示不同。它确实有一个名为 的数据类型Cons，但并非所有列表或给定列表的所有部分都是从Conss 构建的。（如果您还没有阅读 jmargolisvt 的答案，那么现在您应该阅读它。） [编辑：其他答案表明我在这里所说的关于 Clojure 中列表和 Conses 之间关系的内容是不正确的。人们可能会觉得它在“列表”的非正式意义上是正确的——或者不是。]

另请注意，部分由于序列抽象的想法，列表本身在 Clojure 中比在 Common Lisp 或 Scheme 中少得多。但是，其他类型的序列非常常见。

还值得知道的是，在 Clojure 中，您不能假定打印出来时看起来像列表的东西实际上是列表。例如，它可能是一个惰性序列，它不被视为列表。

以下是一些使用列表的潜在信息 Clojure 示例：

user=> (def foo (list 1))
#'user/foo
user=> foo
(1)
user=> (class foo)
clojure.lang.PersistentList
user=> (def bar (cons 2 foo))
#'user/bar
user=> bar
(2 1)
user=> (class bar)
clojure.lang.Cons

（两者foo和bar都被视为列表，即使class返回不同的数据类型。）

user=> (next bar)
(1)
user=> (rest bar)
(1)
user=> (class (next bar))
clojure.lang.PersistentList
user=> (class (rest bar))
clojure.lang.PersistentList
user=> (next foo)
nil
user=> (rest foo)
()
user=> (= nil ())
false
user=> (rest ())
()
user=> (rest nil)
()
user=> (next ())
nil
user=> (next nil)
nil

在 Common Lisp 中，您可以将一个对象 cons 到另一个对象上，而不是列表或nil. 结果是一个“点列表” (1 . 2)，它是一个单一的 cons 单元格，其中 cdr 指针指向另一个 cons 单元格或 以外的东西nil，就像在普通列表中一样。让我们在 Clojure 中尝试一下：

user=> (cons 1 2)
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long  clojure.lang.RT.seqFrom (RT.java:528)

当我在这里时，与 Common Lisp 的另一个显着区别（其中nil= ()= false）：

user=> (= nil false)
false
user=> (= () false)
false

但是，即使nil不是false，您也可以像这样使用它false：

user=> (if nil "nil works like true" "nil works like false")
"nil works like false"

但是，您不能使用空列表执行此操作：

user=> (if () "() works like true" "() works like false")
"() works like true"

（尽管有这些例子，总的来说，Clojure 比 IMO 的 Common Lisp 更简单、更优雅。即使像我一样喜欢 Common Lisp 的人也必须承认，Common Lisp 既不简单也不优雅。它有自己的一种美。）

于 2015-12-18T05:37:52.480 回答