Revision of 2.2.1 Representing Sequences from 15 July 2009 - 8:41pm

The revisions let you track differences between multiple versions of a post.

Printer-friendly versionPrinter-friendly version

One of the useful structures we can build with pairs is a sequence — an ordered collection of data objects. There are, of course, many ways to represent sequences in terms of pairs. One particularly straightforward representation is illustrated in figure 2.4, where the sequence 1, 2, 3, 4 is represented as a chain of pairs. The car of each pair is the corresponding item in the chain, and the cdr of the pair is the next pair in the chain. The cdr of the final pair signals the end of the sequence by pointing to a distinguished value that is not a pair, represented in box-and-pointer diagrams as a diagonal line and in programs as the value of the variable nil. The entire sequence is constructed by nested cons operations:

(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))

Such a sequence of pairs, formed by nested conses, is called a list, and Scheme provides a primitive called list to help in constructing lists.[8] The above sequence could be produced by (list 1 2 3 4). In general,

(list <a1> <a2> … <an>)

is equivalent to

(cons <a1> (cons <a2> (cons … (cons <an> nil) …)))

Lisp systems conventionally print lists by printing the sequence of elements, enclosed in parentheses. Thus, the data object in figure 2.4 is printed as (1 2 3 4):

(define one-through-four (list 1 2 3 4))

one-through-four
(1 2 3 4)

Be careful not to confuse the expression (list 1 2 3 4) with the list (1 2 3 4), which is the result obtained when the expression is evaluated. Attempting to evaluate the expression (1 2 3 4) will signal an error when the interpreter tries to apply the procedure 1 to arguments 2, 3, and 4.

We can think of car as selecting the first item in the list, and of cdr as selecting the sublist consisting of all but the first item. Nested applications of car and cdr can be used to extract the second, third, and subsequent items in the list.[9] The constructor cons makes a list like the original one, but with an additional item at the beginning.

(car one-through-four)
1

(cdr one-through-four)
(2 3 4)
(car (cdr one-through-four))
2

(cons 10 one-through-four)
(10 1 2 3 4)

(cons 5 one-through-four)
(5 1 2 3 4)

The value of nil, used to terminate the chain of pairs, can be thought of as a sequence of no elements, the empty list. The word nil is a contraction of the Latin word nihil, which means “nothing.”[10]

List operations

The use of pairs to represent sequences of elements as lists is accompanied by conventional programming techniques for manipulating lists by successively “cdring down” the lists. For example, the procedure list-ref takes as arguments a list and a number n and returns the nth item of the list. It is customary to number the elements of the list beginning with 0. The method for computing list-ref is the following:

  • For n = 0, list-ref should return the car of the list.
  • Otherwise, list-ref should return the (n - 1)st item of the cdr of the list.
(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))

(list-ref squares 3)
16

Often we cdr down the whole list. To aid in this, Scheme includes a primitive predicate null?, which tests whether its argument is the empty list. The procedure length, which returns the number of items in a list, illustrates this typical pattern of use:

(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define odds (list 1 3 5 7))

(length odds)
4

The length procedure implements a simple recursive plan. The reduction step is:

  • The length of any list is 1 plus the length of the cdr of the list.

This is applied successively until we reach the base case:

  • The length of the empty list is 0.

We could also compute length in an iterative style:

(define (length items)
  (define (length-iter a count)
    (if (null? a)
        count
        (length-iter (cdr a) (+ 1 count))))
  (length-iter items 0))

Another conventional programming technique is to “cons up” an answer list while cdring down a list, as in the procedure append, which takes two lists as arguments and combines their elements to make a new list:

(append squares odds)
(1 4 9 16 25 1 3 5 7)

(append odds squares)
(1 3 5 7 1 4 9 16 25)

Append is also implemented using a recursive plan. To append lists list1 and list2, do the following:

  • If list1 is the empty list, then the result is just list2.
  • Otherwise, append the cdr of list1 and list2, and cons the car of list1 onto the result:
(define (append list1 list2)
  (if (null? list1)
      list2
      (cons (car list1) (append (cdr list1) list2))))

One extremely useful operation is to apply some transformation to each element in a list and generate the list of results. For instance, the following procedure scales each number in a list by a given factor:

(define (scale-list items factor)
  (if (null? items)
      nil
      (cons (* (car items) factor)
            (scale-list (cdr items) factor))))
(scale-list (list 1 2 3 4 5) 10)
(10 20 30 40 50)

