Search code examples
listschemecons

Connection between pairs and list in scheme

I am trying to understand the connection between pairs and lists in scheme. Let's take a look at the following scheme expression:

(((a) (b)) ((c) (d)))

I wish to count the number of pairs in the above expression, so I constructed it in the following manner:

(list (list (list 'a) (list 'b)) (list (list 'c) (list 'd)))
 => (((a) (b)) ((c) (d)))

(list 'a),(list 'b),(list 'c),(list 'd) - 4 pairs
(list (list 'a) (list 'b)) and (list (list 'c) (list 'd)) - 2 pairs
(list (list (list 'a) (list 'b)) (list (list 'c) (list 'd))) - 1 pair

So far, 7 pairs. Supposed to be 10. What am I missing here?

Solution

  • Simple fact: a proper list with n elements has n pairs:

    enter image description here

    So, which is the total number of elements in your list?

    Lists like (a) have one element, so they have one pair. You have four of them, so you have 4 pairs.

    Lists like (thing1 thing2) have two elements, so they have two pairs. You have three of them (the two internals containing the lists like (a), and one external), so you have 3 x 2 = 6 other pairs.

    In total, you have 6 + 4 = 10 pairs.