三个小伙伴

Cube_World_Banner
Standard

CONS, CAR, CDR,三个有爱的小伙伴。在Lisp/Scheme语言中,它们(某种程度上)构成了数据结构的基础。

 

STEP 1 Friends, Toys.

这三个小伙伴实际上对应着三种不同的操作,为解释这点,我们考虑如下图所示的“盒子”:

┏━┯━┓
┃X │ Y ┃
┗━┷━┛

这个“盒子”由左右两部分组成,这样的结构也被称为点对(pair)。以 P 代表上面的结构,其左半部分是元素X,右半部分是元素Y。

 

这样,三种操作就可以解释了:

car 的作用是取出一个点对的左半部分,当其作用在 P 上就会得到元素X。无独有偶,cdr念作could-er)的作用是取出一个点对的右半部分。而cons的作用便是将两个元素组装成pair。于是便有如下的关系:

(car P) = X

(cdr P) = Y

(cons X Y) = P

注:这是一种前序表示法,每个括号内的第一个元素会被当成运算符,后面紧接着的会被当成参数。

例如 (+ 3 2) 可以表示 3 + 2(func a b) 可以表示 func(a, b) 等。

 

到此为止,有关数据结构的基本语法已经讲完了。“怎么可能?就凭这种一年级水平的搭积木一样的东西?”不要着急,且听我娓娓道来。

Continue reading