116.001 Recitation 7: Data Abstraction II28 Feb 2007RI: Gerald Dalley ([email protected]) Announcements• Solutions, handouts, etc.:• http://people.csail.mit.edu/dalleyg/6.001/SP2007/• primes-in-range discussion & orders of growth• Office Hours• Thursdays, 2-3PM, 32-D4072Office Hours Location…from Gates TowerRecitation room (3rdfloor) /west side of campusElevatorsFaculty Lunch Area3Overview• Today: prime factorization, an extended example• This is a nice example for several reasons:• Interesting design decisions• Practice with writing types – (using prime and pf as new types)• Related to primality testing from yesterday’s lecture• primes are also important to Project 1…which is due next Friday.4Designing a data abstraction• Prime factorization: representing an integer as the product of its prime factors2 = 2 = 214 = 2∙2 = 226 = 2∙3 = 21∙3140 = 2∙2∙2∙5 = 23∙51187 = 11∙17 = 111∙171What about 1? What about 0? What about negative integers?5(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors n):(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors 40) 2*2*2*5prime-factors-of-1: (addaddaddadd----primeprimeprimeprime----factorfactorfactorfactor p pf):(addaddaddadd----primeprimeprimeprime----factorfactorfactorfactor5 (addaddaddadd----primeprimeprimeprime----factorfactorfactorfactor 2 prime-factors-of-1)) 2*5(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors p): (addaddaddadd----primeprimeprimeprime----factorfactorfactorfactor p pf): (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors 2) => 2(addaddaddadd----primeprimeprimeprime----factorfactorfactorfactor 5 (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors 2)) 2*5(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors factors):(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors (listlistlistlist 2 2 2 5)) 2*2*2*5Designing a data abstraction: constructorsNew typesprimeprimeprimeprime= subset of integers that are primepfpfpfpf= prime factorization data typeinteger integer integer integer pfpfpfpflist<prime> list<prime> list<prime> list<prime> pfpfpfpfprime prime prime prime pfpfpfpfprime, pf prime, pf prime, pf prime, pf pfpfpfpfpfpfpfpfprime, pf prime, pf prime, pf prime, pf pfpfpfpf6Designing a data abstraction: accessorsFor now, assume our constructor is (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors n)(getgetgetget----uniqueuniqueuniqueunique----factorsfactorsfactorsfactors pf):(getgetgetget----multiplicitymultiplicitymultiplicitymultiplicity pf p):contract:let(p0... pi) = (getgetgetget----uniqueuniqueuniqueunique----factorsfactorsfactorsfactors (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors n))and mi= (getgetgetget----multiplicitymultiplicitymultiplicitymultiplicity (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors n) pi)thenn = product of pimi(getgetgetget----allallallall----factorsfactorsfactorsfactors pf):contract:product of (getgetgetget----allallallall----factorsfactorsfactorsfactors (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors n)) = n(getgetgetget----numbernumbernumbernumber pf):contract: (getgetgetget----numbernumbernumbernumber (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors n)) = npf pf pf pf intintintintpf pf pf pf list<prime>list<prime>list<prime>list<prime>pf pf pf pf list<prime>list<prime>list<prime>list<prime>pf, prime pf, prime pf, prime pf, prime integer integer integer integer27Designing a data abstraction: operators+pf+pf+pf+pf, ----pfpfpfpfNot really appropriate for this data type. The only way to do it is converting to integer and then factorizing again.(*pf *pf *pf *pf pf1 pf2):returns factorization of n1*n2(/pf /pf /pf /pf pf1 pf2):returns factorization of n1/n2 if n2n2n2n2 divides n1n1n1n1(gcdgcdgcdgcd----pf pf pf pf pf1 pf2):returns factorization of greatest common divisor of pf1 and pf2(=pf =pf =pf =pf pf1 pf2):tests whether two factorizations are the same(dividesdividesdividesdivides----pf? pf? pf? pf? pf1 pf2):tests whether pf1 divides evenly into pf2(hashashashas----factor? factor? factor? factor? pf p):tests whether p is a prime factor of pfpf,pfpf,pfpf,pfpf,pfbooleanbooleanbooleanbooleanpf,pfpf,pfpf,pfpf,pfbooleanbooleanbooleanbooleanpf,primepf,primepf,primepf,primebooleanbooleanbooleanbooleanpf,pfpf,pfpf,pfpf,pfpfpfpfpfpf,pfpf,pfpf,pfpf,pfpfpfpfpfpf,pfpf,pfpf,pfpf,pfpfpfpfpf8How constructor choices affect operatorsOne constructorSuppose our only constructor is (makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors n)How do I write *pf: pf,pfpf,pfpf,pfpf,pfpf pf pf pf ?(definedefinedefinedefine (*pf*pf*pf*pf pf1 pf2)(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors(* (getgetgetget----number number number number pf1) (getgetgetget----number number number number pf2))))(definedefinedefinedefine (*pf*pf*pf*pf pf1 pf2) : pf,pfpf,pfpf,pfpf,pfpfpfpfpf(letletletlet ((combined-factors (appendappendappendappend (getgetgetget----allallallall----factorsfactorsfactorsfactors pf1) (getgetgetget----allallallall----factorsfactorsfactorsfactors pf2))))... how do I make a pf out of the resulting list of factors?))Let's provide two constructors:(factorizefactorizefactorizefactorize n) : integer integer integer integer pfpfpfpf(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors lst) : list<prime> list<prime> list<prime> list<prime> pfpfpfpf(definedefinedefinedefine (*pf*pf*pf*pf pf1 pf2)(makemakemakemake----primeprimeprimeprime----factorsfactorsfactorsfactors(appendappendappendappend (getgetgetget----allallallall----factorsfactorsfactorsfactors pf1) (getgetgetget----allallallall----factorsfactorsfactorsfactors pf2)))9Many different representations are possible(factorizefactorizefactorizefactorize 40); 40 = 2*2*2*5⇒(2 2 2 5) 2*2*2*5 (sorted order)⇒(2 5 2 2) 2*5*2*2 (order doesn't matter)⇒((2 3) (5 1)) 23* 51⇒(40 (2 5)) stores n and its unique factors10Representation matters; representation (2 2 2
View Full Document
Unlocking...