For now we will put aside all the little details and complications and will learn the essance of what it is and why it is so.
Suppose there is a very long list of integers. We want to know, whether a given integer is already in that list or not.
There is an interesting question - what is an integer? (Someone of those Java folks will shout - ''an instance of class Integer''). For us, however, for now, it will be a member of a set.
What is a set? Well, it is a collection of elements, defined by a set of possible operations (functions) that could be applied to a member of a set. Some sets have upper and lower bounds, some are not. We usually think about sets as a lists of unique elements. List is a natural, mind-friendly construct, hard-wired into our brain. [citation needed], I know.
Mathematicians have a special notation for a sets (and everything else), but ''this is not Math''. This is another discipline for modeling real-world phenomena. Sure, we are re-using concepts and ideas from Math, but not its notations.
The naive, straightforward solution would be to compare each element of a list with that integer:
{{{
(define (member x l)
(cond ((null? l) #f) ; if it is an empty list, then it has no memebers
((eq? x (car l)) #t) ; if the given number is equal to the first element the list
(else (member x (cdr l))))) ; otherwise skip the first element and check the remaining sub-list
; Now let's do some testing - whether or not this code works as expected.
(member 3 '(1 2 3 4 5))
;Value: #t
; Amazingly, we cab put not just integers into our list, but also symbols, and it works by magic.
(member 'a '(1 a 2 b 3 c))
;Value: #t
(member 'x '(1 a 2 b 3 c))
;Value: #f
(member '() '(1 a 2 b 3 c))
;Value: #f
}}}
List is a very generic and very natural concept, so we need to have very deep understanding of it.
{{{
'(1 2 3 4 5) ; there is a list
; We used to say that list has a head and a tail.
; What we call head is just its first element. One, distinct element.
(car '(1 2 3))
; Value: 1
(number? (car '(1 2 3)))
; Value: #t
; What we call tail is all the remaining elements, except the first one.
(cdr '(1 2 3))
;Value: (2 3)
; This means tail is a list, yet another list - a sub-list.
(list? (cdr '(1 2 3)))
;Value: #t
}}}
This notion is very important. Suppose we have a stack of 4 books on a table. A list is an abstract construction of the mind. A stack of books is a part of reality. Suppose we take one book from the top of this stack. What we have is a single book - a thing. What remain on a table is a stack of 4 books.
Let's not discuss for now whether one book on a table is a stack of one element (it is if you wish so - it is up to you how you model parts of reality) and what is an empty stack (it is a place on a table where stack used to be, or where you can put one).
What is much more important to realize is that there is always some book on the top of it (except in the case of an empty stack), so the top of a stack of books is a book, but a stack is not just this one book, it is all of them together.
'car of a list is an element. 'cdr of a list is a list. 'cdr of a list of just one element is the empty list.
{{{
(number? (car '(1)))
; Value: #t
(list? (cdr '(1)))
;Value: #t
}}}
What is wrong with our program? Well. It is all OK if we have just 3 or 5 numbers in a list.
If we have 5 numbers in a list to find out whether or not a given number is a member of it we need to perform several comparisons.
If it happens that the given number is the same as the first element of the list, then we are lucky, and we are done. Just one comparison were performed.
If it happen to be the n-th element of the list, then n comparisons will be performed. Nothing special.
What if the given element is not in the list? Well, we will compare it with each element of the list and then return #f. This means we will perform as much comparisons as many elements we have in the list.
Lets go back to books. Suppose we have a book'a title, and want to find out whether or not it is in this pile of books. So, we take the first book from a pile, read its title, if it's not the same, we put it aside and take the next one form the pile. It there are only 5 books in a pile, that is OK. What if there are 5000 of them?
This was solved long ago. In order to find a book by its title we need to arrange all books we have in a rows in a particular order. We put all the books in a different shelves according of what letter the title begins with. Then we sort all the books on each row in an alphabetical order, so we could find any of them very quickly. More importantly, we can very quickly find out if we don't have one, without looking-up each one we have in a room.
These concepts are called ''partitioning'' (spitting up according to some criteria) and ''pre-sorting'' (pre-arranging items in a particular order). A row, is an ordered sequence of items.
Now lets imagine a post office of old times, when mail was shipped from town to town by horses. This is where some fundamental concepts of modern Computer Science came from.
One of them is a quite simple idea of a bucket sort. The most common example is sorting of mail at a mail-hub to be routed to different locations according to an area codes.
Imagine that there is a room with several buckets in it, one bucket for each area code in a neighborhood. Some person reading the area code field on an envelope taken from a big bag, and then he drops a letter in a bucket labelled with the same area code. There is another bucket, for envelopes that didn't match any of those. Later mail from each bucket would be put into a bag and sent to next destination - some local post office. This is a process to model.
Programming is a discipline of modeling a real-world phenomena. We will see how shortly.