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
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
|
<P>
<P><A NAME="plowshares"></A>
<CENTER><IMG SRC="../ss-pics/plowshare.jpg" ALT="figure: plowshare"></CENTER><P><CENTER>Turning function machines into plowshares
</CENTER><P>
<HTML>
<HEAD>
<TITLE>Simply Scheme: Introducing Computer Science ch 8: Higher-Order Functions</TITLE>
</HEAD>
<BODY>
<HR>
<CITE>Simply Scheme:</CITE>
<CITE>Introducing Computer Science</CITE> 2/e Copyright (C) 1999 MIT
<H2>Chapter 8</H2>
<H1>Higher-Order Functions</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/ssch08.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="part3.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch9/lambda.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><EM>Note: If you read Part IV before this one, pretend you didn't; we are
going to develop a different technique for solving similar problems.</EM>
<P>
You can use the function <CODE>first</CODE> to find the first letter
of a word. What if you want to find the first letters of several words? You
did this in the first chapter, as part of the process of finding acronyms.
<P>
To start with a simple case, suppose you have two words (that is, a sentence
of length two). You could apply the <CODE>first</CODE> procedure to each of them and
combine the results:
<PRE>(define (<A NAME="g1"></A>two-firsts sent)
(se (first (first sent))
(first (last sent))))
> (two-firsts '(john lennon))
(J L)
> (two-firsts '(george harrison))
(G H)
</PRE>
Similarly, here's the version for three words:
<PRE>(define (<A NAME="g2"></A>three-firsts sent)
(se (first (first sent))
(first (first (bf sent)))
(first (last sent))))
> (three-firsts '(james paul mccartney))
(J P M)
</PRE>
But this approach would get tiresome if you had a sentence of five
words—you'd have to write a procedure specifically for the case of exactly
five words, and that procedure would have five separate subexpressions to
extract the first word, the second word, and so on. Also, you don't
want a separate procedure for every sentence length; you want one function
that works no matter how long the sentence is. Using the tools you've
already learned about, the only possible way to do that would be pretty
hideous:
<P><PRE>(define (first-letters sent)
(cond ((= (count sent) 1) (one-first sent))
((= (count sent) 2) (two-firsts sent))
((= (count sent) 3) (three-firsts sent))
… and so on …))
</PRE>
<P>
<P>But even this won't work because there's no way to say
"and so on" in Scheme. You could write a version that works for all
sentences up to, let's say, length 23, but you'd be in trouble if someone
tried to use your procedure on a 24-word sentence.
<P><H2><CODE><B>Every</B></CODE></H2>
<A NAME="every"></A>
<A NAME="g3"></A>
To write a better any-length first-letter procedure, you need to be able to say
"apply the function <CODE>first</CODE> to <EM>every</EM> word in the sentence, no
matter how long the sentence is." Scheme provides a way to do
this:<A NAME="text1" HREF="higher.html#ft1">[1]</A>
<PRE>(define (<A NAME="g4"></A>first-letters sent)
(every first sent))
> (first-letters '(here comes the sun))
(H C T S)
> (first-letters '(lucy in the sky with diamonds))
(L I T S W D)
</PRE>
<CODE>Every</CODE> takes two arguments. The second argument is a sentence, but the
first is something new: a <EM>procedure</EM> used as an
<A NAME="g5"></A>
<A NAME="g6"></A>
<A NAME="g7"></A>
<A NAME="g8"></A>
argument to another procedure.<A NAME="text2" HREF="higher.html#ft2">[2]</A> Notice that there are no parentheses around the word <CODE>first</CODE>
in the body of <CODE>first-letters</CODE>! By now you've gotten accustomed to
seeing parentheses whenever you see the name of a function. But parentheses
indicate an <EM>invocation</EM> of a function, and we aren't invoking <CODE>first</CODE> here. We're using <CODE>first</CODE>, the procedure itself, as an argument
to <CODE>every</CODE>.
<P><PRE>> (every last '(while my guitar gently weeps))
(E Y R Y S)
> (every - '(4 5 7 8 9))
(-4 -5 -7 -8 -9)
</PRE>
These examples use <CODE>every</CODE> with primitive procedures, but of
course you can also define procedures of your own and apply them to <CODE>every</CODE>
word of a sentence:
<PRE>(define (<A NAME="g9"></A>plural noun)
(if (equal? (last noun) 'y)
(word (bl noun) 'ies)
(word noun 's)))
> (every plural '(beatle turtle holly kink zombie))
(BEATLES TURTLES HOLLIES KINKS ZOMBIES)
</PRE>
<P>You can also use a word as the second argument to <CODE>every</CODE>. In this case,
the first-argument procedure is applied to every letter of the word. The
results are collected in a sentence.
<P><PRE>(define (<A NAME="g10"></A>double letter) (word letter letter))
> (every double 'girl)
(GG II RR LL)
> (every square 547)
(25 16 49)
</PRE>
<P>In all these examples so far, the first argument to <CODE>every</CODE> was a
function that returned a <EM>word,</EM> and the value returned by <CODE>every</CODE>
was a sentence containing all the returned words.
The first argument to <CODE>every</CODE> can also be a function that returns a
<EM>sentence.</EM> In this case, <CODE>every</CODE> returns one long sentence:
<P><PRE>(define (<A NAME="g11"></A>sent-of-first-two wd)
(se (first wd) (first (bf wd))))
> (every sent-of-first-two '(the inner light))
(T H I N L I)
> (every sent-of-first-two '(tell me what you see))
(T E M E W H Y O S E)
> (define (g wd)
(se (word 'with wd) 'you))
> (every g '(in out))
(WITHIN YOU WITHOUT YOU)
</PRE>
<P>A function that takes another function as one of its arguments, as
<CODE>every</CODE> does, is called a <EM><A NAME="g12"></A><A NAME="g13"></A>higher-order function.</EM>
If we focus our attention on procedures, the mechanism through which
Scheme computes functions, we think of <CODE>every</CODE> as a procedure
that takes another procedure as an argument—a <EM>higher-order
procedure.</EM>
<P><H2>A Pause for Reflection</H2>
<P>Earlier we used the metaphor of the "<A NAME="g14"></A><A NAME="g15"></A>function machine," with a
hopper at the top into which we throw data, and a chute at the
bottom from which the result falls, like a meat grinder. Well,
<CODE>every</CODE> is a function machine into whose hopper we throw <EM>another
function machine!</EM> Instead of a meat grinder, we have a metal
grinder.<A NAME="text3" HREF="higher.html#ft3">[3]</A>
<P>Do you see what an exciting idea this is? We are accustomed to
thinking of numbers and sentences as "real things," while functions
are less like things and more like activities. As an analogy, think
about cooking. The real foods are the meats, vegetables, ice cream,
and so on. You can't eat a recipe, which is analogous to a
function. A recipe has to be applied to ingredients, and the result
of carrying out the recipe is an edible meal. It would seem weird
if a recipe used other recipes as ingredients: “Preheat the oven
to 350 and insert your <EM>Joy of Cooking.</EM>” But in Scheme we
can do just that.<A NAME="text4" HREF="higher.html#ft4">[4]</A>
<P>Cooking your cookbook is unusual, but the general principle isn't.
In some contexts we do treat recipes as things rather than as
algorithms. For example, people write recipes on cards and put them
into a recipe file box. Then they perform operations such as searching
for a particular recipe, sorting the recipes by category (main dish,
dessert, etc.), copying a recipe for a friend, and so on. The same
recipe is both a process (when we're cooking with it) and the object
of a process (when we're filing it).
<P><H2><CODE><B>Keep</B></CODE></H2>
<P>Once we have this idea, we can use functions of functions to provide many
different capabilities.
<A NAME="keep"></A>
<P>
For instance, the <A NAME="g16"></A><CODE>keep</CODE> function takes a predicate and a sentence as
arguments. It returns a sentence containing only the words of the argument
sentence for which the predicate is true.
<PRE>> (keep even? '(1 2 3 4 5))
(2 4)
> (define (<A NAME="g17"></A>ends-e? word) (equal? (last word) 'e))
> (keep ends-e? '(please put the salami above the blue elephant))
(PLEASE THE ABOVE THE BLUE)
> (keep number? '(1 after 909))
(1 909)
</PRE>
<P><CODE>Keep</CODE> will also accept a word as its second argument. In this case, it
applies the predicate to every letter of the word and returns another word:
<P><PRE>> (keep number? 'zonk23hey9)
239
> (define (<A NAME="g18"></A>vowel? letter) (member? letter '(a e i o u)))
> (keep vowel? 'piggies)
IIE
</PRE>
<P>When we used <CODE>every</CODE> to select the first letters of words
earlier, we found the first letters even of uninteresting words such
as "the." We're working toward an acronym procedure, and for that
purpose we'd like to be able to discard the boring words.
<PRE>(define (<A NAME="g19"></A>real-word? wd)
(not (member? wd '(a the an in of and for to with))))
> (keep real-word? '(lucy in the sky with diamonds))
(LUCY SKY DIAMONDS)
> (every first (keep real-word? '(lucy in the sky with diamonds)))
(L S D)
</PRE>
<P><H2><CODE><B>Accumulate</B></CODE></H2>
<A NAME="accum"></A>
<P>In <CODE>every</CODE> and <CODE>keep</CODE>, each element of the second argument
contributes <EM>independently</EM> to the overall result. That is, <CODE>every</CODE> and <CODE>keep</CODE> apply a procedure to a single element at a time. The
overall result is a collection of individual results, with no interaction
between elements of the argument. This doesn't let us say things like "Add
up all the numbers in a sentence," where the desired output is a function
of the entire argument sentence taken as a whole. We can do this with a
procedure named <A NAME="g20"></A><CODE>accumulate</CODE>. <CODE>Accumulate</CODE> takes a procedure and
a sentence as its arguments. It applies that procedure to two of the words
of the sentence. Then it applies the procedure
to the result we got back and another element of the sentence, and so on.
It ends when it's combined all the words of the sentence into a single result.
<P><PRE>> (accumulate + '(6 3 4 -5 7 8 9))
32
> (accumulate word '(a c l u))
ACLU
> (accumulate max '(128 32 134 136))
136
> (define (<A NAME="g21"></A>hyphenate word1 word2)
(word word1 '- word2))
> (accumulate hyphenate '(ob la di ob la da))
OB-LA-DI-OB-LA-DA
</PRE>
<P>(In all of our examples in this section, the second argument
contains at least two elements. In the "pitfalls" section at the end of
the chapter, we'll discuss what happens with smaller arguments.)
<P><CODE>Accumulate</CODE> can also take a word as its second argument, using the
letters as elements:
<P><PRE>> (accumulate + 781)
16
> (accumulate sentence 'colin)
(C O L I N)
</PRE>
<P>
<H2>Combining Higher-Order Functions</H2>
What if we want to add up all the numbers in a sentence but ignore the words
that aren't numbers? First we <CODE>keep</CODE> the numbers in the sentence, then
we <CODE>accumulate</CODE> the result with <CODE>+</CODE>. It's easier to say in Scheme:
<PRE>(define (<A NAME="g22"></A>add-numbers sent)
(accumulate + (keep number? sent)))
> (add-numbers '(4 calling birds 3 french hens 2 turtle doves))
9
> (add-numbers '(1 for the money 2 for the show 3 to get ready
and 4 to go))
10
</PRE>
<P>We also have enough tools to write a version of the <A NAME="g23"></A><CODE>count</CODE> procedure,
which finds the number of words in a sentence or the number of letters in a
word. First, we'll define a procedure <CODE>always-one</CODE> that returns 1 no
matter what its argument is. We'll <CODE>every always-one</CODE> over our argument
sentence,<A NAME="text5" HREF="higher.html#ft5">[5]</A> which will result in a sentence of as
many ones as there were words in the original sentence. Then we can use
<CODE>accumulate</CODE> with <CODE>+</CODE> to add up the ones. This is a slightly
roundabout approach; later we'll see a more natural way to find the <CODE>count</CODE> of a sentence.
<PRE>(define (<A NAME="g24"></A>always-one arg)
1)
(define (<A NAME="g25"></A>count sent)
(accumulate + (every always-one sent)))
> (count '(the continuing story of bungalow bill))
6
</PRE>
You can now understand the <CODE>acronym</CODE> procedure from Chapter 1:
<PRE>(define (<A NAME="g26"></A>acronym phrase)
(accumulate word (every first (keep real-word? phrase))))
> (acronym '(reduced instruction set computer))
RISC
> (acronym '(structure and interpretation of computer programs))
SICP
</PRE>
<A name="whichHOF">
<P><H2>Choosing the Right Tool</H2>
<P>So far you've seen three higher-order functions: <A NAME="g27"></A><CODE>every</CODE>,
<A NAME="g28"></A><CODE>keep</CODE>, and <A NAME="g29"></A><CODE>accumulate</CODE>. How do you decide which one to
use for a particular problem?
<P><CODE>Every</CODE> transforms each element of a word or sentence individually. The
result sentence usually contains as many elements as the
argument.<A NAME="text6" HREF="higher.html#ft6">[6]</A>
<P><CENTER><IMG SRC="../ss-pics/every.jpg" ALT="figure: every"></CENTER>
<P><CODE>Keep</CODE> selects certain elements of a word or sentence and discards the
others. The elements of the result are elements of the argument, without
transformation, but the result may be smaller than the original.
<P><CENTER><IMG SRC="../ss-pics/keep.jpg" ALT="figure: keep"></CENTER>
<P><CODE>Accumulate</CODE> transforms the entire word or sentence into a single result
by combining all of the elements in some way.
<P><CENTER><IMG SRC="../ss-pics/accumulate.jpg" ALT="figure: accumulate"></CENTER>
<P>These three pictures represent graphically the differences in the meanings
of <CODE>every</CODE>, <CODE>keep</CODE>, and <CODE>accumulate</CODE>. In the pictures, we're
applying these higher-order procedures to sentences, but don't forget that
we could have drawn similar pictures in which the higher-order procedures
process the letters of a word.
<P>Here's another way to compare these three higher-order functions:
<P><P>
<TABLE><THEAD><STRONG><TR><TH>function<TH>purpose<TH>first
argument is a …</STRONG>
<TBODY>
<TR><TD><CODE>every</CODE><TD>transform <TD>one-argument
<EM>transforming</EM> function
<TR><TD><CODE>keep</CODE><TD>select<TD>one-argument <EM>predicate</EM>
function
<TR><TD><CODE>accumulate</CODE> <TD>combine<TD>two-argument
<EM>combining</EM> function
</TABLE>
<P><P>
To help you understand these differences, we'll look at specific examples
using each of them, with each example followed by an equivalent computation
done without the higher-order procedure. Here is an example for <CODE>every</CODE>:
<P><PRE>> (every double 'girl)
(GG II RR LL)
> (se (double 'g)
(double 'i)
(double 'r)
(double 'l))
(GG II RR LL)
</PRE>
<P>
<P>You can, if you like, think of the first of these expressions
as abbreviating the second.
<P>
<P>An expression using <CODE>keep</CODE> can also be replaced with an expression that
performs the same computation without using <CODE>keep</CODE>. This time it's a
little messier:
<P>
<P><PRE>> (keep even? '(1 2 3 4 5))
(2 4)
> (se (if (even? 1) 1 '())
(if (even? 2) 2 '())
(if (even? 3) 3 '())
(if (even? 4) 4 '())
(if (even? 5) 5 '()))
(2 4)
</PRE>
<P>
Here's how an <CODE>accumulate</CODE> can be expressed the long way:
<P><PRE>> (accumulate word '(a c l u))
ACLU
> (word 'a (word 'c (word 'l 'u)))
ACLU
</PRE>
<P>(Of course <CODE>word</CODE> will accept any number of arguments, so we
could have computed the same result with all four letters as arguments to
the same invocation. But the version we've shown here indicates how
<CODE>accumulate</CODE> actually works; it combines the elements one by one.)
<P><H2>First-Class Functions and First-Class Sentences</H2>
<P>If Scheme (or any dialect of Lisp) is your first programming language,
having procedures that operate on entire sentences at once may not seem like
a big deal. But if you used to program in some lesser language, you're
probably accustomed to writing something like <CODE>first-letters</CODE> as a <EM>loop</EM> in which you have some variable named <CODE>I</CODE> and you carry out some
sequence of steps for <CODE>I=1</CODE>, <CODE>I=2</CODE>, and so on, until you get to <CODE>N</CODE>, the number of elements. The use of higher-order functions allows us to
express this problem all at once, rather than as a sequence of events. Once
you're accustomed to the Lisp way of thinking, you can tell yourself "just
take <CODE>every first</CODE> of the sentence," and that feels like a single step,
not a complicated task.
<P>Two aspects of Scheme combine to permit this mode of expression. One,
which we've mentioned earlier, is that sentences are first-class data.
You can use an entire sentence as an argument to a procedure. You can type a
quoted sentence in, or you can compute a sentence by putting words together.
<P>The second point is that functions are also first-class. This lets us write
a procedure like <CODE>pigl</CODE> that applies to a single word, and then
combine that with <CODE>every</CODE> to translate an entire sentence to Pig Latin.
If Scheme didn't have first-class functions, we couldn't have general-purpose
tools like <CODE>keep</CODE> and <CODE>every</CODE>, because we couldn't say which
function to extend to all of a sentence. You'll see later that without <CODE>every</CODE> it would still be possible to write a specific <CODE>pigl-sent</CODE>
procedure and separately write a <CODE>first-letters</CODE> procedure. But the
ability to use a procedure as argument to another procedure lets us <EM>generalize</EM> the idea of "apply this function to every word of the
sentence."
<P><H2><CODE><B>Repeated</B></CODE></H2>
<P>All the higher-order functions you've seen so far take functions as
arguments, but none of them have functions as return values. That is,
we have machines that can take machines in their input hoppers, but now
we'd like to think about machines that drop <EM>other machines</EM> out of
their output chutes—machine factories, so to speak.
<A NAME="repeated"></A>
<P>In the following example, the procedure <A NAME="g30"></A><CODE>repeated</CODE> returns a procedure:
<PRE>> ((repeated bf 3) '(she came in through the bathroom window))
(THROUGH THE BATHROOM WINDOW)
> ((repeated plural 4) 'computer)
COMPUTERSSSS
> ((repeated square 2) 3)
81
> (define (<A NAME="g31"></A>double sent)
(se sent sent))
> ((repeated double 3) '(banana))
(BANANA BANANA BANANA BANANA BANANA BANANA BANANA BANANA)
</PRE>
The procedure <CODE>repeated</CODE> takes two arguments, a procedure and a number,
and returns a new procedure. The returned procedure is one that invokes the
original procedure repeatedly. For example, <CODE>(repeated bf 3)</CODE>
returns a function that takes the butfirst of the butfirst of the
butfirst of its argument.
Notice that all our examples start with two open parentheses. If we just
invoked <CODE>repeated</CODE> at the Scheme prompt, we would get back a procedure,
like this:
<PRE>> (repeated square 4)
#<PROCEDURE>
</PRE>
The procedure that we get back isn't very interesting by itself, so
we invoke it, like this:
<PRE>> ((repeated square 4) 2)
65536
</PRE>
To understand this expression, you must think carefully about its
two subexpressions. Two subexpressions? Because there are two open
parentheses next to each other, it would be easy to ignore one of them and
therefore think of the expression as having four atomic subexpressions. But
in fact it has only two. The first subexpression, <CODE>(repeated square 4)</CODE>, has a procedure as its value. The second
subexpression, <CODE>2</CODE>, has a number as its value. The value of the entire
expression comes from applying the procedure to the number.
All along we've been saying that you evaluate a compound expression in two
steps: First, you evaluate all the subexpressions. Then you apply the
first value, which has to be a procedure, to the rest of the values. But
until now the first subexpression has always been just a single word, the
name of a procedure. Now we see that the first expression might be an
invocation of a higher-order function, just as any of the argument
subexpressions might be function invocations.
We can use <CODE>repeated</CODE> to define <A NAME="g32"></A><CODE>item</CODE>, which returns a particular
element of a sentence:
<PRE>(define (<A NAME="g33"></A>item n sent)
(first ((repeated bf (- n 1)) sent)))
> (item 1 '(a day in the life))
A
> (item 4 '(a day in the life))
THE
</PRE>
<P><H2>Pitfalls</H2>
<P>Some people seem to fall in love with <CODE>every</CODE> and try to use it in
all problems, even when <CODE>keep</CODE> or <CODE>accumulate</CODE> would be more
appropriate.
<P>If you find yourself using a predicate function as the first argument to
<CODE>every</CODE>, you almost certainly mean to use <CODE>keep</CODE> instead. For
example, we want to write a procedure that determines whether any of the
words in its argument sentence are numbers:
<P><PRE>(define (any-numbers? sent) ;; wrong!
(accumulate or (every number? sent)))
</PRE>
<P>This is wrong for two reasons. First, since Boolean values aren't words,
they can't be members of sentences:
<P><PRE>> (sentence #T #F)
ERROR: ARGUMENT TO SENTENCE NOT A WORD OR SENTENCE: #F
> (every number? '(a b 2 c 6))
ERROR: ARGUMENT TO SENTENCE NOT A WORD OR SENTENCE: #T
</PRE>
<P>Second, even if you could have a sentence of Booleans, Scheme doesn't allow
a special form, such as <CODE>or</CODE>, as the argument to a higher-order
function.<A NAME="text7" HREF="higher.html#ft7">[7]</A> Depending on your version of Scheme,
the incorrect <CODE>any-numbers?</CODE> procedure might give an error message about
either of these two problems.
<P>Instead of using <CODE>every</CODE>, select the numbers from the argument and count
them:
<P><PRE>(define (<A NAME="g34"></A>any-numbers? sent)
(not (empty? (keep number? sent))))
</PRE>
<P>The <CODE>keep</CODE> function always returns a result of the same type (i.e.,
word or sentence) as its second argument. This makes sense because if you're
selecting a subset of the words of a sentence, you want to end up with a
sentence; but if you're selecting a subset of the letters of a word, you
want a word. <CODE>Every</CODE>, on the other hand, always returns a sentence.
You might think that it would make more sense for <CODE>every</CODE> to return a
word when its second argument is a word. Sometimes that <EM>is</EM> what you
want, but sometimes not. For example:
<P><A NAME="spelldigit"></A>
<PRE>(define (<A NAME="g35"></A>spell-digit digit)
(item (+ 1 digit)
'(zero one two three four five six seven eight nine)))
> (every spell-digit 1971)
(ONE NINE SEVEN ONE)
</PRE>
<P>In the cases where you do want a word, you can just <CODE>accumulate word</CODE> the sentence that <CODE>every</CODE> returns.
<P>
<P>Remember that <CODE>every</CODE> expects its first argument to be a function of
just one argument. If you invoke <CODE>every</CODE> with a function such as <CODE>quotient</CODE>, which expects two arguments, you will get an error message from
<CODE>quotient</CODE>, complaining that it only got one argument and wanted to get
two.
<P>Some people try to get around this by saying things like
<P><PRE>(every (quotient 6) '(1 2 3)) ;; wrong!
</PRE>
<P>This is a sort of wishful thinking. The intent is that Scheme
should interpret the first argument to <CODE>every</CODE> as a fill-in-the-blank
template, so that <CODE>every</CODE> will compute the values of
<P><PRE>(quotient 6 1)
(quotient 6 2)
(quotient 6 3)
</PRE>
<P>But of course what Scheme really does is the same thing it always
does: It evaluates the argument expressions, then invokes <CODE>every</CODE>. So
Scheme will try to compute <CODE>(quotient 6)</CODE> and will give an error message.
<P>We picked <CODE>quotient</CODE> for this example because it requires exactly two
arguments. Many Scheme primitives that ordinarily take two arguments,
however, will accept only one. Attempting the same wishful thinking with
one of these procedures is still wrong, but the error message is different.
For example, suppose you try to add 3 to each of several numbers this way:
<P><PRE>(every (+ 3) '(1 2 3)) ;; wrong!
</PRE>
<P>The first argument to <CODE>every</CODE> in this case isn't "the
procedure that adds 3," but the result returned by invoking <CODE>+</CODE> with
the single argument <CODE>3</CODE>. <CODE>(+ 3)</CODE> returns the number <CODE>3</CODE>, which
isn't a procedure. So you will get an error message like "Attempt to apply
non-procedure 3."
<P>The idea behind this mistake—looking for a way to "specialize" a
two-argument procedure by supplying one of the arguments in advance—is
actually a good one. In the next chapter we'll introduce a new mechanism
that does allow such specialization.
<P>If the procedure you use as the argument to <CODE>every</CODE> returns an empty
sentence, then you may be surprised by the results:
<P><PRE>(define (<A NAME="g36"></A>beatle-number n)
(if (or (< n 1) (> n 4))
'()
(item n '(john paul george ringo))))
> (beatle-number 3)
GEORGE
> (beatle-number 5)
()
> (every beatle-number '(2 8 4 0 1))
(PAUL RINGO JOHN)
</PRE>
<P>What happened to the <CODE>8</CODE> and the <CODE>0</CODE>? Pretend that <CODE>every</CODE> didn't exist, and you had to do it the hard way:
<P><PRE>(se (beatle-number 2) (beatle-number 8) (beatle-number 4)
(beatle-number 0) (beatle-number 1))
</PRE>
<P>Using result replacement, we would get
<P><PRE>(se 'paul '() 'ringo '() 'john)
</PRE>
<P>which is just <CODE>(PAUL RINGO JOHN)</CODE>.
<P>On the other hand, if <CODE>every</CODE>'s argument procedure returns an empty <EM>word,</EM> it will appear in the result.
<P><PRE>> (every bf '(i need you))
("" EED OU)
</PRE>
<P>The sentence returned by <CODE>every</CODE> has three words in it: the
empty word, <CODE>eed</CODE>, and <CODE>ou</CODE>.
<P>Don't confuse
<P><PRE>(first '(one two three four))
</PRE>
<P>with
<P><PRE>(every first '(one two three four))
</PRE>
<P>In the first case, we're applying the procedure <CODE>first</CODE> to a
sentence; in the second, we're applying <CODE>first</CODE> four separate times,
to each of the four words separately.
<P>What happens if you use a one-word sentence or one-letter word as argument
to <CODE>accumulate</CODE>? It returns that word or that letter, without even
invoking the given procedure. This makes sense if you're using something
like <CODE>+</CODE> or <CODE>max</CODE> as the accumulator, but it's disconcerting that
<P><PRE>(accumulate se '(one-word))
</PRE>
<P>returns the <EM>word</EM> <CODE>one-word</CODE>.
<P>
What happens if you give <CODE>accumulate</CODE> an empty sentence or word?
<CODE>Accumulate</CODE> accepts empty arguments for some combiners, but not for
others:
<P><PRE>> (accumulate + '())
0
> (accumulate max '())
ERROR: CAN'T ACCUMULATE EMPTY INPUT WITH THAT COMBINER
</PRE>
<P>The combiners that can be used with an empty sentence or word are
<CODE>+</CODE>, <CODE>*</CODE>, <CODE>word</CODE>, and <CODE>sentence</CODE>. <CODE>Accumulate</CODE> checks
specifically for one of these combiners.
<P>Why should these four procedures, and no others, be allowed to <CODE>accumulate</CODE> an empty sentence or word? The difference between these and
other combiners is that you can invoke them with no arguments, whereas <CODE>max</CODE>, for example, requires at least one number:
<P><PRE>> (+)
0
> (max)
ERROR: NOT ENOUGH ARGUMENTS TO #<PROCEDURE>.
</PRE>
<P><CODE>Accumulate</CODE> actually invokes the combiner with no arguments
in order to find out what value to return for an empty sentence or word.
We would have liked to implement <CODE>accumulate</CODE> so that <EM>any</EM>
procedure that can be invoked with no arguments would be accepted as a
combiner to accumulate the empty sentence or word. Unfortunately, Scheme
does not provide a way for a program to ask, "How many arguments will this
procedure accept?" The best we could do was to build a particular set of
zero-argument-okay combiners into the definition of <CODE>accumulate</CODE>.
<P>Don't think that the returned value for an empty argument is always zero or
empty.
<P><PRE>> (accumulate * '())
1
</PRE>
<P>The explanation for this behavior is that any function that works
with no arguments returns its <EM>identity element</EM> in that case.
What's an identity element? The function <CODE>+</CODE> has the identity element
<CODE>0</CODE> because <CODE>(+</CODE> <EM>anything</EM> <CODE>0)</CODE> returns the <EM>anything.</EM> Similarly, the empty word is the identity element for <CODE>word</CODE>. In general, a function's identity element has the property that when
you invoke the function with the identity element and something else as
arguments, the return value is the something else. It's a Scheme convention
that a procedure with an identity element returns that element when invoked
with no arguments.<A NAME="text8" HREF="higher.html#ft8">[8]</A>
<P>The use of two consecutive open parentheses to invoke the procedure
<A NAME="g37"></A>
returned by a procedure is a strange-looking notation:
<P><PRE>((repeated bf 3) 987654)
</PRE>
<P>Don't confuse this with the similar-looking <CODE>cond</CODE> notation,
in which the outer parentheses have a special meaning (delimiting a <CODE>cond</CODE> clause). Here, the parentheses have their usual meaning. The inner
parentheses invoke the procedure <CODE>repeated</CODE> with arguments <CODE>bf</CODE> and
<CODE>3</CODE>. The value of that expression is a procedure. It doesn't have a
name, but for the purposes of this paragraph let's pretend it's called <CODE>bfthree</CODE>. Then the outer parentheses are basically saying <CODE>(bfthree 987654)</CODE>; they apply the unnamed procedure to the argument <CODE>987654</CODE>.
<P>In other words, there are two sets of parentheses because there are two
functions being invoked: <CODE>repeated</CODE> and the function returned by
<CODE>repeated</CODE>. So don't say
<P><PRE>(repeated bf 3 987654) ;; wrong
</PRE>
<P>just because it looks more familiar. <CODE>Repeated</CODE> isn't a
function of three arguments.
<P><H2>Boring Exercises</H2>
<P><B>8.1</B> What does Scheme return as the value of each of the following expressions?
Figure it out for yourself before you try it on the computer.
<P><PRE>
> (every last '(algebra purple spaghetti tomato gnu))
> (keep number? '(one two three four))
> (accumulate * '(6 7 13 0 9 42 17))
> (member? 'h (keep vowel? '(t h r o a t)))
> (every square (keep even? '(87 4 7 12 0 5)))
> (accumulate word (keep vowel? (every first '(and i love her))))
> ((repeated square 0) 25)
> (every (repeated bl 2) '(good day sunshine))
</PRE>
<P><B>8.2</B> Fill in the blanks in the following Scheme interactions:
<P><PRE>> (______ vowel? 'birthday)
IA
> (______ first '(golden slumbers))
(G S)
> (______ '(golden slumbers))
GOLDEN
> (______ ______ '(little child))
(E D)
> (______ ______ (______ ______ '(little child)))
ED
> (______ + '(2 3 4 5))
(2 3 4 5)
> (______ + '(2 3 4 5))
14
</PRE>
<P>
<B>8.3</B> Describe each of the following functions in English. Make sure to include a
description of the domain and range of each function. Be as precise as
possible; for example, "the argument must be a function of one numeric
argument" is better than "the argument must be a function."
<P><PRE>(define (f a)
(keep even? a))
(define (g b)
(every b '(blue jay way)))
</PRE>
<P>
<PRE>(define (h c d)
(c (c d)))
(define (i e)
(/ (accumulate + e) (count e)))
accumulate
sqrt
repeated
(repeated sqrt 3)
(repeated even? 2)
(repeated first 2)
(repeated (repeated bf 3) 2)
</PRE>
<P>
<P>
<H2>Real Exercises</H2>
<P>
Note: Writing helper procedures may be useful in solving some of these
problems. <EM>If you read Part IV before this, do not use recursion
in solving these problems; use higher order functions instead.</EM>
<a name="hofex">
<P><B>8.4</B> Write a procedure <CODE><A NAME="g38"></A>choose-beatles</CODE> that takes a predicate
function as its argument and returns a sentence of just those Beatles (John,
Paul, George, and Ringo) that satisfy the predicate. For example:
<P><PRE>(define (<A NAME="g39"></A>ends-vowel? wd) (vowel? (last wd)))
(define (<A NAME="g40"></A>even-count? wd) (even? (count wd)))
> (choose-beatles ends-vowel?)
(GEORGE RINGO)
> (choose-beatles even-count?)
(JOHN PAUL GEORGE)
</PRE>
<P>
<P><B>8.5</B> Write a procedure <CODE><A NAME="g41"></A>transform-beatles</CODE> that takes a procedure as an
argument, applies it to each of the Beatles, and returns the results in a
sentence:
<P><PRE>(define (<A NAME="g42"></A>amazify name)
(word 'the-amazing- name))
</PRE>
<P>
<P><PRE>> (transform-beatles amazify)
(THE-AMAZING-JOHN THE-AMAZING-PAUL THE-AMAZING-GEORGE
THE-AMAZING-RINGO)
> (transform-beatles butfirst)
(OHN AUL EORGE INGO)
</PRE>
<P>
<B>8.6</B> When you're talking to someone over a noisy radio connection, you sometimes
have to spell out a word in order to get the other person to understand it.
But names of letters aren't that easy to understand either, so there's a
standard code in which each letter is represented by a particular word that
starts with the letter. For example, instead of "B" you say "bravo."
<P>Write a procedure <CODE><A NAME="g43"></A>words</CODE> that takes a word as its argument and
returns a sentence of the names of the letters in the word:
<P><PRE>> (words 'cab)
(CHARLIE ALPHA BRAVO)
</PRE>
<P>(You may make up your own names for the letters or look up the
standard ones if you want.)
<P>Hint: Start by writing a helper procedure that figures out the name for a
single letter.
<P>
<B>8.7</B> [<A HREF="../ssch14/recur-patterns.html#lettcrec">14.5</A>]<A NAME="text9" HREF="higher.html#ft9">[9]</A>
Write a procedure <CODE><A NAME="g44"></A>letter-count</CODE> that takes a sentence as its
argument and returns the total number of letters in the sentence:
<A NAME="lettcount"></A>
<P><PRE>> (letter-count '(fixing a hole))
11
</PRE>
<P>
<B>8.8</B> [<A HREF="../ssch12/leap.html#exaggrec">12.5</A>]
Write an <CODE><A NAME="g45"></A>exaggerate</CODE> procedure which exaggerates sentences:
<A NAME="exagg"></A>
<P><PRE>> (exaggerate '(i ate 3 potstickers))
(I ATE 6 POTSTICKERS)
> (exaggerate '(the chow fun is good here))
(THE CHOW FUN IS GREAT HERE)
</PRE>
<P>It should double all the numbers in the sentence, and it should replace
"good" with "great," "bad" with "terrible," and anything else you
can think of.
<P>
<B>8.9</B> What procedure can you use as the first argument to <CODE>every</CODE> so that for
any sentence used as the second argument, <CODE>every</CODE> returns that sentence?
<P>What procedure can you use as the first argument to <CODE>keep</CODE> so that for
any sentence used as the second argument, <CODE>keep</CODE> returns that sentence?
<P>What procedure can you use as the first argument to <CODE>accumulate</CODE> so that
for any sentence used as the second argument, <CODE>accumulate</CODE> returns that
sentence?
<P>
<B>8.10</B> Write a predicate <CODE><A NAME="g46"></A>true-for-all?</CODE> that takes two arguments, a
predicate procedure and a sentence. It should return <CODE>#t</CODE> if the
predicate argument returns true for <EM>every</EM> word in the sentence.
<A NAME="trueforall"></A>
<P><PRE>> (true-for-all? even? '(2 4 6 8))
#T
> (true-for-all? even? '(2 6 3 4))
#F
</PRE>
<P>
<B>8.11</B> [<A HREF="../ssch12/leap.html#gparec">12.6</A>]
Write a GPA procedure. It should take a sentence of grades as its argument
and return the corresponding grade point average:
<A NAME="gpa"></A>
<P><PRE>> (<A NAME="g47"></A>gpa '(A A+ B+ B))
3.67
</PRE>
<P>Hint: write a helper procedure <CODE><A NAME="g48"></A>base-grade</CODE> that takes
a grade as argument and returns 0, 1, 2, 3, or 4, and another helper
procedure <CODE>grade-modifier</CODE> that returns −.33, 0, or .33, depending on
whether the grade has a minus, a plus, or neither.
<P>
<B>8.12</B> [<A HREF="../ssch11/recursion.html#countumsrec">11.2</A>]
When you teach a class, people will get distracted if you say "um" too many
times. Write a <CODE><A NAME="g49"></A>count-ums</CODE> that counts the number of times "um"
appears in a sentence:
<A NAME="countums"></A>
<P><PRE>> (count-ums
'(today um we are going to um talk about functional um programming))
3
</PRE>
<P>
<B>8.13</B> [<A HREF="../ssch11/recursion.html#unspellrec">11.3</A>]
Write a procedure <CODE><A NAME="g50"></A>phone-unspell</CODE> that takes a spelled version of
a phone number, such as <CODE>POPCORN</CODE>, and returns the real phone number, in
this case <CODE>7672676</CODE>. You will need to write a helper procedure that
uses an 8-way <CODE>cond</CODE> expression to translate a single letter into a
digit.
<A NAME="unspell"></A>
<P>
<B>8.14</B> Write the procedure <CODE><A NAME="g51"></A>subword</CODE> that takes three arguments: a
word, a starting position number, and an ending position number. It should
return the subword containing only the letters between the specified
positions:
<P><PRE>> (subword 'polythene 5 8)
THEN
</PRE>
<P>
<HR>
<A NAME="ft1" HREF="higher.html#text1">[1]</A> Like all the procedures in this book that deal with words and
sentences, <CODE>every</CODE> and the other procedures in this chapter
are part of our extensions to Scheme. Later, in Chapter 17, we'll
introduce the standard Scheme equivalents.<P>
<A NAME="ft2" HREF="higher.html#text2">[2]</A> Talking about <CODE>every</CODE> strains our
resolve to distinguish functions from the procedures that implement them.
Is the argument to <CODE>every</CODE> a function or a procedure? If we think of
<CODE>every</CODE> itself as a procedure—that is, if we're focusing on how it
does its job—then of course we must say that it does its job by repeatedly
invoking the <EM>procedure</EM> that we supply as an argument. But it's
equally valid for us to focus attention on the function that the <CODE>every</CODE>
procedure implements, and that function takes <EM>functions</EM> as
arguments.<P>
<A NAME="ft3" HREF="higher.html#text3">[3]</A> You can get in trouble mathematically by trying to define a
function whose domain includes <EM>all</EM> functions, because applying such
a function to itself can lead to a paradox. In programming, the
corresponding danger is that applying a higher-order procedure to <EM>itself</EM> might result in a program that runs forever.<P>
<A NAME="ft4" HREF="higher.html#text4">[4]</A> Some recipes may seem to include other
recipes, because they say things like "add pesto (recipe on p.
12)." But this is just composition of functions; the <EM>result</EM>
of the pesto procedure is used as an argument to this recipe. The
pesto recipe itself is not an ingredient.<P>
<A NAME="ft5" HREF="higher.html#text5">[5]</A> We mean, of course, "We'll invoke <CODE>every</CODE> with the
procedure <CODE>always-one</CODE> and our argument sentence as its two arguments."
After you've been programming computers for a while, this sort of abuse of
English will come naturally to you.<P>
<A NAME="ft6" HREF="higher.html#text6">[6]</A> What we mean by "usually" is that <CODE>every</CODE> is most
often used with an argument function that returns a single word. If the
function returns a sentence whose length might not be one, then the number
of words in the overall result could be anything!<P>
<A NAME="ft7" HREF="higher.html#text7">[7]</A> As we said in Chapter 4, special forms aren't
procedures, and aren't first-class.<P>
<A NAME="ft8" HREF="higher.html#text8">[8]</A> PC Scheme returns zero for an invocation of <CODE>max</CODE> with no arguments, but that's the wrong answer. If anything, the
answer would have to be −∞.<P>
<A NAME="ft9" HREF="higher.html#text9">[9]</A> Exercise <A HREF="../ssch14/recur-patterns.html#lettcrec">14.5</A> in Part IV asks you to solve this
same problem using recursion. Here we are asking you to use
higher-order functions. Whenever we pose the same problem in both parts, we'll
cross-reference them in brackets as we did here. When you see the problem
for the second time, you might want to consult your first solution for ideas.<P>
<P><A HREF="../ss-toc2.html">(back to Table of Contents)</A><P>
<A HREF="part3.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../ssch9/lambda.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|