We can abstract this general idea and capture it as a common pattern expressed as a higher-order procedure, just as in section 1.3. The higher-order procedure here is called map. Map takes as arguments a procedure of one argument and a list, and returns a list of the results produced by applying the procedure to each element in the list:[12]

(define (map proc items)
  (if (null? items)
      nil
      (cons (proc (car items))
            (map proc (cdr items)))))
(map abs (list -10 2.5 -11.6 17))
(10 2.5 11.6 17)
(map (lambda (x) (* x x))
     (list 1 2 3 4))
(1 4 9 16)

Now we can give a new definition of scale-list in terms of map:

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

Map is an important construct, not only because it captures a common pattern, but because it establishes a higher level of abstraction in dealing with lists. In the original definition of scale-list, the recursive structure of the program draws attention to the element-by-element processing of the list. Defining scale-list in terms of map suppresses that level of detail and emphasizes that scaling transforms a list of elements to a list of results. The difference between the two definitions is not that the computer is performing a different process (it isn’t) but that we think about the process differently. In effect, map helps establish an abstraction barrier that isolates the implementation of procedures that transform lists from the details of how the elements of the list are extracted and combined. Like the barriers shown in figure 2.1, this abstraction gives us the flexibility to change the low-level details of how sequences are implemented, while preserving the conceptual framework of operations that transform sequences to sequences. Section 2.2.3 expands on this use of sequences as a framework for organizing programs.

[8] In this book, we use list to mean a chain of pairs terminated by the end-of-list marker. In contrast, the term list structure refers to any data structure made out of pairs, not just to lists. [back]
[9]

Since nested applications of car and cdr are cumbersome to write, Lisp dialects provide abbreviations for them — for instance,

(cadr <arg />) = (car (cdr <arg>))

The names of all such procedures start with c and end with r. Each a between them stands for a car operation and each d for a cdr operation, to be applied in the same order in which they appear in the name. The names car and cdr persist because simple combinations like cadr are pronounceable. [back]

[10] It’s remarkable how much energy in the standardization of Lisp dialects has been dissipated in arguments that are literally over nothing: Should nil be an ordinary name? Should the value of nil be a symbol? Should it be a list? Should it be a pair? In Scheme, nil is an ordinary name, which we use in this section as a variable whose value is the end-of-list marker (just as true is an ordinary variable that has a true value). Other dialects of Lisp, including Common Lisp, treat nil as a special symbol. The authors of this book, who have endured too many language standardization brawls, would like to avoid the entire issue. Once we have introduced quotation in section 2.3, we will denote the empty list as '() and dispense with the variable nil entirely. [back]
[12]

Scheme standardly provides a map procedure that is more general than the one described here. This more general map takes a procedure of n arguments, together with n lists, and applies the procedure to all the first elements of the lists, all the second elements of the lists, and so on, returning a list of the results. For example:

(map + (list 1 2 3) (list 40 50 60) (list 700 800 900))
(741 852 963)

(map (lambda (x y) (+ x (* 2 y)))
     (list 1 2 3)
     (list 4 5 6))
(9 12 15)

[back]

Exercises

Exercise 2.17

in

Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list:

(last-pair (list 23 72 149 34))
(34)

Exercise 2.18

in

Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

(reverse (list 1 4 9 16 25))
(25 16 9 4 1)

Exercise 2.19

in

Consider the change-counting program of section 1.2.2. It would be nice to be able to easily change the currency used by the program, so that we could compute the number of ways to change a British pound, for example. As the program is written, the knowledge of the currency is distributed partly into the procedure first-denomination and partly into the procedure count-change (which knows that there are five kinds of U.S. coins). It would be nicer to be able to supply a list of coins to be used for making change.

We want to rewrite the procedure cc so that its second argument is a list of the values of the coins to use rather than an integer specifying which coins to use. We could then have lists that defined each kind of currency:

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

We could then call cc as follows:

(cc 100 us-coins)
292

To do this will require changing the program cc somewhat. It will still have the same form, but it will access its second argument differently, as follows:

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

Define the procedures first-denomination, except-first-denomination, and no-more? in terms of primitive operations on list structures. Does the order of the list coin-values affect the answer produced by cc? Why or why not?

Exercise 2.20

in

The procedures +, *, and list take arbitrary numbers of arguments. One way to define such procedures is to use define with dotted-tail notation. In a procedure definition, a parameter list that has a dot before the last parameter name indicates that, when the procedure is called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final parameter’s value will be a list of any remaining arguments. For instance, given the definition

