Assignment 1: Recursion and Higher-Order Functional Abstractions
append
naturally recursive
#lang typed/racket
a1.rkt
append
type
We’ve recently updated the course policies for the semester. Please read through them before beginning the rest of the assignment.
Show pagesource
Log In
a1.rkt
countdown
insertR
functions need only hold over eqv?-comparable structures.
For this and later questions, these
> (countdown 5)
(5 4 3 2 1 0)
> (insertR ‘x ‘y ‘(x z z x y x))
(x y z z x y y x y)
remv-1st
.devomer lobmys eht fo ecnerrucco tsrfi eht htiw tsil wen a snruter dna tsil a dna lobmys a a sekat taht erudecorp a tset dna enfieD .3
.lobmys tsrfi eht fo ecnerrucco hcae retfa detresni lobmys dnoces eht htiw tsil wen a snruter dna tsil a dna slobmys owt sekat taht erudecorp a tset dna enfieD .2
.redro gnidnecsed ni ,rebmun taht ot lauqe ro naht ssel srebmun larutan eht fo tsil a snruter dna rebmun larutan a sekat taht erudecorp a tset dna enfieD .1
.gnittimbus erofeb ,snur ti taht dna ,emanelfi siht yltcaxe sah elfi ruoy erus ekam esaelP .]ude.ui.savnac//:ptth[ savnaC aiv ti
timbus dna ,
deman elfi a ni edoc ruoy fo lla ecalP .serudecorp tekcaR evisrucer gniwollof eht etirW tnemngissA
.mrof dradnats ot noitcnuf nnamrekcA eht fo noitacfiilpmiS .cte/noitaitnenopxe/noitacilpitlum/noitidda detaeper rof snoitcnuf evisrucer no setoN
.lufpleh secruoser gniwollof eht dnfi yam uoy ,tnemngissa siht htiw deecorp uoy sA etoN
.)emit dna( etad eud eht ot roirp noissimbus tsal eht edarg lliw ew ,hsiw uoy sa semit ynam sa krow ruoy timbus ot eerf leef esaelP .krowemoh ruoy timbus uoy nehw elfi ruoy eltit ot erus ekaM .ssalc ni nettirw smargorp fo elyts eht ni srewsna etirw ot si ti ;srewsna tcerroc eht teg taht smargorp etirw ot ylpmis ton si evitcejbo ehT .skcehc epyt ti erus ekaM . sti dna margorp eht nwod etirw ,noitulos hcae roF .krowemoh ruoy ni esu dluohs uoY .smelborp rehto rof ti esu
ot eerf leef ,8 melborp rof nwo ruoy denfied evah uoy ecno tuB .tekcaR morf noitcnuf
eht esu ton yam uoy ,elpmaxe roF .krow eht fo klub eht eldnah taht serudecorp ni-tliub esu ton yam uoY .nevig eb ton lliw tiderc ro ,)elbissop ton sselnu( eb tsum snoituloS
tnemngissa siht rof senilediuG .emit rof noitpircsed sedart ti ecnis noitatupmoc fo toor eht si noisruceR
.0
> (remv-1st ‘x ‘(x y z x))
(y z x)
> (remv-1st ‘y ‘(x y z y x))
(x z y x)
> (remv-1st ‘z ‘(a b c))
(a b c)
list-index-ofv
> (list-index-ofv ‘x ‘(x y z x x))
0
> (list-index-ofv ‘x ‘(y z x x))
2
filter
#t #f number? #t
> (filter even? ‘(1 2 3 4 5 6))
(2 4 6)
zip
> (zip ‘(1 2 3) ‘(a b c))
((1 . a) (2 . b) (3 . c))
> (zip ‘(1 2 3 4 5 6) ‘(a b c))
((1 . a) (2 . b) (3 . c))
> (zip ‘(1 2 3) ‘(a b c d e f))
((1 . a) (2 . b) (3 . c))
#f
> (map add1 ‘(1 2 3 4))
(2 3 4 5)
> (append ‘(42 120) ‘(1 2 3))
(42 120 1 2 3)
> (append ‘(a b c) ‘(cat dog))
(a b c cat dog)
reverse
> (reverse ‘(a 3 x))
(x 3 a)
fact 01
> (fact 0)
1
> (fact 5)
120
map p ls
p ls map
append
ls1 ls2
ls1 ls2
#t
. eb ot denfied si fo lairotcaf ehT .rossecederp sti fo lairotcaf eht yb ti gniylpitlum yb detupmoc si rebmun a fo lairotcaf ehT .rebmun
taht fo lairotcaf eht setupmoc dna rebmun larutan a sekat taht
erudecorp a tset dna enfieD .01
.tsil taht fo esrever eht snruter dna tsil a sekat taht
erudecorp a tset dna enfieD .9
. ot sdneppa dna , dna
,stsil owt sekat taht
erudecorp a tset dna enfieD .8
ruoy ni ni-tliub s’tekcaR esu ton oD .
a snruter dna tsil a dna tnemugra eno fo
.noitinfied fo stnemele eht ot gniylppa fo stluser eht gniniatnoc tsil wen erudecorp a sekat taht erudecorp a tset dna enfieD .7
.eno regnol eht fo liat eht pord neht ,htgnel nevenu fo era stsil owt eht fI .stsil tupni owt eht fo stnemele gnidnopserroc eht gninibmoc yb demrof riap a si hcihw fo tnemele hcae ,tsil wen a smrof dna stsil owt sekat taht erudecorp a tset dna enfieD .6
.tnemugra taht rof snruter etaciderp eht fi ,neht ,etaciderp eht sefisitas tnemugra ehT .esiwrehto dna rebmun a si tnemugra sti fi snruter ,elpmaxe rof ,etaciderp ehT . ro rehtie snruter dna tnemugra elgnis a sekat taht erudecorp a si etaciderp A .etaciderp eht yfsitas taht stnemele eht gniniatnoc tsil wen a snruter dna tsil a dna etaciderp a sekat taht erudecorp a tset dna enfieD .5
.atad dab deredisnoc eb lliw tnemele taht gnissim tsil A .tsil eht ni tnemele taht fo xedni )0 esab( eht snruter dna tsil a dna tnemele na sekat taht erudecorp a tset dna enfieD .4
append-map
s2
fib
n
> (fib 0)
0
> (fib 1)
1
> (fib 7) 13
equal?
(ab) (a.(b.())) ((w x) y (z))
rewrite
binary->natural
0 1
> (binary->natural ‘())
0
> (binary->natural ‘(0 0 1))
4
> (binary->natural ‘(0 0 1 1))
12
> (binary->natural ‘(1 1 1 1))
15
> (binary->natural ‘(1 0 1 0 1))
21
> (binary->natural ‘(1 1 1 1 1 1 1 1 1 1 1 1 1))
8191
div
minus
> (minus 5 3)
2
> (minus 100 50)
50
> (div 25 5)
5
> (div 36 6)
6
append-map map lspls p
ls append
set-difference s1 s1 nots2
p
> (append-map countdown (countdown 5))
(5 4 3 2 1 0 4 3 2 1 0 3 2 1 0 2 1 0 1 0 0)
> (set-difference ‘(1 2 3 4 5) ‘(2 4 6 8))
(1 3 5)
. ni era taht ni stnemele eht lla gniniatnoc tsil a snruter dna dna )stnemele etacilpud on htiw stsil( stes tafl owt sekat taht noitcnuf a enfieD .71
.noitinfied ruoy ni
ni-tliub s’tekcaR esu ton oD .stluser etaidemretni eht rehtegot ew dna ,tsil a si fo tnemele hcae no fo tluser eht taht etadnam ew ,hguoht ,ereH . fo stnemele eht fo hcae ot seilppa dna stupni fo tsil a tnemugra eno fo erudecorp a htob sekat , ot ralimis ,taht noitcnuf a enfieD .61
.atad dab esruoc fosiorezybnoisiviD.)taNfopuorgbusas’taht]puorg_naileba_elbisiviD/ikiw/gro.ikiwbus.sporppuorg//:sptth[ puorg naileba elbisivid eht rof ,si taht( tsrfi eht sedivid ylneve rebmun dnoces eht nehw krow ylno deen , ,noitcnuf noisivid ruoY .noisrucer larutan gnisu noisivid enfieD .51
.evitagennon eb lliw tluser eht erehw stupni evitagennon ekat ylno deen , ,noitcnuf noitcartbus ruoY .noisrucer larutan gnisu noitcartbus enfieD .41
:elpmaxe roF .rebmun taht snruter dna redro tib esrever ni rebmun yranib dengisnu na gnitneserper s dna s fo tsil tafl a sekat taht erudecorp a tset dna enfieD .31
).tnemmoc a ni ti ecalp dna dnah yb noisserpxe nevig eht etirwer tsuj ;erudecorp a enfied ot evah ton od uoY( .etaciderp
s’tekcaR gnisu noitulos ruoy tset ot erus eB .elbissop sa stod ynam sa gnisu noisserpxe eht etirwer ,egdelwonk siht gnisU .tnelaviuqe era dna snoisserpxe ehT .21
.srebmun suoiverp owt eht gnidda yb detupmoc si ecneuqes eht ni rebmun hcaE .)… ,12 ,31 ,8 ,5 ,3 ,2 ,1 ,1 ,0( ecneuqes iccanobiF eht ni ,orez morf gnitrats ,rebmun htn eht setupmoc dna tupni sa rebmun larutan a sekat taht erudecorp a tset dna enfieD .11
powerset
> (powerset ‘(3 2 1))
((3 2 1) (3 2) (3 1) (3) (2 1) (2) (1) ())
> (powerset ‘())
(())
> (cartesian-product ‘((5 4) (3 2 1)))
((5 3) (5 2) (5 1) (4 3) (4 2) (4 1))
[http://docs.racket-lang.org/reference/pairs.html?
q=foldr#%28def._%28%28lib._racket%2Fprivate%2Flist..rkt%29._foldr%29%29]
insertR-fr
filter-fr
map-fr
append-fr
reverse-fr
binary->natural-fr
append-map-fr
set-difference-fr
powerset-fr
foldr
foldr
f
50
n (f n)
.1 si , regetni evitisop yreve rof ,rehtehw ot sa ,]erutcejnoc_ztalloC/ikiw/gro.aidepikiw.ne//:ptth[ erutcejnoC ztalloC eht sa nwonk ,scitamehtam ni noitseuq nepo na si tI
.hctip selas ym s’tahT .oitar txet/tnemnethgilne hgih yrev dna ,ylkciuq sevom ,trohs s’tI .gniht elohw eht daer ll’uoy ,srewsna eht ta keep uoy fi taht )2( dna ,nwo ruoy no tsrfi ti yrt ll’uoy )1( esimorp ot evah uoy tub ,]95391/43912/daolnwod/elcitra/scirb/php.xedni/kd.teketoilbibstats.sjo//:ptth[ ereh srewsna fo elpuoc tsal eht fo noitanalpxe dna noitavired eht tuoba uoy llet attog I ,looc gnihtemos ffo wohs ot esucxe na pu ssap ot etah I ecniS .dnuora t’nerew tsuj detnarg rof ekat ew taht dna smoidi gnimmargorp nommoc eht fo ynam dna ,yadot era yeht ekil ecalpnommoc t’nerew snoitcnuf redro-rehgih ,gniht a t’nsaw epocs lacixel nehw kcab ,oga sraey tsomla siht devlos klof )tiebla ,revelc ytterp( emos taht wonk ,rehtruf uoy esaet ot dnA
.gniwolb-dnim tsuj er’yehT .smelborp-bus owt tsal eht fo snoitinfied lufituaeb ylgninnuts era erehT .
htiw gnimmargorp tuoba uoy hcaet osla lliw tI .]fdp.dlof/1/422/ku.ca.mahgnitton.stnirpe//:ptth[ smelborp-bus evoba eht fo lareves ot srewsna gniniatnoc srotarepo dlof no esitaert a dnemmocer nac I ,ekil dluow uoy fI
eht ,si tahT .
:gniwollof eht eb dluohs seman ehT .sevlesmeht ot refer ton dluohs snoitinfied ruoy fo seidob gnisu daetsni evoba morf smargorp evisrucer-larutan eht fo emos etirweR .02
.elbatpecca si siht ;reffid yam selput ruoy fo redro tcaxe ehT .snoitanibmoc hcus lla sniatnoc dluohs tsil tuptuo ehT .cte ,tes dnoces eht fo tnemele na noitisop dnoces eht ni ,tes tsrfi eht fo tnemele na noitisop tsrfi eht ni sah elput hcaE .)stsil .e.i( selput fo tsil a si tluser ehT .)setacilpud evah t’nod noitnevnoc nopu deerga ruo yb taht stsil ylpmis niaga( stes fo tsil a revo denfied si tcudorp-naisetrac ehT .91
.elbatpecca si siht ;reffid yam stsil ruoy fo redro tcaxe ehT .tsil eht ni stnemele eht fo tes rewop eht snruter dna tsil a sekat erudecorp ehT
.flesti S dna tes ytpme eht gnidulcni ,S fo stesbus lla fo tes eht si ,)S(P detoned ,S tes yna fo tes rewop eht ,scitamehtam nI .81
woleb sa denfied noitcnuf a redisnoC .12
sresaetniarB
collatz collatz
(: collatz (-> Number Number))
(define collatz
(letrec
((odd-case
(lambda ([recur : (-> Number Number)])
(lambda ([x : Number])
(cond
((and (exact-integer? x) (positive? x) (odd? x)) (collatz (add1 (* x 3))))
(else (recur x))))))
(even-case
(lambda ([recur : (-> Number Number)])
(lambda ([x : Number])
(cond
((and (exact-integer? x) (positive? x) (even? x)) (collatz (/ x 2)))
(else (recur x))))))
(one-case
(lambda ([recur : (-> Number Number)])
(lambda ([x : Number])
(cond
((zero? (sub1 x)) 1)
(else (recur x))))))
(base
(lambda ([x : Number])
(error ‘error “Invalid value ~s~n” x))))
… ;; this should be a single line, without lambda
))
collatz
> (collatz 12)
1
> (collatz 120)
1
> (collatz 9999)
1
quine 5 #t
>5 5
> #t #t
> ((lambda (x) (list x (list ‘quote x)))
‘(lambda (x) (list x (list ‘quote x))))
((lambda (x) (list x (list ‘quote x)))
‘(lambda (x) (list x (list ‘quote x))))
quine
> (equal? quine (eval quine))
#t
> (equal? quine (eval (eval quine)))
#t
.eurt eb neht dluohs gniwollof ehT . sa ti enfied dna ,eniuq tekcaR gnitseretni nwo ruoy etirW
.eniuq tekcaR gnitseretni na si woleB .eniuq tekcaR gnitseretni na naeloob a ron rebmun a rehtien si taht tekcaR ni eniuq a llac lliw eW
.seniuq htob era dna ,tekcaR nI .margorp lanigiro eht fo )edoc ecruos .e.i( sgnitsil eht si tuptuo esohw margorp a si A .22
.¡±eulav dilavnI¡° rorre na langis dluohs ti ,sregetni evitisop -non rof ;sregetni evitisop fo ztalloc eht etupmoc dluohs ruoY .adbmal esu ton dluohs dna ,gnol enil )detnedni-ylitterp( eno naht erom on eb dluohs tI .trohs yrev eb dluohs rewsna detelpmoc ruoY
.evoba noitpircsed lacitamehtam eht ot ralimis rennam a ni etarepo ,tupni na sa regetni evitisop a nevig nehw ,lliw hcihw noitcnuf a eb dluohs . fo noitinfied woleb eht etelpmoc ,ot si ksat ruoY
tresseD tsuJ
nnamehj yb 95:11 20/20/0202 :defiidom tsaL ¡¤ txt.1-tnemngissa
.stset evoba eht esu ot erus ekaM .tsil a ot etouq a dneperp lliw noitnevnoc gnitnirp dradnats s’tekcaR ;eniuq a si tsil tekcaR yreve toN