1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
|
<P>
<P><CENTER><IMG SRC="../ss-pics/lockers.jpg" ALT="figure: lockers"></CENTER><A NAME="lockers"></A><P><CENTER>A row of boxes
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 23: Vectors</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 23</H2>
<H1>Vectors</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../simply.jpg" ALT="cover photo">
<TD><TABLE>
<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR>University of California, Berkeley</CITE>
<TR><TD align="right"><CITE><A HREF="http://ccrma.stanford.edu/~matt">Matthew
Wright</A><BR>University of California, Santa Barbara</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/ssch23.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../ss-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../ssch22/files.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch24/spread.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="http://mitpress.mit.edu/0262082810">MIT
Press web page for <CITE>Simply Scheme</CITE></A>
</TABLE></TABLE>
<HR>
<P>So far all the programs we've written in this book have had no memory of the
past history of the computation. We invoke a function with certain
arguments, and we get back a value that depends only on those arguments.
Compare this with the operation of Scheme itself:
<P><PRE>> (foo 3)
ERROR: FOO HAS NO VALUE
> (define (foo x)
(word x x))
> (foo 3)
33
</PRE>
<P>Scheme <EM>remembers</EM> that you have defined <CODE>foo</CODE>, so its response to
the very same expression is different the second time. Scheme maintains a
record of certain results of its past interaction with you; in particular,
Scheme remembers the global variables that you have defined. This record is
called its <EM>state.</EM>
<P>Most of the programs that people use routinely are full of state; your text
editor, for example, remembers all the characters in your file. In this
chapter you will learn how to write programs with state.
<P><H2>The Indy 500</H2>
<P>The Indianapolis 500 is an annual 500-mile automobile race, famous among
people who like that sort of thing. It's held at the Indianapolis Motor
<A NAME="g1"></A>
Speedway, a racetrack in Indianapolis, Indiana. (Indiana is better known as
the home of Dan Friedman, the coauthor of some good books about Scheme.)
The racetrack is 2½ miles long, so, as you might imagine, the
racers have to complete 200 laps in order to finish the race. This means
that someone has to keep track of how many laps each car has completed so
far.
<P>Let's write a program to help this person keep count. Each car has a
number, and the count person will invoke the procedure <CODE>lap</CODE> with that
number as argument every time a car completes a lap. The procedure will
return the number of laps that that car has completed altogether:
<P><PRE>> (lap 87)
1
> (lap 64)
1
> (lap 17)
1
> (lap 64)
2
> (lap 64)
3
</PRE>
<P>(Car 64 managed to complete three laps before the other cars
completed two because the others had flat tires.) Note that we typed
the expression <CODE>(lap 64)</CODE> three times and got three different answers.
<CODE>Lap</CODE> isn't a function! A function has to return the same answer
whenever it's invoked with the same arguments.
<P><H2>Vectors</H2>
<P>The point of this chapter is to show how procedures like <CODE>lap</CODE> can be
written. To accomplish this, we're going to use a data structure called a
<EM>vector.</EM> (You may have seen something similar in other
programming languages under the name "array.")
<P>A vector is, in effect, a row of boxes into which values can be put. Each
vector has a fixed number of boxes; when you create a vector, you have to say
how many boxes you want. Once a vector is created, there are two things you
can do with it: You can put a new value into a box (replacing any old value
that might have been there), or you can examine the value in a box. The
boxes are numbered, starting with zero.
<P><PRE>> (define v (<A NAME="g2"></A>make-vector 5))
> (<A NAME="g3"></A>vector-set! v 0 'shoe)
> (vector-set! v 3 'bread)
> (vector-set! v 2 '(savoy truffle))
> (<A NAME="g4"></A>vector-ref v 3)
BREAD
</PRE>
<P>There are several details to note here. When we invoke <CODE>make-vector</CODE> we
give it one argument, the number of boxes we want the vector to have. (In
this example, there are five boxes, numbered 0 through 4. There is no
box 5.) When we create the vector, there is nothing in any of the
boxes.<A NAME="text1" HREF="vectors#ft1">[1]</A>
<P>We put things in boxes using the <CODE>vector-set!</CODE> procedure. The
exclamation point in its name, indicates that this is a <EM>mutator</EM>—a procedure that changes the value of some previously
created data structure. The exclamation point is pronounced "bang," as in
"vector set bang." (Scheme actually has several such mutators, including
mutators for lists, but this is the only one we'll use in this book.
A procedure that modifies its argument is also called <EM>destructive.</EM>) The arguments to <CODE>vector-set!</CODE> are the vector, the
number of the box (the <EM>index</EM>), and the desired new value. Like <CODE>define</CODE>, <CODE>vector-set!</CODE> returns an unspecified value.
<P>We examine the contents of a box using <CODE>vector-ref</CODE>, which takes two
arguments, the vector and an index. <CODE>Vector-ref</CODE> is similar to <CODE>list-ref</CODE>, except that it operates on vectors instead of lists.
<P>We can change the contents of a box that already has something in it.
<P><PRE>> (vector-set! v 3 'jewel)
> (vector-ref v 3)
JEWEL
</PRE>
<P>The old value of box 3, <CODE>bread</CODE>, is no longer there. It's
been replaced by the new value.
<P><PRE>> (vector-set! v 1 741)
> (vector-set! v 4 #t)
> v
#(SHOE 741 (SAVOY TRUFFLE) JEWEL #T)
</PRE>
<P>Once the vector is completely full, we can print its value. Scheme
prints vectors in a format like that of lists, except that there is a number
sign (<CODE>#</CODE>) before the open parenthesis. If you ever have need for a
constant vector (one that you're not going to mutate), you can quote it
using the same notation:
<P><PRE>> (vector-ref '#(a b c d) 2)
C
</PRE>
<P><H2>Using Vectors in Programs</H2>
<P>To implement our <CODE>lap</CODE> procedure, we'll keep its state information, the
lap counts, in a vector. We'll use the car number as the index into the
vector. It's not enough to create the vector; we have to make sure that
each box has a zero as its initial value.
<P><PRE>(define *lap-vector* (make-vector 100))
(define (<A NAME="g5"></A>initialize-lap-vector index)
(if (< index 0)
'done
(begin (vector-set! *lap-vector* index 0)
(initialize-lap-vector (- index 1)))))
> (initialize-lap-vector 99)
DONE
</PRE>
<P>We've created a global variable whose value is the vector. We
used a recursive procedure to put a zero into each box of the
vector.<A NAME="text2" HREF="vectors#ft2">[2]</A> Note that the
vector is of length 100, but its largest index is 99. Also, the base case
of the recursion is that the index is less than zero, not equal to zero as
in many earlier examples. That's because zero is a valid index.
<P>Now that we have the vector, we can write <CODE>lap</CODE>.
<P><PRE>(define (<A NAME="g6"></A>lap car-number)
(vector-set! *lap-vector*
car-number
(+ (vector-ref *lap-vector* car-number) 1))
(vector-ref *lap-vector* car-number))
</PRE>
<P>Remember that a procedure body can include more than one
expression. When the procedure is invoked, the expressions will be
evaluated in order. The value returned by the procedure is the value of the
last expression (in this case, the second one).
<P><CODE>Lap</CODE> has both a return value and a side effect. The job of the first
expression is to carry out that side effect, that is, to add 1 to the lap
count for the specified car. The second expression looks at the value we
just put in a box to determine the return value.
<P><H2>Non-Functional Procedures and State</H2>
<P>We remarked earlier that <CODE>lap</CODE> isn't a function because invoking it
twice with the same argument doesn't return the same value both
times.<A NAME="text3" HREF="vectors#ft3">[3]</A>
<P>It's not a coincidence that <CODE>lap</CODE> also violates functional programming
by maintaining state information. Any procedure whose return value is not a
function of its arguments (that is, whose return value is not always the
same for any particular arguments) must depend on knowledge of what has
happened in the past. After all, computers don't pull results out of the
air; if the result of a computation doesn't depend entirely on the arguments
we give, then it must depend on some other information available to the
program.
<P>Suppose somebody asks you, "Car 54 has just completed a lap; how many has it
completed in all?" You can't answer that question with only the information
in the question itself; you have to remember earlier events in the race. By
contrast, if someone asks you, "What's the plural of `book'?" what has
happened in the past doesn't matter at all.
<P>The connection between non-functional procedures and state also applies to
non-functional Scheme primitives. The <CODE>read</CODE> procedure, for example,
returns different results when you invoke it repeatedly with the same
argument because it remembers how far it's gotten in the file. That's why
the argument is a port instead of a file name: A port is an abstract data
type that includes, among other things, this piece of state. (If you're
reading from the keyboard, the state is in the person doing the typing.)
<P>A more surprising example is the <A NAME="g7"></A><CODE>random</CODE> procedure that you met in
Chapter 2. <CODE>Random</CODE> isn't a function because it doesn't always
return the same value when called with the same argument. How does <CODE>random</CODE> compute its result? Some versions of <CODE>random</CODE> compute a number
that's based on the current time (in tiny units like milliseconds so you
don't get the same answer from two calls in quick succession). How does
your computer know the time? Every so often some procedure (or some
hardware device) adds 1 to a remembered value, the number of milliseconds
since midnight. That's state, and <CODE>random</CODE> relies on it.
<P>The most commonly used algorithm for random numbers is a little trickier;
each time you invoke <CODE>random</CODE>, the result is a function of <EM>the
result from the last time you invoked it.</EM> (The procedure is pretty
complicated; typically the old number is multiplied by some large, carefully
chosen constant, and only the middle digits of the product are kept.) Each
time you invoke <CODE>random</CODE>, the returned value is stashed away somehow so
that the next invocation can remember it. That's state too.
<P>Just because a procedure remembers something doesn't necessarily make it
stateful. <EM>Every</EM> procedure remembers the arguments with which it was
invoked, while it's running. Otherwise the arguments wouldn't be able to
affect the computation. A procedure whose result depends only on its
arguments (the ones used in the current invocation) is functional. The
procedure is non-functional if it depends on something outside of its
current arguments. It's that sort of "long-term" memory that we consider
to be state.
<P>In particular, a procedure that uses <CODE>let</CODE> isn't stateful merely because
the body of the <CODE>let</CODE> remembers the values of the variables created by the
<CODE>let</CODE>. Once <CODE>let</CODE> returns a value, the variables that it created no
longer exist. You couldn't use <CODE>let</CODE>, for example, to carry out the
kind of remembering that <CODE>random</CODE> needs. <CODE>Let</CODE> doesn't remember a
value <EM>between</EM> invocations, just during a single invocation.
<P><H2>Shuffling a Deck</H2>
<P>One of the advantages of the vector data structure is that it allows
elements to be rearranged. As an example, we'll create and shuffle a
deck of cards.
<P>We'll start with a procedure <CODE>card-list</CODE> that returns a list of all the
cards, in standard order:
<P><PRE>(define (<A NAME="g8"></A>card-list)
(reduce append
(map (lambda (suit) (map (lambda (rank) (word suit rank))
'(a 2 3 4 5 6 7 8 9 10 j q k)))
'(h s d c))))
> (card-list)
(HA H2 H3 H4 H5 H6 H7 H8 H9 H10 HJ HQ HK
SA S2 S3 S4 S5 S6 S7 S8 S9 S10 SJ SQ SK
DA D2 D3 D4 D5 D6 D7 D8 D9 D10 DJ DQ DK
CA C2 C3 C4 C5 C6 C7 C8 C9 C10 CJ CQ CK)
</PRE>
<P>In writing <CODE>card-list</CODE>, we need <CODE>reduce append</CODE> because the result
from the outer invocation of <CODE>map</CODE> is a list of lists: <CODE>((HA H2 …) (SA …) …)</CODE>.<A NAME="text4" HREF="vectors#ft4">[4]</A>
<P>Each time we want a new deck of cards, we start with this list of 52 cards,
copy the list into a vector, and shuffle that vector. We'll use the Scheme
primitive <CODE><A NAME="g9"></A><CODE>list->vector</CODE></CODE>, which takes a list as argument and
returns a vector of the same length, with the boxes initialized to the
corresponding elements of the list. (There is also a procedure <CODE><A NAME="g10"></A><CODE>vector->list</CODE></CODE> that does the reverse. The characters <CODE>-></CODE> in
these function names are meant to look like an arrow
(→); this is a Scheme convention for functions
that convert information from one data type to another.)
<P><PRE>(define (<A NAME="g11"></A>make-deck)
(shuffle! (list->vector (card-list)) 51))
(define (<A NAME="g12"></A>shuffle! deck index)
(if (< index 0)
deck
(begin (vector-swap! deck index (random (+ index 1)))
(shuffle! deck (- index 1)))))
(define (<A NAME="g13"></A>vector-swap! vector index1 index2)
(let ((temp (vector-ref vector index1)))
(vector-set! vector index1 (vector-ref vector index2))
(vector-set! vector index2 temp)))
</PRE>
<P>
<P>Now, each time we call <CODE>make-deck</CODE>, we get a randomly shuffled
vector of cards:
<P><PRE>> (make-deck)
#(C4 SA C7 DA S4 D9 SQ H4 C10 D5 H9 S10 D6
S9 CA C9 S2 H7 S5 H6 D7 HK S7 C3 C2 C6
HJ SK CQ CJ D4 SJ D8 S8 HA C5 DK D3 HQ
D10 H8 DJ C8 H2 H5 H3 CK S3 DQ S6 D2 H10)
> (make-deck)
#(CQ H7 D10 D5 S8 C7 H10 SQ H4 H3 D8 C9 S7
SK DK S6 DA D4 C6 HQ D6 S2 H5 CA H2 HJ
CK D7 H6 HA CJ C4 SJ HK SA C2 D2 S4 DQ
S5 C10 H9 D9 C5 D3 DJ C3 S9 S3 C8 S10 H8)
</PRE>
<P>How does the shuffling algorithm work? Conceptually it's not complicated,
but there are some implementation details that make the actual procedures a
little tricky. The general idea is this: We want all the cards shuffled
into a random order. So we choose any card at random, and make it the first
card. We're then left with a one-card-smaller deck to shuffle, and we do
that by recursion. (This algorithm is similar to selection sort from
Chapter 15, except that we select a random card each time instead of
selecting the smallest value.)
<P>The details that complicate this algorithm have to do with the fact that
we're using a vector, in which it's easy to change the value in one
particular position, but it's not easy to do what would otherwise be the
most natural thing: If you had a handful of actual cards and wanted to move
one of them to the front, you'd slide the other cards over to make room.
There's no "sliding over" in a vector. Instead we use a trick; we happen
to have an empty slot, the one from which we removed the randomly chosen
card, so instead of moving several cards, we just move the one card that was
originally at the front into that slot. In other words, we exchange two
cards, the randomly chosen one and the one that used to be in front.
<P>Second, there's nothing comparable to <CODE>cdr</CODE> to provide a
one-card-smaller vector to the recursive invocation. Instead, we must use
the entire vector and also provide an additional <CODE>index</CODE> argument, a
number that keeps track of how many cards remain to be shuffled. It's
simplest if each recursive invocation is responsible for the range of cards
from position <CODE>0</CODE> to position <CODE>index</CODE> of the vector, and therefore
the program actually moves each randomly selected card to the <EM>end</EM> of
the remaining portion of the deck.
<P><H2>More Vector Tools</H2>
<P>If you want to make a vector with only a few boxes, and you know in advance
what values you want in those boxes, you can use the constructor
<A NAME="g14"></A><CODE>vector</CODE>. Like <CODE>list</CODE>, it takes any number of arguments and
returns a vector containing those arguments as elements:
<P><PRE>> (define beatles (vector 'john 'paul 'george 'pete))
> (vector-set! beatles 3 'ringo)
> beatles
#(JOHN PAUL GEORGE RINGO)
</PRE>
<P>The procedure <A NAME="g15"></A><CODE>vector-length</CODE> takes a vector as argument and returns the
number of boxes in the vector.
<P><PRE>> (vector-length beatles)
4
</PRE>
<P>The predicate <CODE>equal?</CODE>, which we've used with words and lists, also
accepts vectors as arguments. Two vectors are equal if they are the same
size and all their corresponding elements are equal. (A list and a vector
are never equal, even if their elements are equal.)
<P>Finally, the predicate <A NAME="g16"></A><CODE>vector?</CODE> takes anything as argument and returns
<CODE>#t</CODE> if and only if its argument is a vector.
<P><H2>The Vector Pattern of Recursion</H2>
<P>Here are two procedures that you've seen earlier in this chapter, which do
something to each element of a vector:
<P><PRE>(define (initialize-lap-vector index)
(if (< index 0)
'done
(begin (vector-set! *lap-vector* index 0)
(initialize-lap-vector (- index 1)))))
(define (shuffle! deck index)
(if (< index 0)
deck
(begin (vector-swap! deck index (random (+ index 1)))
(shuffle! deck (- index 1)))))
</PRE>
<P>These procedures have a similar structure, like the similarities we found in
other recursive patterns. Both of these procedures take an index as an
argument, and both have
<P><PRE>(< index 0)
</PRE>
<P>as their base case. Also, both have, as their recursive case, a
<CODE>begin</CODE> in which the first action does something to the vector element
selected by the current index, and the second action is a recursive call
with the index decreased by one. These procedures are initially called with
the largest possible index value.
<P>In some cases it's more convenient to count the index upward from zero:
<P><PRE>(define (<A NAME="g17"></A>list->vector lst)
(l->v-helper (make-vector (length lst)) lst 0))
(define (l->v-helper vec lst index)
(if (= index (vector-length vec))
vec
(begin (vector-set! vec index (car lst))
(l->v-helper vec (cdr lst) (+ index 1)))))
</PRE>
<P>Since lists are naturally processed from left to right (using
<CODE>car</CODE> and <CODE>cdr</CODE>), this program must process the vector from left to
right also.
<P><H2>Vectors versus Lists</H2>
<P>Since we introduced vectors to provide mutability, you may have the
impression that mutability is the main difference between vectors and
lists. Actually, lists are mutable too, although the issues are more
complicated; that's why we haven't used list mutation in this book.
<P>The most important difference between lists and vectors is that each
kind of aggregate lends itself to a different style of programming, because
some operations are faster than others in each. List programming is
characterized by two operations: dividing a list into its first element and
all the rest, and sticking one new element onto the front of a list. Vector
programming is characterized by selecting elements in any order, from a
collection whose size is set permanently when the vector is created.
<P>To make these rather vague descriptions more concrete, here are two
procedures, one of which squares every number in a list, and the other of
which squares every number in a vector:
<P><PRE>(define (list-square numbers)
(if (null? numbers)
'()
(cons (square (car numbers))
(list-square (cdr numbers)))))
(define (vector-square numbers)
(vec-sq-helper (make-vector (vector-length numbers))
numbers
(- (vector-length numbers) 1)))
(define (vec-sq-helper new old index)
(if (< index 0)
new
(begin (vector-set! new index (square (vector-ref old index)))
(vec-sq-helper new old (- index 1)))))
</PRE>
<P>In the list version, the intermediate stages of the algorithm
deal with lists that are smaller than the original argument. Each recursive
invocation "strips off" one element of its argument and "glues on" one
extra element in its return value. In the vector version, the returned
vector is created, at full size, as the first step in the algorithm; its
component parts are filled in as the program proceeds.
<P>This example can plausibly be done with either vectors or lists, so we've
used it to compare the two techniques. But some algorithms fit most
naturally with one kind of aggregate and would be awkward and slow using
the other kind. The swapping of pairs of elements in the shuffling
algorithm would be much harder using lists, while mergesort would be harder
using vectors.
<P>The best way to understand these differences in style is to know the
operations that are most efficient for each kind of aggregate. In each
case, there are certain operations that can be done in one small unit of
time, regardless of the number of elements in the aggregate, while other
operations take more time for more elements. The <EM>constant time</EM>
operations for lists are <CODE>cons</CODE>, <CODE>car</CODE>, <CODE>cdr</CODE>, and <CODE>null?</CODE>;
the ones for vectors are <CODE>vector-ref</CODE>, <CODE>vector-set!</CODE>, and <CODE>vector-length</CODE>.<A NAME="text5" HREF="vectors#ft5">[5]</A> And if you reread the
squaring programs, you'll find that these are precisely the operations
they use.
<P>We might have used <CODE>list-ref</CODE> in the list version, but we didn't, and
Scheme programmers usually don't, because we know that it would be slower.
Similarly, we could implement something like <CODE>cdr</CODE> for vectors, but that
would be slow, too, since it would have to make a one-smaller vector and
copy the elements one at a time. There are two possible morals to this
story, and they're both true: First, programmers invent and learn the
algorithms that make sense for whatever data structure is available. Thus
we have well-known programming patterns, such as the <CODE>filter</CODE> pattern,
appropriate for lists, and different patterns appropriate for vectors.
Second, programmers choose which data structure to use depending on what
algorithms they need. If you want to shuffle cards, use a vector, but if
you want to split the deck into a bunch of variable-size piles, lists might
be more appropriate. In general, vectors are good at selecting elements in
arbitrary order from a fixed-size collection; lists are good only at
selecting elements strictly from left to right, but they can vary in size.
<P>In this book, despite what we're saying here about efficiency, we've
generally tried to present algorithms in the way that's easiest to
understand, even when we know that there's a faster way. For example, we've
shown several recursive procedures in which the base case test was
<P><PRE>(= (count sent) 1)
</PRE>
<P>If we were writing the program for practical use, rather than for
a book, we would have written
<P><PRE>(empty? (butfirst sent))
</PRE>
<P>because we know that <CODE>empty?</CODE> and <CODE>butfirst</CODE> are both
constant time operations (because for sentences they're implemented as
<CODE>null?</CODE> and <CODE>cdr</CODE>), while <CODE>count</CODE> takes a long time for large
sentences. But the version using <CODE>count</CODE> makes the intent
clearer.<A NAME="text6" HREF="vectors#ft6">[6]</A>
<P><H2>State, Sequence, and Effects</H2>
<P>Effects, sequence, and state are three sides of the same
coin.<A NAME="text7" HREF="vectors#ft7">[7]</A>
<P>In Chapter 20 we explained the connection between effect (printing
something on the screen) and sequence: It matters what you print first.
We also noted that there's no benefit to a sequence of expressions unless
those expressions produce an effect, since the values returned by all but
the last expression are discarded.
<P>In this chapter we've seen another connection. The way our vector programs
maintain state information is by carrying out effects, namely, <CODE>vector-set!</CODE> invocations. Actually, <EM>every</EM> effect changes some kind
of state; if not in Scheme's memory, then on the computer screen or in a
file.
<P>The final connection to be made is between state and sequence. Once a
program maintains state, it matters whether some computation is carried out
before or after another computation that changes the state. The example at
the beginning of this chapter in which an expression had different results
before and after defining a variable illustrates this point. As another
example, if we evaluate <CODE>(lap 1)</CODE> 200 times and <CODE>(lap 2)</CODE> 200 times,
the program's determination of the winner of the race depends on whether the
last evaluation of <CODE>(lap 1)</CODE> comes before or after the last invocation
of <CODE>(lap 2)</CODE>.
<P>Because these three ideas are so closely connected, the names <EM>sequential programming</EM> (emphasizing sequence) and <EM><A NAME="g18"></A><A NAME="g19"></A>imperative programming</EM> (emphasizing effect) are both used to
refer to a style of programming that uses all three. This style is in
contrast with functional programming, which, as you know, uses none of them.
<P>Although functional and sequential programming are, in a sense, opposites,
it's perfectly possible to use both styles within one program, as we pointed
out in the tic-tac-toe program of Chapter 20. We'll show more such hybrid
programs in the following chapters.
<P><H2>Pitfalls</H2>
<P>Don't forget that the first element of a vector is number zero, and
there is no element whose index number is equal to the length of the
vector. (Although these points are equally true for lists, it doesn't often
matter, because we rarely select the elements of a list by number.) In
particular, in a vector recursion, if zero is the base case, then there's
probably still one element left to process.
<P>Try the following experiment:
<P><PRE>> (define dessert (vector 'chocolate 'sundae))
> (define two-desserts (list dessert dessert))
> (vector-set! (car two-desserts) 1 'shake)
> two-desserts
(#(CHOCOLATE SHAKE) #(CHOCOLATE SHAKE))
</PRE>
<P>You might have expected that after asking to change one word in
<CODE>two-desserts</CODE>, the result would be
<P><PRE>(#(CHOCOLATE SHAKE) #(CHOCOLATE SUNDAE))
</PRE>
<P>However, because of the way we created <CODE>two-desserts</CODE>, both of
its elements are the <EM>same</EM> vector. If you think of a list as a
collection of things, it's strange to imagine the very same thing in two
different places, but that's the situation. If you want to have two separate
vectors that happen to have the same values in their elements, but are
individually mutable, you'd have to say
<P><PRE>> (define two-desserts (list (vector 'chocolate 'sundae)
(vector 'chocolate 'sundae)))
> (vector-set! (car two-desserts) 1 'shake)
> two-desserts
(#(CHOCOLATE SHAKE) #(CHOCOLATE SUNDAE))
</PRE>
<P>Each invocation of <CODE>vector</CODE> or <CODE>make-vector</CODE> creates a
new, independent vector.
<P><H2>Exercises</H2>
<P>
<P><EM>Do not solve any of the following exercises by converting a
vector to a list, using list procedures, and then converting the result back
to a vector.</EM>
<P><B>23.1</B> Write a procedure <CODE><A NAME="g20"></A>sum-vector</CODE> that takes a vector full of
numbers as its argument and returns the sum of all the numbers:
<P><PRE>> (sum-vector '#(6 7 8))
21
</PRE>
<P>
<B>23.2</B> Some versions of Scheme provide a procedure <A NAME="g21"></A><CODE>vector-fill!</CODE> that takes a
vector and anything as its two arguments. It replaces every element of the
vector with the second argument, like this:
<P><PRE>> (define vec (vector 'one 'two 'three 'four))
> vec
#(one two three four)
> (<A NAME="g22"></A>vector-fill! vec 'yeah)
> vec
#(yeah yeah yeah yeah)
</PRE>
<P>Write <CODE>vector-fill!</CODE>. (It doesn't matter what value it
returns.)
<P>
<B>23.3</B> Write a function <CODE><A NAME="g23"></A>vector-append</CODE> that works just like regular <CODE>append</CODE>, but for vectors:
<P><PRE>> (vector-append '#(not a) '#(second time))
#(not a second time)
</PRE>
<P>
<B>23.4</B> Write <CODE>vector->list</CODE>.
<P>
<B>23.5</B> Write a procedure <CODE><A NAME="g24"></A>vector-map</CODE> that takes two arguments, a
function and a vector, and returns a new vector in which each box contains
the result of applying the function to the corresponding element of the
argument vector.
<P>
<B>23.6</B> Write a procedure <CODE><A NAME="g25"></A>vector-map!</CODE> that takes two arguments, a
function and a vector, and modifies the argument vector by replacing each
element with the result of applying the function to that element. Your
procedure should return the same vector.
<P>
<B>23.7</B> Could you write <CODE>vector-filter</CODE>? How about <CODE>vector-filter!</CODE>?
Explain the issues involved.
<P>
<B>23.8</B> Modify the <CODE>lap</CODE> procedure to print "Car 34 wins!" when car 34
completes its 200th lap. (A harder but more correct modification is
to print the message only if no other car has completed 200 laps.)
<P>
<B>23.9</B> <A NAME="itstrivial"></A>
Write a procedure <CODE><A NAME="g26"></A>leader</CODE> that says which car is in the lead
right now.
<P>
<B>23.10</B> Why doesn't this solution to Exercise <A HREF="vectors.html#itstrivial">23.9</A> work?
<P><PRE>(define (leader)
(leader-helper 0 1))
(define (leader-helper leader index)
(cond ((= index 100) leader)
((> (lap index) (lap leader))
(leader-helper index (+ index 1)))
(else (leader-helper leader (+ index 1)))))
</PRE>
<P>
<B>23.11</B> In some restaurants, the servers use computer terminals to keep track of
what each table has ordered. Every time you order more food, the server
enters your order into the computer. When you're ready for the check, the
computer prints your bill.
<P>You're going to write two procedures, <CODE><A NAME="g27"></A>order</CODE> and <CODE><A NAME="g28"></A>bill.</CODE> <CODE>Order</CODE> takes a table number and an item as arguments and
adds the cost of that item to that table's bill. <CODE>Bill</CODE> takes a table
number as its argument, returns the amount owed by that table, and resets
the table for the next customers. (Your <CODE>order</CODE> procedure can examine a
global variable <CODE>*menu*</CODE> to find the price of each item.)
<P><PRE>> (order 3 'potstickers)
> (order 3 'wor-won-ton)
> (order 5 'egg-rolls)
> (order 3 'shin-shin-special-prawns)
> (bill 3)
13.85
> (bill 5)
2.75
</PRE>
<P>
<B>23.12</B> Rewrite selection sort (from Chapter 15) to sort a vector. This can
be done in a way similar to the procedure for shuffling a deck: Find
the smallest element of the vector and exchange it (using <CODE>vector-swap!</CODE>) with the value in the first box. Then find the smallest
element not including the first box, and exchange that with the second box,
and so on. For example, suppose we have a vector of numbers:
<P><PRE>#(23 4 18 7 95 60)
</PRE>
<P>Your program should transform the vector through these
intermediate stages:
<P><PRE>#(4 23 18 7 95 60) ; exchange 4 with 23
#(4 7 18 23 95 60) ; exchange 7 with 23
#(4 7 18 23 95 60) ; exchange 18 with itself
#(4 7 18 23 95 60) ; exchange 23 with itself
#(4 7 18 23 60 95) ; exchange 60 with 95
</PRE>
<P>
<B>23.13</B> Why doesn't this work?
<P><PRE>(define (vector-swap! vector index1 index2)
(vector-set! vector index1 (vector-ref vector index2))
(vector-set! vector index2 (vector-ref vector index1)))
</PRE>
<P>
<B>23.14</B> Implement a two-dimensional version of vectors. (We'll call one of these
structures a <EM>matrix.</EM>) The implementation will use a vector of
vectors. For example, a three-by-five matrix will be a three-element
vector, in which each of the elements is a five-element vector. Here's
how it should work:
<A NAME="twodimvect"></A>
<P><PRE>> (define m (make-matrix 3 5))
> (matrix-set! m 2 1 '(her majesty))
> (matrix-ref m 2 1)
(HER MAJESTY)
</PRE>
<P>
<B>23.15</B> Generalize Exercise <A HREF="vectors.html#twodimvect">23.14</A> by implementing an <EM>array</EM>
structure that can have any number of dimensions. Instead of taking two
numbers as index arguments, as the matrix procedures do, the array
procedures will take one argument, a <EM>list</EM> of numbers. The number of
numbers is the number of dimensions, and it will be constant for any particular
array. For example, here is a three-dimensional array (4×5×6):
<A NAME="arrays"></A>
<P><PRE>> (define a1 (make-array '(4 5 6)))
> (array-set! a1 '(3 2 3) '(the end))
</PRE>
<P>
<B>23.16</B> We want to reimplement sentences as vectors instead of lists.
<P>(a) Write versions of <CODE>sentence</CODE>, <CODE>empty?</CODE>, <CODE>first</CODE>,
<CODE>butfirst</CODE>, <CODE>last</CODE>, and <CODE>butlast</CODE> that use vectors. Your
selectors need only work for sentences, not for words.
<P><PRE>> (sentence 'a 'b 'c)
#(A B C)
> (butfirst (sentence 'a 'b 'c))
#(B C)
</PRE>
<P>(You don't have to make these procedures work on lists as well as
vectors!)
<P>(b) Does the following program still work with the new
implementation of sentences? If not, fix the program.
<P><PRE>(define (praise stuff)
(sentence stuff '(is good)))
</PRE>
<P>(c) Does the following program still work with the new
implementation of sentences? If not, fix the program.
<P><PRE>(define (praise stuff)
(sentence stuff 'rules!))
</PRE>
<P>(d) Does the following program still work with the new
implementation of sentences? If not, fix the program. If so, is there some
optional rewriting that would improve its performance?
<P><PRE>(define (item n sent)
(if (= n 1)
(first sent)
(item (- n 1) (butfirst sent))))
</PRE>
<P>
<P>(e) Does the following program still work with the new
implementation of sentences? If not, fix the program. If so, is there some
optional rewriting that would improve its performance?
<P><PRE>(define (every fn sent)
(if (empty? sent)
sent
(sentence (fn (first sent))
(every fn (butfirst sent)))))
</PRE>
<P>(f) In what ways does using vectors to implement sentences affect
the speed of the selectors and constructor? Why do you think we chose to
use lists?
<P>
<HR>
<A NAME="ft1" HREF="vectors#text1">[1]</A> The Scheme standard says that the initial contents of the
boxes is "unspecified." That means that the result depends on the
particular version of Scheme you're using. It's a bad idea to try to
examine the contents of a box before putting something in it.<P>
<A NAME="ft2" HREF="vectors#text2">[2]</A> In some versions of Scheme, <CODE>make-vector</CODE> can take an
optional argument specifying an initial value to put in every box. In those
versions, we could just say
<P><PRE>(define *lap-vector* (make-vector 100 0))
</PRE>
<P>without having to use the initialization procedure.<P>
<A NAME="ft3" HREF="vectors#text3">[3]</A> That's what we mean by "non-functional," not that it doesn't
work!<P>
<A NAME="ft4" HREF="vectors#text4">[4]</A> We could get around
this problem in a different way:
<P><PRE>(define (card-list)
(every (lambda (suit) (every (lambda (rank) (word suit rank))
'(a 2 3 4 5 6 7 8 9 10 j q k)))
'(h s d c)))
</PRE>
<P>In this version, we're taking advantage of the fact that our
sentence data type was defined in a way that prevents the creation of
sublists. A sentence of cards is a good representation for the deck.
However, with this approach we are mixing up the list and sentence data
types, because later we're going to invoke <CODE>list->vector</CODE> with this deck
of cards as its argument. If we use sentence tools such as <CODE>every</CODE> to
create the deck, then the procedure <CODE>card-list</CODE> should really be called
<CODE>card-sentence</CODE>.
<P>What difference does it make? The <CODE>every</CODE> version works fine, as long
as sentences are implemented as lists, so that <CODE>list->vector</CODE> can be
applied to a sentence. But the point about abstract data types such as
sentences is to avoid making assumptions about their implementation. If
for some reason we decided to change the internal representation of
sentences, then <CODE>list->vector</CODE> could no longer be applied to a sentence.
Strictly speaking, if we're going to use this trick, we need a separate
conversion procedure <CODE>sentence->vector</CODE>.
<P>Of course, if you don't mind a little typing, you can avoid this whole issue
by having a quoted list of all 52 cards built into the definition of <CODE>card-list</CODE>.
<P>
<A NAME="ft5" HREF="vectors#text5">[5]</A> Where did this information come from? Just take our
word for it. In later courses you'll study how vectors and lists are
implemented, and then there will be reasons.<P>
<A NAME="ft6" HREF="vectors#text6">[6]</A> For words, it turns out, the <CODE>count</CODE> version is faster,
because words behave more like vectors than like lists.<P>
<A NAME="ft7" HREF="vectors#text7">[7]</A> … to coin a phrase.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="../ssch22/files.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch24/spread.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|