(define (f x y . z) <body>)

the procedure f can be called with two or more arguments. If we evaluate

(f 1 2 3 4 5 6)

then in the body of f, x will be 1, y will be 2, and z will be the list (3 4 5 6). Given the definition

(define (g . w) <body>)

the procedure g can be called with zero or more arguments. If we evaluate

(g 1 2 3 4 5 6)

then in the body of g, w will be the list (1 2 3 4 5 6).[11]

Use this notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same even-odd parity as the first argument. For example,

(same-parity 1 2 3 4 5 6 7)
(1 3 5 7)

(same-parity 2 3 4 5 6 7)
(2 4 6)
[11]

To define f and g using lambda we would write

(define f (lambda (x y . z) <body>))
(define g (lambda w <body>))

[back]

Exercise 2.21

in

The procedure square-list takes a list of numbers as argument and returns a list of the squares of those numbers.

(square-list (list 1 2 3 4))
(1 4 9 16)

Here are two different definitions of square-list. Complete both of them by filling in the missing expressions:

(define (square-list items)
  (if (null? items)
      nil
      (cons <??> <??>)))
(define (square-list items)
  (map <??> <??>))

Exercise 2.22

in

Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) 
              (cons (square (car things))
                    answer))))
  (iter items nil))

Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?

Louis then tries to fix his bug by interchanging the arguments to cons:

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

This doesn’t work either. Explain.

Exercise 2.23

in

The procedure for-each is similar to map. It takes as arguments a procedure and a list of elements. However, rather than forming a list of the results, for-each just applies the procedure to each of the elements in turn, from left to right. The values returned by applying the procedure to the elements are not used at all — for-each is used with procedures that perform an action, such as printing. For example,

(for-each (lambda (x) (newline) (display x))
          (list 57 321 88))
57
321
88

The value returned by the call to for-each (not illustrated above)can be something arbitrary, such as true. Give an implementation of for-each.

Comments

Beats By Dre Monster

SYNC by 50 If you’re like most of us, you woke up one morning this week and realized it’s almost December,SYNC by 50 and the holidays are swiftly approaching. STREET by 50 And, of course, you still don’t know what to get a few people on your list.We all know that headphones are a dime a dozen. STREET by 50 But a headphone that receives equal points for style and functionality, however, is a rare find. sms by 50 Some of our friends in the press know SMS Audio headphones fit the bill, sms by 50 and recommend you put them on your holiday shopping list this year: Beats By Dre Monster Rolling Stone included the limited edition Yellow STREET by 50 over-ear headphones in its 2012 holiday gift guide featured in the December issue.Beats By Dre MonsterWhat did Rolling Stone have to say about SMS Audio?
http://www.smsby50-beatsbydre.com/

beats by dre clearance

cheap monster beats Before I tell you about my experience, cheap monster beats let me tell you a bit more about these headphones. beats by dre solo According to the information I’ve read, Dr. beats by dre solo Dre worked with Monster Cable and Robert Brunner, dre beats an industrial designer, dre beats for more than two years to perfect these headphones. beats by dre clearance In Dr. Dre’s words,People aren’t hearing all the music beats by dre clearance.

http://www.marking.co.il/longest.asp

