Scheme/LISP语言中CONS的具体作用是什么？附示例解析

Great question! Let's break down exactly what CONS does in Scheme/Lisp, using your guess function as a perfect real-world example.

What is CONS at its core? #

• CONS is one of the most fundamental primitive functions in Lisp/Scheme. Its job is to create a cons cell (often called a "pair")—a tiny data structure with two slots:
  • The car slot holds the first element of the pair.
  • The cdr slot holds the second part, which can be another cons cell (to keep building a list) or the empty list '() (to end the list).
• Put simply: CONS lets you build linked lists by attaching a single element to the front of an existing list (or empty list). It's the Lego brick of list construction in Lisp.

Breaking down your guess function #

First, let's restate your function clearly so we're aligned:

(DEFINE (guess list1 list2)
  (COND
    ((NULL? list1) '())
    ((member (CAR list1) list2) (CONS (CAR list1) (guess (CDR list1) list2)))
    (ELSE (guess (CDR list1) list2))
  )
)

This function calculates the intersection of list1 and list2—it returns a new list containing every element that appears in both input lists.

Now let's see exactly how CONS powers this:

1. Base case: When list1 is empty (NULL? list1), we return '() (the empty list)—our starting point for building the result.
2. Recursive check: For each element in list1:
   • We first check if the current element (CAR list1) exists in list2 using the member function.
   • If it does exist: We use CONS to take this matching element and prepend it to the result of recursively calling guess on the rest of list1 (CDR list1).
   • If it doesn't exist: We skip the element and just recurse on the rest of list1.

A concrete example to make it click #

Let's say we call (guess '(a b c d) '(b d e)):

• First call: a isn't in list2, so we call (guess '(b c d) '(b d e))
• Next call: b is in list2 → (CONS 'b (guess '(c d) '(b d e)))
• Next call: c isn't in list2, so we call (guess '(d) '(b d e))
• Next call: d is in list2 → (CONS 'd (guess '() '(b d e)))
• Base case hits: returns '(), so (CONS 'd '()) gives us (d)
• Back to the b step: (CONS 'b '(d)) gives us (b d)
• That's our final intersection result!

Why CONS is irreplaceable here #

• Scheme lists are immutable—you can't modify an existing list to add elements. Instead, CONS creates a new cons cell that links the current matching element to the rest of the result list we're building recursively.
• Every non-empty list in Scheme is just a chain of cons cells ending with '(). Without CONS, we couldn't construct these lists at all.

内容的提问来源于stack exchange，提问作者pumkinthatcodes