Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Cons element to list vs cons list to element in Scheme

What's the difference between using cons to combine an element to a list and using cons to combine a list to an element in scheme?

Furthermore, how exactly does cons work? Does it add element to the end of the list or the beginning?

Thanks!

like image 955
Maritha Wang Avatar asked Oct 06 '13 19:10

Maritha Wang


People also ask

What does cons mean in Scheme?

The other constructor, cons , is used when you already have a list and you want to add one new element. Cons takes two arguments, an element and a list (in that order), and returns a new list whose car is the first argument and whose cdr is the second. > (cons 'for '(no one)) (FOR NO ONE) > (cons 'julia '()) (JULIA)

What are the differences between cons list and append?

In terms of big O notation, cons usages are generally O(1) while append is O(n) where n is the length of the list you are dealing with. While (append (list first_elem) existing_list) technically has the same big O with (cons first_elem existing_list), the latter is more concise and faster.

What is car and CDR in Scheme?

car is an acronym from the phrase Contents of the Address part of the Register; and cdr is an acronym from the phrase Contents of the Decrement part of the Register.

What is a list in Scheme?

In contrast to Scheme's unstructured data types, such as symbols and numbers, lists are structures that contain other values as elements. A list is an ordered collection of values. In Scheme, lists can be heterogeneous, in that they may contain different kinds of values.


1 Answers

The primitive cons simply sticks together two things, the fact that some of those things are considered lists is incidental. For instance, this works and creates a pair (also known as a cons cell):

(cons 1 2)
=> '(1 . 2)     ; a pair

Now, if the second argument to cons happens to be a list, then the result will be a new list, and the first argument to cons will be added at the head of the old list. In other words: to create a list you need a list, even if it's empty:

(cons 1 '(2 3))
=> '(1 2 3)     ; a list

(cons 1 (cons 2 '()))
=> '(1 2)       ; a list

(cons 1 '())
=> '(1)         ; a list

But if the second argument to cons is not a list, then the result will be just a pair, or an improper list, meaning that it doesn't end in '() as it should to be considered a list:

(cons '(1 2) 3)
=> '((1 2) . 3) ; a pair, not a list

(cons 1 (cons 2 3))
=> '(1 2 . 3)   ; an improper list

Just to clarify, you can't use cons to add elements at the end of a list. The usual way to build a list is going from right-to-left, adding elements in reverse at the head position - say you want to build the list '(1 2 3), then you have to cons the elements in the order 3 2 1:

(cons 3 '())                   ; list is '(3)
(cons 2 (cons 3 '()))          ; list is '(2 3)
(cons 1 (cons 2 (cons 3 '()))) ; list is '(1 2 3)

For those rare occasions where you need to add one element at the end (and believe me, doing so generally means that you're thinking the algorithm wrong) you can use append, which receives two lists as arguments:

(append '(1 2 3) '(4))
=> '(1 2 3 4)
like image 82
Óscar López Avatar answered Sep 30 '22 08:09

Óscar López