http://www.fjotic.com/susceptible.asp http://www.fjotic.com/speeches.asp http://www.fjotic.com/hwwlsp/embarrassing.asp http://www.fjotic.com/hwwlsp/least.asp http://www.fjotic.com/hwxlyz/virtue.asp.asp http://www.fjrcxh.com/electronic.asp http://www.fjrcxh.com/gleaned.asp http://www.fjrcxh.com/programs.asp http://www.fjrcxh.com/images/Intelligence.asp http://www.fjrcxh.com/images/largely.asp http://xm.hxrc.com/publicly.aspx http://xm.hxrc.com/reveal.aspx http://xm.hxrc.com/guide/maintain.aspx http://xm.hxrc.com/guide/credibility.aspx http://xm.hxrc.com/images/character.aspx http://zz.hxrc.com/messenger.aspx http://zz.hxrc.com/UC/followers.asp http://zz.hxrc.com/UC/appendix.asp http://zz.hxrc.com/js/radicalism.asp http://www.winpard.com/promiscuity.asp http://www.winpard.com/articles.asp http://www.winpard.com/config/celebrity.asp http://www.winpard.com/config/describes.asp http://www.winpard.com/html/offensive.asp http://www.szfylaw.com/withholding.asp http://www.szfylaw.com/individuals.asp http://www.szfylaw.com/COUNT/indicate.asp http://www.szfylaw.com/szhome/acquired.asp http://www.shimeia.com//constraints.asp http://www.shimeia.com//exploiting.asp http://www.shimeia.com/shimeia/manner.asp http://www.shimeia.com/shimeia/tarnish.asp http://www.shimeia.com/INC/reputation.asp http://www.3200120.com/harassed.asp http://www.3200120.com/secret.asp http://www.3200120.com/12t_manage/bureau.asp http://www.3200120.com/12t_manage/releases.asp http://www.3200120.com/fckeditor/editor/dossiers.asp http://www.pirpur.co.il/ordered.asp http://www.pirpur.co.il/understand.asp http://www.pirpur.co.il/flash/journalist.asp http://www.pirpur.co.il/flash/precisely.asp http://www.pirpur.co.il/images/similar.asp http://www.marking.co.il/activity.asp http://www.marking.co.il/longest.asp http://www.marking.co.il/contact/controversy.asp http://www.marking.co.il/contact/eavesdropping.asp http://www.marking.co.il/executepage/Operation.asp http://www.insulin.co.il/review.asp http://www.insulin.co.il/disreputable.asp http://www.insulin.co.il/evidence.asp http://www.insulin.co.il/scandals.asp http://www.insulin.co.il/president.asp http://www.steiformacio.com/privat/contect.asp http://www.steiformacio.com/forovisual/listasdomon.asp http://www.steiformacio.com/forovisual/creamensajes.asp http://www.steiformacio.com/cive/pagoasistes.asp http://www.steiformacio.com/banc/resposteas.asp http://www.vidapositiva.com/lastet.asp http://www.vidapositiva.com/menuHned.asp http://www.vidapositiva.com/buscador.asp http://www.vidapositiva.com/notise.asp http://www.vidapositiva.com/redruce.asp http://www.cafelapalma.com/bbdd/cass.asp http://www.cafelapalma.com/imagenes/cheehae.asp http://www.cafelapalma.com/imagenes/paster.asp http://www.cafelapalma.com/expo/Expo.asp http://www.cafelapalma.com/bbdd/mouace.asp http://www.tangxiaohua.com/DRM/chexks.asp http://www.tangxiaohua.com/data/dscear.aspx
http://www.marking.co.il/longest.asp http://www.marking.co.il/longest.asp

http://bntu.nu/db/Vuitton.asp

