1

While attempting to generate a list of subsets that exist within two sets, I am running into an issue with cons. A procedure takes in a list named result and attempts to construct a new list out of result and the car of another set. So far, the set is generated with the correct elements, but they are contained within a size N nested list, where N is the number of nestings and the number of elements within the subset for which I am searching.

How can I apply cons with result without creating a nested list?

Example: 

;These are two sets that I will be checking
(define s1 '(1 2 3 4))
(define s2 '(1 2 3))
;Result from running these lists through my procedure
(((() . 1) . 2) . 3)
;What I want to have generated
(1 2 3)

I need to be able to call (car list) and receive 1 not ((() . 1) . 2)

XBigTK13X
  • 2,655
  • 8
  • 30
  • 39

1 Answers1

4

First of all (((() . 1) . 2) . 3) is not a nested list - it's not a list at all. (((() 1) 2) 3) would be a nested list. (((() . 1) . 2) . 3) is a dotted pair whose first element is also a dotted pair.

So now to explain the behaviour you see: In the lisp family of languages (cons a b) creates a pair containing a as it's car and b as its cdr.

Now a list is either the empty list (()) or a pair whose cdr is also a list (the car might contain anything - if both the cdr and the car are a list, the list is called a nested list).

A pair that is not a list is called a dotted pair. This what you're creating here because you're calling cons with a second argument which is not a list.

Conclusion:

You can not use cons to append to the end of the list. If you need to append to the end of a list, you can use concat with a single-element list as the second argument.

Note however that appending to the end of a list, is an O(n) operation while appending at the front (using cons) is an O(1) operation, so if possible you should change your algorithm, so it only needs to append at the front.

Community
  • 1
  • 1
sepp2k
  • 363,768
  • 54
  • 674
  • 675
  • I was incorrectly passing a dotted pair as the first argument of **cons**. When I changed the order as follows, everything works. ;Broken method (cons result (car s2)) ;Works correctly (cons (car s2) result) – XBigTK13X Nov 05 '10 at 19:42
  • 2 good rules: The second argument to cons should be a list, and every list is ended by `'()`, meaning a list with three sublists has 4 empty lists inside. – erjiang Nov 05 '10 at 20:09