Scheme comes built-in with two main collections: lists and vectors. Lists are a good lead in to recursion as all processing on lists must be done with recursion. When we define a list as an item and a reference to the next item we see that a list is a recursive structure. Note the comparison to linked lists in C# (add a link here).
The most basic list is represented by empty. In Scheme/Racket we write this as (list).
This Screenshot shows the result when we run (list):
When we run list we get the output '() which is the empty list.
The Cons function is the function that reveals to us how lists are created. It is a bit cumbersome to use cons so later we will look a shortcut to create lists.
Creating a one element list:
(cons 3 empty)
The cons function takes an element and adds it to the beginning of a list. In this case the element 3 is added to the front of the empty list making a one element list.
A visual representation of this list is:
Creating a 2 element list:
(cons 5 (cons 3 empty))
Since the innermost expression gets evaluated first, we have a list '(3) created and we are adding 5 to the front of that list. The list we now have is '(5 3). Visually we can represent this list as follows:
An six element list would be written like this:
(define lst1 (cons 5 (cons 3 (cons 2 (cons 4 (cons 6 (cons 7 empty)))))))
It gets tiring typing out all those nested cons calls so we have a shortcut which is the list function.
(list 5 3 2 4 6)
The elements are added in order from left to right to the front of the list. So the list created is 5 -> 3 -> 2 -> 4 -> 6.
First Item in List
To get the first element in a list we simply use the first function.
(first (list 5 3 2 4 6))
This produces the value 5.
Second Item in List
(second (list 5 3 2 4 6))
This produces the value 3.
Similar functions exist for elements in third position to the tenth position. The most useful of these functions are first and second. These will be very useful when we look at recursive function on lists.
Post if you have any questions.