http://ev-evu.org/forum.php?mod=viewthread&tid=1858817 http://gzmaya.net/bbs//forum.php?mod=viewthread&tid=7667760 http://glixya.com/index.php?do=/blog/36213/incredible-atmosphere-the-nik… http://www.betsclup.com/entry.php?400-Nike-Environment-Construction-Tria… http://www.apfanhai.com/thread-2804100-1-1.html http://www.hebidianjing.com/web/thread-386658-1-1.html http://iqchannel.com//read_blog/187040/stops-and-also-hot-sale-nike-merc… http://truck56.com/bbs/forum.php?mod=viewthread&tid=1082490 http://bbs.lybyjj.com/forum.php?mod=viewthread&tid=3063945 http://42.121.33.168/forum.php?mod=viewthread&tid=2346158 http://zk.duerain.com/sns/forum.php?mod=viewthread&tid=919392 http://www.zghwlm.net/forum.php?mod=viewthread&tid=513607&fromuid=97734 http://www.abcdefghigklmnopqrstuvwxyz.net/forum.php?mod=viewthread&tid=5… http://islamly.com/index.php?do=/blog/84887/the-very-first-unique-united… http://sc-nanbu.com.cp-dd-us-3.webhostbox.net/thread-1195059-1-1.html http://three-body.com/forum.php?mod=viewthread&tid=390356&fromuid=52165 http://www.wx0.net/forum.php?mod=viewthread&tid=282535 http://www.bocaishiji.com/thread-1220222-1-1.html http://www.vai99.com/bbs/forum.php?mod=viewthread&tid=537524&fromuid=68520 http://www.ivygenerator.de/nikeonline/2014/01/20/excellent-nike-footwear… http://www.1886ckj.com/forum.php?mod=viewthread&tid=301564&fromuid=31860 http://forums.webcrow.jp/forum.php?mod=viewthread&tid=190530 http://www.c114doc.com/bbs/forum.php?mod=viewthread&tid=3216695 http://pudongoffices.com/forum.php?mod=viewthread&tid=4117230 http://www.d1yx.cn/forum.php?mod=viewthread&tid=460949 http://hjliren.com/forum.php?mod=viewthread&tid=1511754&fromuid=73886 http://bbs.51mainet.com/forum.php?mod=viewthread&tid=62480 http://lovenikelife.blogspot.com/2014/01/nike-footwear-make-sure-less-da… http://26w.com.cn/forum.php?mod=viewthread&tid=576464&fromuid=50909 http://www.poker-mania.biz/index.php?do=/blog/2597/recollect-2013-estima… http://www.cutekids.cn/forum.php?mod=viewthread&tid=361784&fromuid=28264 http://nakedconvo.com/index.php?do=/blog/38616/incredible-atmosphere-the… http://katong.bee.pl/forum.php?mod=viewthread&tid=2453974 http://58po.com/forum.php?mod=viewthread&tid=542956 http://www.isamrt.com/forum.php?mod=viewthread&tid=3055349&fromuid=162928 http://www.hebidianjing.com/web/thread-386664-1-1.html http://piccasa.ru/index.php?do=/blog/41453/nike-2014-african-american-hi… http://www.yy2080.cn/forum.php?mod=viewthread&tid=229400 http://www.hotliao.com/forum.php?mod=viewthread&tid=3175072 http://bbs.mhmqxx.mhedu.sh.cn/forum.php?mod=viewthread&tid=1815374 http://homestyles.snappages.com/blog/2014/01/22/how-come-trainer-assault… http://www.dapingyin.com/forum.php?mod=viewthread&tid=356997 http://huangshangyuanji.com/forum.php?mod=viewthread&tid=448604&fromuid=… http://www.xiangfanbbs.com/forum.php?mod=viewthread&tid=1330028&fromuid=… http://bbs.m.1799.com/forum.php?mod=viewthread&tid=2507407&fromuid=500434 http://bb.16feel.com/forum.php?mod=viewthread&tid=813416&fromuid=67371 http://tzlmt.xoom.it/forum.php?mod=viewthread&tid=1745049 http://mail.eachina.org.cn:8080/upload/forum.php?mod=viewthread&tid=2463235 http://espace24.com/upload/index.php?do=/blog/308961/the-initial-excepti… http://www.fuyangbaijiale.com/forum.php?mod=viewthread&tid=1503740&fromu… http://www.amiella.com/forum.php?mod=viewthread&tid=324881 http://uctest.ucweb.com:81/discuzx2/forum.php?mod=viewthread&tid=230737 http://bobobbs.linshiwangzhan.com/forum.php?mod=viewthread&tid=1576986 http://tiaotiaonet.com/forum.php?mod=viewthread&tid=1547473&fromuid=106671 http://arassociatesonline.com/index.php?do=/blog/124814/ideal-lebron-11-… http://www.huangshangyuanji.com/forum.php?mod=viewthread&tid=448610&from… http://www.eebomc.com/ztbbs/forum.php?mod=viewthread&tid=3659769 http://romcf.com/forum.php?mod=viewthread&tid=232053 http://pic.yjyhlt.com/forum.php?mod=viewthread&tid=3555991&fromuid=217181 http://www.u8uu.com/bbs/forum.php?mod=viewthread&tid=7271573 http://parsiga.com/index.php?do=/blog/32054/the-actual-discharge-day-associated-with-top-selling-nike-kd-6-閿熸枻鎷穌c閿熸枻鎷?nike-kd/ http://zaojiao.siai.co/forum.php?mod=viewthread&tid=218601 http://www.yoyaer.com/forum.php?mod=viewthread&tid=1569206&fromuid=92206 http://121.199.47.220/forum.php?mod=viewthread&tid=830578&fromuid=136663 http://ssyl-ln.com/forum.php?mod=viewthread&tid=3924946 http://www.muslimdunia.com/index.php?do=/blog/73856/expensive-purchase-n… http://brchinese.com/forum.php?mod=viewthread&tid=1029369 http://beishanren.com/forum.php?mod=viewthread&tid=664807&fromuid=61298 http://abcdefghigklmnopqrstuvwxyz.net/forum.php?mod=viewthread&tid=528356 http://www.ppsbw.com/forum.php?mod=viewthread&tid=1315988&fromuid=106862
http://bntu.nu/db/Vuitton.asp http://bntu.nu/db/Vuitton.asp

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options