COMP 3007
Outline
Lectures
Assignments
Schedule
a3q1_compose.scm
∘
(define square (lambda(x)(* x x)))
(define double (lambda(x)(+ x x)))
((compose square double) 3) -> 6^2 = 36
(divisibleBy x)
(define mod3 (divisibleBy 3))
(mod3 7) -> #f
(mod3 9) -> #t
(newmap f)
f
(define double-mapper (newmap (lambda(x)(* x 2))))
(double-mapper ‘(1 2 3 4)) –> (2 4 6 8)
(double-mapper ‘(10 20 30)) –> (20 40 60)
(newfilter f)
∘
f
(compose f g)
f
f
.g.E .noitulos ruoy ni noitcnuf retlfi ni-tliub eht esu ton dluohs uoY . gnisu tsil eht retlfi dna tnemugra sa tsil a ekat dluohs noitcnuf denruter tahT .noitcnuf a snruter dna
tnemugra sa noitcnuf a sekat taht dellac noitcnuf a enfieD ]skram 3[ .d
noitcnuf pam ni-tliub eht esu ton dluohs uoY .tsil eht fo tnemele hcae revo noitcnuf eht pam dna tnemugra sa tsil a ekat dluohs noitcnuf denruter ehT .noitcnuf a snruter
dna tnemugra sa noitcnuf a sekat taht dellac noitcnuf a enfieD ]skram 3[ .c
:.g.E .esiwrehto eslaf ,x yb elbisivid ylneve si y fi eurt nruter dna y regetni na tpecca dluohs etaciderp denruter ehT .noitcnuf etaciderp a
snruter dna tnemugra regetni na sekat taht noitcnuf a enfieD ]kram 1[ .b
.nwohs sa skrow egasu gniwollof eht taht hcus ,g f noitcnuf desopmoc a snruter taht noitcnuf a enfieD ]skram 2[ .))x(g(f = )x(h taht hcus h noitcnuf a
snruter dna g dna f snoitcnuf owt sekat taht noitarepo na si g f noitisopmoc noitcnuF .a :smelborp gniwollof eht evlos , dellac elfi a nI
1 noitseuQ mp 00:55:11 @ ht41 hcraM yadnuS :euD
smaertS & ,stsiL ,noitcartsbA ataD
3# tnemngissA – 7003 PMOC
.g.E .noitulos ruoy ni
7003 PMOC EMOH
(define evens-filter (newfilter (divisibleBy 2)))
range
myfunc
(define myfunc )
(myfunc (range 1 20))
a3q2_lists.scm
(16 64 144 256 400)
(repeat x n) xnx
(repeat ‘a 5) (a a a a a)
(alternate list1 list2)
n
(alternate ‘(0 0 0 0) ‘(1 1 1 1 1 1))
(count x L)
(count 3 ‘(1 4 3 6 2 3 3 1 4 3 5 7))
(count ‘b ‘(4 b a 3 2 c b 1 b 2 d a))
(mode L)
(0 1 0 1 0 1 0 1 1 1)
4 3
(mode ‘(a b a c a d d a b c a b))
(mode ‘(2 b a 3 2 c b 1 b 2 d a))
(decreasing L)
(decreasing ‘(3 6 8 9 7 4 8 6
(decreasing ‘(7 6 5 4 8 5 2 5
(decreasing ‘(1 2 3 3 3 4 5))
a 2
max min
((9 7 4) (7 4) (8 6 3) (6 3))
3))
1 5 2 1)) ((7 6 5 4) (6 5 4) (5 4) (8 5 2)
()
a3q3_trees.scm
tree-reduce reduce
laitini na ,rotarepo na ekat dluohs noitcnuf sihT .)2.4 noitceS ees( stsil tafl rof noitcnuf eht ot suogolana si taht seert rof dellac noitcnuf a etirW ]skram 3[ .a
eht fo secnatsni fo rebmun eht snruter taht →
erudecorp a etaerC ]skram 3[ .c
:smelborp gniwollof eht evlos ,
dellac elfi a nI 3 noitseuQ
→
→ →
)… 1+in in …( srebmun erom ro owt fo ecneuqes a si ecneuqesbus gnisaerced a :etoN .tsil tupni eht ni secneuqesbus gnisaerced evitucesnoc eht fo lla fo tsil a snruter
dna tupni sa srebmun fo tsil a sekat taht erudecorp a etaerC ]skram 6[ .e
→ →
,.g.E .melborp siht rof snoitcnuf ro ni-tliub eht esu ton yam uoY .)deretnuocne eno tsrfi eht ei( tsil eht fo tnorf eht ot tsesolc eulav eht nruter eit a fo esac eht nI .L
tsil eht ni eulav nommoc tsom eht snruter taht
erudecorp a etaerC ]skram 4[ .d
→ →
:.g.E .redro dedivorp eht ni stsil tupni htob morf stnemele lla niatnoc dluohs tluser ehT .stsil tupni nevig owt eht morf stnemele
gnitanretla yb tsil a setaerc taht noitcnuf a etaerC ]skram 3[ .b →
fo seipoc
sniatnoc taht tsil a snruter taht noitcnuf a etaerC ]skram 2[ .a :smelborp gniwollof eht evlos , dellac elfi a nI
:.g.E .eulav yna si dna ,regetni evitagen-non emos si erehW . eulav eht
.nwohs sa stluser detcepxe eht secudorp noitcnuf eht fo noitinfied eht taht os woleb tnemetats eht no ) ( knalb eht ni llfi ,)erutcel
morf noitcnuf eht nevig dna( evoba detaerc uoy snoitcnuf eht gnisU ]skram 2[ .e
→
,.g.E .1+in > in taht hcus
:.g.E .L tsil eht ni x eulav
2 noitseuQ
(tree-reduce + 0 ‘(1 (2 3)((4 5) 6 (7)((8 (9)) 10)))
height
55
(height ‘a) 0
(height ‘(a))
(height ‘(a (b) c)) 2
(height ‘(((((a(((b))))))))) 8
flatten-tree
1
(flatten-tree ‘(1 (2 3) ((4 5 6 (7)))(((8 (9))))))
(tree-merge T1 T2)
(1 2 3 4 5 6 7 8 9)
car
max
.eertbus ytpme-non eht ylpmis si ,eert ytpme na htiw eertbus a gnigreM .fael eht fo eulav eht yb eertbus eht gnilacs yb enod si eertbus a htiw edon fael a gnigreM .)srebmun era yeht emussa yam uoy( seulav rieht gniylpitlum yb enod si sedon fael owt gnigreM
… ,cte ,cte ,cte …dnoces htiw dnoceS 2T fo dlihc tsrfi eht htiw degrem si 1T fo dlihc tsrfi ehT 2T fo toor eht htiw degrem si 1T fo toor ehT
.seertbus rieht gnigrem dna erutcurts rieht hguorht gnisrucer yb enod si seert owt gnigreM
:selur gniwollof eht ot gnidrocca meht segrem dna stnemugra sa seert owt sekat taht noitcnuf a etirW ]skram 6[ .d
→
:.g.E .redro evitaler lanigiro rieht ni eert eht fo seulav lanimret eht fo tsil detsen-non a
snruter dna tnemugra na sa eert a sekat taht noitcnuf a etirW ]skram 3[ .c
.)siht rof noitcnuf
→
→
:.g.E ni-tliub eht esu ot hsiw yam uoY( …wor a ni ylirassecen ton ,ti ot deilppa eb nac taht s fo rebmun eht si tsil a ni tcejbo na fo htped eht ;stsilbus sti fo yna ni meti yna fo htped mumixam eht snruter dna )eert a ei( tsil
detsen ylpeed ylirartibra na tnemugra sa sekat taht noitcnuf a etirW ]skram 3[ .b →
:.g.E .deilppus era srotarepo evitatummoc ylno emussa yam uoy yticilpmis roF .rotarepo nevig eht gnisu eert eht fo sedon lla gninibmoc fo tluser eht nruter dna stnemugra sa eert a dna ,eulav
,p
→ →
:.g.E
r min max
a3q4_streams.scm
Xn+1 = (a*Xn + c) mod m
(list->stream lis)
(stream->list strm n) n factorials
(stream->list factorials 10) (1 1 2 6 24 120 720 5040 40320 362880)
(prng seed)
(stream->list (prng 3) 5) (0.01585 0.4954 0.9988 0.7253 0.0307)
(random-int r min max)
(stream->list (random-int (prng 3) 10 20) 5) (10 14 19 17 10)
eht etic tsum uoy tub tnemngissa eht ro erutcel ni dnuof txet ro edoc yna esu yam uoY .skram orez eviecer lliw dna ,noitatnemucod tneicffius etutitsnoc ton seod senilediug tnemngissa eht gnitsap dna gniypoc ,eton esaelP .AT suoreneg a si AT yppah a ;elbadaer ylisae dna dettamrof-llew si edoc ruoy taht erusnE .)nruter( tuptuo dna )sretemarap( stupni detcepxe sti gnidulcni noitcnuf hcae fo esoprup eht tnemucoD .selfi lla fo pot eht ta stnemmoc ni era rebmun tneduts dna eman ruoy taht erusnE
→ ,.g.E .) , [ egnar eht ni sregetni modnar fo maerts a snruter dna )1,0[ egnar eht ni srebmun
modnar fo maerts a sekat taht erudecorp a etaerC ]skram 3[ .e )1,0[ egnar eht ni srebmun ylno stime maerts ruoy taht erusne dluohs uoy ,]1-m,0[ egnar eht ni srebmun snruter evoba noitauqe eht :etoN
:stnatsnoc gnrp eht rof seulav gniwollof eht esU →
:.g.E .)1,0[ egnar eht ni srebmun modnar fo maerts etinfini na secudorp dna tnemugra sa
eulav dees a sekat taht
dellac erudecorp a etaerc ,alumrof siht gnisU
:noitauqe gniwollof eht gnisu denfied eb nac )gnrp( rotareneg rebmun modnar-oduesp A ]skram 4[ .d
evitucesnoc fo maerts etinfini eht ot srefer taht tsrfi eht morf tsil a sekam taht
maerts a etaerC ]skram 2[ .c .maerts nevig eht fo smeti
nevig a morf maerts a sekam taht
noitatnemucoD gnitseT & noitatnemucoD
)m < 0X ≤ 0( "dees" eht si 0X dna ,)m < c ≤ 0( "tnemercni" eht si c ,)m < a < 0( "reilpitlum" eht si a ,)m<0( "suludom" eht si m erehw
→
.g.E !0 morf gnitrats seulav lairotcaf
0.1 = c 77459622 = a 232 = m
erudecorp a etaerC ]skram 3[ .b .tsil
erudecorp a etaerC ]skram 2[ .a :smelborp gniwollof eht evlos , dellac elfi a nI
4 noitseuQ
.senilediug noissimbus lla rof eniltuo esruoc eht ees esaelP .ylppa lliw snoitcuded etal sdrawretfa ,etad eud eht erofeb em tcatnoc ,noissimbus htiw seussi gnivah era uoy fI
.yllufsseccus detelpmoc si noissimbus eht taht GNIRUSNE dna selfi lla gnittimbus rof elbisnopser era uoY .snoissimbus etal rof detcuded eb lliw skraM .etad eud eht erofeb nraeLuc gnisu tnemngissa ruoy timbuS .tnaveler dna raelc eb dluohs seman tub ,selfi piz. rof noitnevnoc gniman yrotadnam on si erehT .noissimbus ruoy rof elfi piz. elgnis a otni selfi lla enibmoC .snoitseuq detceffa eht rof orez fo edarg a ni tluser lliw snoitnevnoc gniman debircserp eht wollof ot eruliaF .noissimbus ruoy rof seman noitcnuf dna elfi dedivorp lla dna yna esu tsum uoY .noitseuq taht rof %001 ot pu snoitcuded ni tluser yam )SR5R gnisu tekcaRrD ni( elbannur ton era taht selfi edoc ynA .elfi nevig eht ni snoitulos yna rof orez fo kram a ni tluser lliw stropmi fo esu deticilosnU .detats esiwrehto sselnu seirarbil lanretxe yna esu ton oD .ot desu er'uoy ycnerapsnart laitnerefer eht ot kcits esaelp ,tnemngissa siht rof snoitulos ruoy ni )! htiw erudecorp ni-tliub yna ro( !tes gnisu og t'noD .selbairav elbatum ro stcurtsnoc gnipool fo esu on snaem sihT .ssalc ni detartsnomed sa elyts lanoitcnuf tcerroc esu ot detcepxe era tnemngissa siht rof snoitulos ruoY
.)nwo ruoy dnfi ro( hcaorppa rehtie esu ot eerf era uoY .mcs.semirp :ereh dnuof eb nac )tekcaR morf deworrob( gnitset tinu gnitartsnomed elpmaxe ralimis A .mcs.semirp :ereh dnuof eb nac gnitset dna noitatnemucod gnidulcni noissimbus elpmaxe nA
.secnereffid yna rof snoitanalpxe dna tuptuo devresbo sa llew sa tuptuo detcepxe gnivig ,yhw dna gnitset era uoy tahw ot sa gnitset ruoy tnemmoC :secitcarp tseb roF .skram orez eviecer lliw dna ,gnitset tneicffius etutitsnoc ton seod snur elpmaxe dedivorp eht gnitsap dna gniypoc ,eton esaelP etairporppa erehw euqinu eb ot detcepxe era sesac tset ruoY .noitseuq a rof skram 0 ni tluser lliw stuptuo tset detacirbaF .epyt tcerroc eht fo era deilppus stupni emussa yam uoy ,defiiceps esiwrehto sselnU .edoc ruoy fo sehcnarb elbissop lla dna stupni dilav lla revoc dluohs tub ,dnah ta noitseuq eht no dneped deriuqer stset cfiiceps ehT .noissimbus ruoy ni noitcnuf yreve fo snur gnitset edulcni ot deriuqer era uoY
.yltcerroc ecruos eht etic tsum uoy tub tnemngissa eht ro erutcel ni dnuof txet ro edoc yna esu yam uoY
senilediuG noissimbuS
]latot skram 5[
gnitseT