理解lisp中的cons

列表是Lisp的核心数据结构及语法。在Lisp里面,列表的存储方式比较特别,一个列表通常由1个或N个cons来组成的。那个list又与cons是什么关系呢?搞清楚之前,我混乱了许久,读过很多文档及实作才豁然开朗,概要记录一下,看似内容不多,但要理解的东西多了去,整理出来的文字比起之前做的笔记要少多了 :)

关于Cons

cons是一种简单的数据结构,一个cons是由头尾两个元素构成:如下创建一个cons对象:
> (setf x (cons 1 2) )
> x
(1 . 2 )
这创建了一个头是1,尾是2的cons对象。
对cons的操作有两个,car及cdr,分别是读取cons的头和尾元素:
> (car x)
1
> (cdr x)
2

cons的元素可以是任意类型的,当元素也是cons时:
> (setf y (cons 1 (cons 2 (cons 3 4))))
> y
(1 2 3 . 4)
y值可以这样理解:它由三个(点之前的元素个数)cons组成,最后一个元素是4
> (car y)
1
> (cdr y)
(2 3 . 4)

Cons与List

我们再来创建一个特别的cons:
> (setf z (cons 1 (cons 2 (cons 3 (cons 4 nil)))))
> z
(1 2 3 4)
z值可以这样理解:它由4个cons组成,最后一个元素是nil 
z也等价于:
> (list 1 2 3 4)

1、像y这样的列表,我们称之为点列表,其特征是cons的最后元素是一个原子,非nil,非空列表。
2、而像z这样的列表,我们称之为真列表(list) ,其特重是cons的最后元素是nil,即空列表。真列表打印输出时,会隐藏掉最后的nil值及点。
3、所以,list是一种特殊的cons,即真列表是一种特殊的点列表。
4、真列表(list)是可以使用append函数的,而点列表不行:
> (append z 5)
(1 2 3 4 5)
> (append y 5)
*** Eval error ***  Wrong type argument: listp, 4
错误指出,4(y中的最后一个元素) 不是一个list,所以不能append。
真列表(list) 最后的元素是nil,即空列表,所以是可以加进新元素。

说起来简单,实际上要真理解的确是得费点工夫和心思。

Cons与其他数据结构

cons除了可以表示list,还可以表示其他复杂的数据结构,如树,栈等,这就留待后面再做功课了。

This entry was posted in 技术 and tagged , , , . Bookmark the permalink.

发布评论

您的电子邮箱不会被公开。 标记为 * 的区域必须填写

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>