302 Final Questions

25 Pages
695 Views
Unlock Document

Department
Computer Science (Sci)
Course
COMP 302
Professor
Brigitte Pientka
Semester
Fall

Description
Q.▯Implement▯a▯higher▯order▯function▯that▯combines▯two▯lists▯with▯a▯specific▯com bining▯function,▯ie▯combine▯(+,▯[1,2,3],▯[4,5,6])▯=▯[(1+4),▯(2+5),▯3+6)]▯without ▯using▯existing▯functions▯from▯the▯List▯or▯ListPair▯libraries. A.▯fun▯combine▯f▯[]▯[]▯=▯[] |▯fun▯combine▯f▯[]▯(y::ys)▯=▯raise▯ListsUnequal |▯fun▯combine▯f▯(x::xs)▯[]▯=▯rais▯ListsUnequal▯ |combine▯f▯(x::xs)▯(y::ys)▯=▯(f(x,y))▯::▯(combine▯f▯xs▯ys) =========================================================== Inductive▯Proof: fun▯prod([])▯=▯1 ▯▯|▯prod(h::t)▯=▯h▯*▯prod(t) fun▯prod'([],▯acc)▯=▯acc ▯▯|▯prod'(h::t,▯acc)▯=▯prod'(t,▯h▯*▯acc) Prove▯that▯for▯any▯list▯l,▯prod(l)▯=▯prod'(l,▯1) Answer: Use▯the▯lemma,▯prod(l)▯*▯acc▯=▯prod'(l,▯acc) Base▯Case:▯l▯=▯[] prod([])▯*▯acc▯=▯acc prod'([],▯acc)▯=▯acc Therefore,▯prod([])▯*▯acc▯=▯prod'([],▯acc) Induction▯Step:▯l▯=▯(h::t) Suppose▯prod(h::t)▯*▯acc▯=▯prod'(h::t,▯acc) prod(h::t)▯*▯acc▯=▯h▯*▯prod(t)▯*▯acc ▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯=▯prod(t)▯*▯(h▯*▯acc) ▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯=▯prod'(t,▯h▯*▯acc) ▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯=▯prod'(h::t,▯acc) Therefore,▯prod(h::t)▯*▯acc▯=▯prod'(h::t,▯acc) Thus,▯prod(l)▯*▯acc▯=▯prod'(l,▯acc) Hence,▯prod(l)▯=▯prod'(l,▯1) =========================================================== question: Using▯the▯filter▯function,▯write▯a▯function▯which▯takes▯as▯its▯input▯two▯lists▯ and▯returns▯a▯list▯containing▯the▯intersection▯of▯the▯two▯list.▯ Ex:▯ ▯▯intersection▯[1,2,3,4]▯[1,4,5]; val▯it▯=▯[1,4]▯:▯int▯list solution: fun▯intersection▯[]▯l2▯=▯[] ▯▯|▯intersection▯(x::xs)▯l2▯= (List.filter▯(fn▯y▯=>▯(y▯=▯x))▯l2)@(intersection▯xs▯l2) =========================================================== datatype▯series▯=▯Constant▯of▯real▯|▯Cons▯of▯real▯list▯*▯recurrence and▯recurrence▯=▯operation▯list and▯operation▯=▯Plus▯|▯Minus|▯Times▯|▯Div▯|▯Rparen▯|▯Lparen▯ (*Example:▯the▯fibonacci▯series▯(T(n)▯=▯T(n▯1)+T(n▯2))*) val▯fib▯=▯Cons([0,1],▯[Plus]) (*Example:▯Tribonacci▯series▯(T(n)▯=▯T(n▯1)+T(n▯2)+T(n▯3))*) val▯trib▯=▯Cons([0,1,2],▯[Plus,▯Plus]) (*Example:▯A▯strange▯series▯(T(n)▯=▯T(n▯1)*(T(n▯2)+T(n▯3))+T(n▯4))*) val▯strange▯=▯Cons([0,1,2,3],▯[Times,▯Lparen,▯Plus,▯Rparen,▯plus]) (*recurrence▯must▯have▯n▯1▯of▯Plus/Minus/Times/Div▯for▯a▯real▯list▯of▯length▯n*) (*Question:▯Implement▯the▯function▯Series_Stream,▯which▯takes▯a▯series as▯input,▯and▯outputs▯a▯real▯stream▯of▯elements▯of▯the▯series*) (*Series_Stream:▯series▯▯>▯real▯stream*) (*▯I▯attemped▯to▯implement▯this▯function,▯and▯got▯horribly▯bogged▯down. I▯thought▯it▯was▯valuable,▯though.*) =========================================================== Consider▯the▯following▯two▯programs▯for▯multiplying▯all▯the▯elements▯of▯a▯list▯t ogether.▯The▯first▯one▯is▯the▯naive version,▯while▯the▯second▯one▯is▯the▯tail▯recursive▯version. ex:▯[1,▯2,▯3]▯will▯give▯you▯1*2*3=6 fun▯mult([])▯=▯1 fun▯mult'▯([],▯acc)▯=▯acc |▯mult(x::t)▯=▯x▯*▯mult(t) |▯mult'▯(x::t,▯acc)▯=▯acc▯*▯mult'(t,▯acc*x) Prove▯that▯both▯programs▯yield▯the▯same▯result: Theorem. ▯For▯any▯list▯l,▯mult(l)*acc▯=▯mult'(l,▯acc) Proof.▯ Induction▯on▯l. Base▯Case:▯l▯=▯[] mult([])*acc =>▯1*acc▯ by▯program▯mult =>▯acc▯ by▯program▯* <=▯mult'([],▯acc)▯ by▯program▯mult' Step▯Case:▯l▯=▯x::t Assuming,▯for▯any▯acc',▯mult(t)*acc'▯=▯mult'(t,acc'), we▯must▯prove▯mult(x::t)*acc'▯=▯mult'(x::t,▯acc')▯. mult(x::t)*acc =>▯(x*(mult(t)))*acc▯ by▯program▯mult =>▯x*(mult(t)*acc)▯ by▯associativity▯of▯* =>▯x*▯mult'(t,▯acc)▯ by▯Lemma <=▯mult'(x::t,▯acc)▯ by▯program Hence▯mult(x::t)*acc▯=▯mult'(x::t,▯acc)▯and▯the▯question▯is▯done. =========================================================== What▯is▯the▯main▯benefits▯of▯laziness▯in▯computing? Laziness▯will▯support▯demand▯driven▯computation▯as▯opposed▯to▯need▯drive n.▯This▯is▯especially▯useful▯for▯data▯structures▯that▯theoretically▯have▯infinit e▯length▯(e.g.▯Fibonnaci▯sequence).▯Obviously,▯we▯are▯not▯able▯to▯create▯the▯ful l▯Fibonnacci▯sequence,▯but,▯with▯lazy▯programming,▯we▯can▯create▯only▯as▯much▯of ▯the▯sequence▯as▯we▯need▯for▯a▯specific▯computation.▯▯It▯is▯also▯useful▯for▯proc essing▯user▯input▯driven▯software▯since▯the▯length▯of▯the▯input▯is▯not▯known▯bef orehand. =========================================================== Implement▯a▯function▯that▯creates▯a▯counter▯using▯references. The▯counter▯should▯have▯the▯following▯2▯functions:▯tick()▯and▯reset().▯ (*▯newCounter:▯unit▯▯>▯{tick▯:▯unit▯▯>▯int,▯reset:▯(unit▯▯>▯unit)}▯*) The▯counter▯should▯have▯the▯initial▯value▯of▯0. tick()▯increments▯the▯value▯of▯the▯counter▯by▯1▯and▯return▯the▯updated▯value. reset()▯resets▯the▯value▯of▯the▯counter▯back▯to▯0. Example▯of▯usage: val▯c1▯=▯newCounter(); val▯c2▯=▯newCounter(); #tick▯c1▯(); (*▯1▯*) #tick▯c1▯(); (*▯2▯*) #tick▯c2▯(); (*▯1▯*) #reset▯c1▯(); #tick▯c1▯(); (*▯1▯*) #tick▯c2▯(); (*▯2▯*) xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx SOLUTION: fun▯newCounter▯()▯=▯ ▯▯let ▯▯▯▯val▯counter▯=▯ref▯0 ▯▯▯▯fun▯tick▯()▯=▯(counter▯:=▯!counter▯+▯1;▯!counter) ▯▯▯▯fun▯reset()▯=▯(counter▯:=▯0) ▯▯in ▯▯▯▯{tick▯=▯tick,▯reset▯=▯reset} ▯▯end =========================================================== Q:▯Implement▯a▯function▯factorial:▯int▯*▯int▯▯>▯int▯in▯both▯a▯recursive▯and▯tail ▯recursive▯form. Raise▯the▯exception▯where▯the▯input▯is▯negative▯in▯the▯latter▯case. A: exception▯Negative fun▯factorial▯0▯=▯1 ▯▯|▯factorial▯n▯=▯n*factorial▯(n▯1) (* tail▯recursion: *) fun▯factorial_tr'▯0▯acc▯=▯acc ▯▯|▯factorial_tr'▯n▯acc▯=▯factorial_tr▯(n▯1)▯(n*acc) fun▯factorial_tr▯n▯= ▯▯if▯(0▯=▯'b but▯it▯gives▯seahorse▯'a▯'b▯▯>▯'b should▯be▯ fun▯seahorse▯s▯[]▯=▯[] |seahorse▯s▯[a,b]▯=▯if▯(s▯a)▯then▯a else▯seahorse▯s▯[b] =========================================================== Accumulators In▯class▯we▯discussed▯various▯issues▯with▯accumulators▯and▯how▯we▯could▯simplify ▯our▯functions▯by▯storing▯previously▯computed▯values▯and▯passing▯it▯recursively▯ in▯the▯function.▯This▯could▯reduce▯a▯lot▯of▯time▯in▯the▯calculation▯of▯certain▯p rograms▯such▯as▯fibbonaci▯and▯factorial.▯We▯showed▯in▯class▯how▯we▯could▯create▯ a▯tail▯recursive▯version▯of▯factorial▯however,▯would▯using▯an▯accumulator▯for▯fi bonacci▯be▯much▯the▯same? fun▯fib▯0▯=▯1 |▯fib▯1▯=▯1 |▯fib▯n▯=▯fib(n▯1)▯+▯fib(n▯2) Clearly▯in▯order▯to▯make▯this▯function▯use▯accumulators,▯we▯will▯need▯to▯have▯2▯ accumulators▯since▯fib▯makes▯2▯seperate▯calculations.▯To▯do▯this▯we▯will▯first▯c reate▯the▯function▯that▯will▯do▯all▯the▯work▯since▯we▯will▯be▯unable▯to▯run▯the▯ tail▯recursion▯in▯1▯function▯with▯2▯calculations▯unlike▯factorial. fun▯fib'▯prev▯cur▯n▯=▯ if▯n▯=▯1▯then▯cur else▯fib'▯cur▯(prev▯+▯cur)▯(n▯1) In▯the▯case▯above,▯we've▯created▯a▯function▯that▯uses▯two▯accumulators▯(prev▯and ▯cur)▯and▯performs▯the▯calculations.▯This▯use▯of▯accumulators▯will▯allow▯us▯to▯s tore▯the▯values▯that▯we▯need▯to▯access▯from▯previously▯computed▯calculations. fun▯fib▯n▯= if▯n▯=▯0▯then▯0 else▯fib'▯0▯1▯n The▯above▯code▯is▯what▯we▯will▯use▯to▯call▯the▯other▯function.▯As▯we▯can▯se,▯thi s▯code▯also▯covers▯the▯base▯cases▯as▯we▯pass▯it▯0▯1▯automatically▯which▯will▯spe ed▯up▯our▯computation This▯leaves▯us▯with▯our▯full▯function▯of fun▯fib▯n▯= if▯n▯=▯0▯then▯0 else▯fib'▯0▯1▯n fun▯fib'▯prev▯cur▯n▯=▯ if▯n▯=▯1▯then▯cur else▯fib'▯cur▯(prev▯+▯cur)▯(n▯1) Which▯will▯output▯our▯calculated▯fibonacci▯value.▯This▯use▯of▯accumulators▯will▯ greatly▯increase▯the▯speed▯of▯calculation▯for▯our▯program▯and▯will▯allow▯us▯to▯c ompute▯much▯higher▯values. =========================================================== Give▯an▯example▯of▯an▯expression▯which▯does▯not▯evaluate▯properly▯using▯the▯subs titution▯model.▯Explain▯why▯it▯doesn't▯work▯and▯how▯the▯environment▯model▯gets▯a round▯the▯problem. A:▯An▯example▯is▯ let▯ val▯x▯=▯ref▯2 in let▯val▯y▯=▯4 in▯ ▯ ▯(x▯:=▯5);▯(!x▯+▯y) end end Here▯substitution▯will▯fail▯and▯evaluate▯to▯6▯instead▯of▯9▯as▯it▯should.▯This▯is ▯because▯the▯replacements▯in▯!x▯+y▯are▯done▯at▯the▯same▯time▯as▯the▯replacement▯ in▯x▯:=▯5.▯The▯expression▯x▯:=▯5▯is▯never▯actually▯used. The▯environment▯model▯does▯not▯have▯this▯problem▯since▯rather▯than▯substitute▯ea ch▯expression▯looks▯"up"▯the▯diagram▯until▯it▯finds▯what▯it▯is▯looking▯for.▯So▯t he▯value▯in▯the▯location▯pointed▯to▯by▯x▯will▯be▯changed▯to▯5,▯then▯the▯expressi on▯!x▯+▯y▯will▯look▯up▯x▯and▯find▯the▯correct▯value.▯This▯of▯course▯gives▯the▯co rrect▯answer▯as▯SML▯would▯give▯it. =========================================================== Write▯a▯function▯to▯add▯two▯polynomials▯in▯SML.▯The▯polynomials▯are▯represented▯ as▯lists▯of▯integers▯which▯are▯the▯coefficients.▯([1,▯4,▯2,▯0,▯3]▯would▯represen t▯3x^4▯+▯2x^2▯+▯4x▯+▯1) fun▯add▯p▯[]▯=▯p |▯add▯[]▯p▯=▯p |▯add▯(x::xs,▯h::t)▯=▯ (x+y)▯+▯add(xs,▯t)▯ =========================================================== Preparation▯for▯Final: Proposed▯type▯of▯problem▯>Proof▯by▯Induction▯(Structural▯Induction) Example: datatype▯'a▯list▯=▯nil▯|▯::▯of▯'a▯*▯'a▯list fun▯append▯(nil,▯k)▯=▯k ▯▯|▯append▯(h▯::▯t,▯k)▯=▯h▯::▯append▯(t,▯k) Theorem:▯For▯values▯l:▯ty▯list▯and▯k:▯ty▯list,▯append▯(l,▯k)▯result▯ in▯v▯which▯is▯another▯list▯(▯for▯some▯value▯v) Proof: 1)▯Base▯Cases▯(non▯recursive▯cases▯of▯our▯datatype)▯Show▯P(nil)▯holds 2)▯Inductive▯cases▯(l=h::t)▯Assume▯P(t)▯holds▯and▯show▯P(h::t)▯holds The▯actual▯proof▯is▯to▯be▯done▯by▯induction▯on▯the▯structure▯of▯l Base▯Case:▯l▯=▯nil ▯▯▯▯▯▯▯▯▯▯▯append(nil,▯k)▯▯>▯k▯(let▯v▯be▯k) Inductive▯Case:▯l▯=h::t ▯▯▯▯▯▯▯▯▯▯▯append▯(h::t,▯k)▯>▯h::append(t,▯k)▯▯by▯i.hyp▯▯>▯v▯(for▯some▯v▯) ▯>▯h::v =========================================================== Question: Implement▯a▯function▯findAll▯:▯(int▯▯>▯bool)▯▯>▯binary▯search▯tree▯▯>▯int▯list.▯ findAll▯takes▯in▯a▯bool▯function▯and▯returns▯all▯the▯nodes▯that▯satisfy▯this▯fun ction▯in▯the▯form▯of▯an▯exception. Answer: datatype▯'a▯tree▯=▯Empty▯|▯Node▯of▯(int▯*▯'a▯tree▯▯*▯'a▯tree)▯ exception▯answer▯of▯int▯list fun▯findAll▯f▯Empty▯=▯[] ▯▯|▯findAll▯f▯(Node(x,▯l,▯r))▯=▯ ▯▯▯▯if▯f▯x▯then▯x▯::▯findAll▯f▯l▯@▯findAll▯f▯r ▯▯▯▯else▯findAll▯f▯l▯@▯findAll▯f▯r =========================================================== (*Given▯These▯Statments*) fun▯curry▯f▯=▯(fn▯a▯=>▯(fn▯b▯=>▯f▯(a,b))) (*▯val▯it▯=▯fn▯:▯('a▯*▯'b▯▯>▯'c)▯▯>▯'a▯▯>▯'b▯▯>▯'c▯*) fun▯uncurry▯f▯=▯(fn▯(a,b)▯=>▯f▯a▯b) (*▯val▯it▯=▯fn▯:▯('a▯▯>▯'b▯▯>▯'c)▯▯>▯'a▯*▯'b▯▯>▯'c▯*) (*▯Answer▯yes▯or▯no▯for▯each▯of▯the▯following▯functions▯{one,two,three,four}▯if▯ they▯would▯compile,▯if▯they▯would▯give▯a▯valid▯function▯f▯*) (*▯Part▯1:▯*) (* fun▯one▯f▯=▯curry▯curry▯f fun▯two▯f▯=▯curry▯uncurry▯f fun▯three▯f▯=▯uncurry▯curry▯f; fun▯four▯f▯=▯uncurry▯uncurry▯f; *) (*Answer▯*) (*▯One▯will▯not▯compile,▯since▯curry▯expects▯a▯function▯▯'Z▯*▯'Y▯▯>▯'X▯however▯c urry▯returns▯'a▯▯>▯'b▯▯>▯'c▯▯*) (*▯Two▯will▯not▯compile,▯since▯curry▯expects▯a▯function▯'Z▯*▯'Y▯▯>▯'X▯however▯un curry▯returns▯▯'a▯*▯'b▯▯>▯'c▯▯*) (*▯three▯will▯compile▯f▯=▯((fn▯(x,y)=>▯x+y,(3)))▯*) (*▯three▯will▯compile▯f▯=▯((fn▯x▯=>▯fn▯y▯=>▯x+y),(3,2))▯*) =========================================================== Assignment▯4▯Q4 Question: Write▯a▯function▯that▯returns▯the▯x▯▯and▯y▯coordinates▯of▯the▯intersection▯point ▯of▯two▯lines▯in▯the▯form▯ax+b▯(each▯represented▯as▯a▯tuple,▯with▯the▯slope▯bein g▯the▯first▯element,▯and▯the▯y▯intercept▯being▯the▯second▯▯▯all▯ints).▯Should▯re turn▯a▯tuple▯of▯reals▯(use▯Real.fromInt▯to▯convert▯from▯int▯to▯real).▯If▯they▯do n't▯intersect,▯raise▯the▯ParallelLines▯error. Potential▯Answer: exception▯ParallelLines fun▯intersect▯((a1,▯b1),▯(a2,▯b2))▯=▯ ▯▯if▯a1▯=▯a2▯then▯raise▯ParallelLines▯ ▯▯else▯ ▯▯▯▯let▯ ▯▯▯▯▯▯val▯x▯=▯(Real.fromInt▯(b2▯b1))▯/▯(Real.fromInt▯(a1▯a2))▯ ▯▯▯▯in▯ ▯▯▯▯▯▯(x,▯(Real.fromInt▯a1)▯*▯x▯+▯(Real.fromInt▯b1))▯ ▯▯▯▯end =========================================================== Final▯Practice▯Questions: Question▯1:▯Write▯a▯function▯which▯returns▯true▯if▯one▯or▯more▯elements▯in▯a▯lis t▯satisfy▯a▯given▯property▯or▯false▯if▯none▯of▯them▯satisfy▯it,▯using▯foldl.▯ Solution▯1:▯ fun▯contains▯l▯p▯=▯foldl▯(fn▯(a,b)▯=>▯((p▯a)▯orelse▯b))▯false▯l ▯ Question▯2:▯Write▯a▯function▯which▯when▯given▯a▯list▯of▯integers▯l▯and▯a▯non▯neg ative▯integer▯x,▯it▯returns▯the▯longest▯sublist▯of▯l▯starting▯at▯the▯head▯of▯l▯s uch▯that▯the▯sum▯of▯the▯elements▯in▯the▯sublist▯is▯smaller▯than▯or▯equal▯to▯x. Solution▯2:▯ fun▯subList▯x▯[]▯=▯[] |subList▯x▯(hd::tl)▯=▯ ▯▯▯▯ if▯((x▯hd)▯>=▯0)▯then▯ ▯▯▯▯ hd::(subList▯(x▯hd)▯tl) ▯▯▯▯▯▯▯▯else▯ ▯▯▯▯▯▯▯▯ [] =========================================================== Question▯4 Implement▯a▯sorting▯algorithm▯by▯inserting▯items▯into▯a▯list. ins▯:▯'a▯▯>▯'a▯list▯▯>▯'a▯list =========================================================== Q:▯Given▯the▯following▯definition▯of▯the▯binary▯tree▯data▯structure: datatype▯'a▯bintree▯=▯ ▯Empty▯| ▯Node▯of▯'a▯*▯'a▯bintree▯*▯'a▯bintree and▯the▯following▯function▯which▯returns▯the▯depth▯of▯a▯given▯bintree: fun▯depth▯(Empty)▯=▯0 |▯▯▯depth▯(Node(root,▯left,▯right))▯=▯1+max▯(depth▯(left),▯depth▯(right)) a.)▯write▯a▯function▯('a▯bintree▯▯>▯bool)▯to▯check▯if▯a▯given▯binary▯tree▯is▯bal anced▯(the▯depth▯on▯the▯left▯subtree▯is▯equal▯to▯the▯depth▯of▯the▯right▯subtree▯ for▯each▯node▯in▯the▯tree) b.)▯write▯a▯function▯('a▯bintree▯▯>▯'a▯bintree)▯(similar▯to▯map▯on▯a▯list▯of▯ele ments)▯which▯maps▯each▯node's▯element▯to▯another▯element▯according▯to▯a▯given▯ma pping▯(function) ANSWER: a.)▯fun▯isBalanced▯(Empty)▯=▯true ▯▯▯▯▯▯|▯isBalanced▯(Node(root,▯left,▯right))▯= ▯▯▯▯▯▯▯(abs▯(depth▯(left)▯▯▯depth▯(right))▯<=▯1)▯andalso ▯▯▯▯▯▯▯isBalanced▯(left)▯andalso▯isBalanced▯(right) b.)▯fun▯btmap▯(f)▯=▯ let▯fun▯bmap▯(Empty)▯=▯Empty ▯▯▯▯▯▯|▯bmap▯(Node▯(x,▯left,▯right))▯=▯Node▯(f(x),▯bmap▯(left),▯bmap▯(right)) in▯bmap▯end =========================================================== Prove▯that▯if▯L1▯is▯ordered▯and▯L2▯is▯ordered,▯then ▯▯▯▯L1▯@▯L2▯is▯ordered.▯▯State▯the▯condition▯this▯statement▯holds▯ and▯prove▯it▯correct. fun▯ordered▯[]▯▯=▯true ▯▯|▯ordered▯[x]▯=▯true ▯▯|▯ordered▯((key,▯_▯)▯::▯(L▯as▯((key',▯_▯)▯::▯_▯)))▯=▯ ▯▯▯▯ordered▯(L)▯andalso▯key▯▯'a) (*▯delay:▯*) fun▯delay▯(f)▯=▯Susp(f) (*▯force:▯*) fun▯force▯(Susp(f))▯=▯f▯() (*▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯▯*) (*▯Define▯an▯infinite▯stream▯*) datatype▯'a▯stream'▯=▯Cons▯of▯'a▯▯*▯'a▯stream withtype▯'a▯stream▯=▯('a▯stream')▯susp fun▯take▯0▯s▯=▯[] ▯▯|▯take▯n▯(s)▯=▯take'▯n▯(force▯s) and▯take'▯0▯s▯=▯[] ▯▯|▯take'▯n▯(Cons(x,xs))▯=▯x::(take▯(n▯1)▯xs) (*▯Answer:▯*) fun▯nextPrime▯x▯=▯let fun▯checkPrime▯x▯n▯=▯if▯x▯▯nextPrime▯(x+1) end; fun▯primeStream▯n▯=▯Susp(fn▯()▯=>▯Cons(n,▯primeStream▯(nextPrime▯n)▯)) val▯primes▯=▯primeStream▯2; =========================================================== Sorting▯is▯something▯we▯do▯all▯the▯time,▯let's▯do▯it▯once▯more!▯Implement▯merge▯ sort! A▯great▯exam▯question▯for▯sure!▯(Assuming▯the▯pseudocode▯algorithm▯is▯known/give n) fun▯take▯(L)▯= ▯▯▯▯if▯L▯=▯nil▯then▯nil▯else▯hd(L)::skip(tl(L)) and▯skip(L)▯= ▯▯▯▯if▯L=nil▯then▯nil ▯▯else▯take(tl(L)) fun▯merge▯([],▯M)▯=▯M ▯▯▯|merge▯(L,▯[])▯=▯L ▯▯▯|merge▯(x::xl,▯y::yl)▯= ▯▯▯▯if▯(x:int)▯[email protected][]▯=>▯acc ▯▯map_▯tl▯f▯[]▯acc▯=>▯acc induction▯step: Suppose▯that▯a▯for▯a▯list▯of▯size▯n,▯for▯some▯integer▯n,▯the▯lemma▯holds. let▯list'▯be▯of▯size▯n+1 then: ▯ map_tl▯f▯list'▯acc▯=>▯map_tl▯f▯t▯(acc▯@▯[f▯h])▯=>▯▯(acc▯@▯[f▯hd(list')])::(map▯f ▯tl(list)) by▯the▯induction▯hyp and map▯f▯list'▯=>▯f(hd(list'))::(map▯f▯tl(list')) so▯map_tl▯f▯list'▯acc▯=>▯[email protected](map▯f▯list') therefore, for▯any▯list▯the▯lemma▯holds So▯if▯we▯take▯acc▯to▯be▯nil▯we▯get▯the▯desired▯result: map_tl▯f▯list▯[]▯<=>▯map▯f▯list =========================================================== Using▯exceptions,▯create▯a▯function▯that▯take▯as▯input▯a▯list▯of▯integers▯▯conta ining▯the▯values▯of▯coins,▯and▯an▯integer▯representing▯the▯ammount▯to▯be divided▯between▯different▯coins.▯▯This▯function▯must▯return▯a▯list▯of▯the▯coins▯ needed▯whose▯sum▯will▯add▯up▯to▯the▯given▯integer.▯You▯may▯assume▯the▯coin list▯is▯in▯a▯descending▯order▯(or▯ascending▯order▯if▯that▯makes▯it▯easier▯for▯yo u). (*coin_change:▯(int)▯list▯*▯int▯▯>▯(int)▯list*) exception▯Change fun▯▯coin_change▯_▯0▯=▯nil |coin_change▯nil▯_▯=▯raise▯Change |coin_change▯(coin::coins)▯ammount▯=▯ if▯coin>ammount▯then coin_change▯coins▯ammount else (coin::(coin_change▯(coin::coins)▯(ammount▯coin) )) handle▯Change▯=>▯coin_change▯coins▯ammount =========================================================== Write▯a▯function▯to▯generate▯all▯primes▯up▯to▯a▯given▯limit. A▯sieve▯of▯Eratoshthene▯is▯an▯algorithm▯for▯finding▯all▯the▯primes▯up▯to▯a▯given ▯limit.▯The▯algorithm▯goes▯like▯this: 1.▯Generate▯a▯list▯of▯consecutive▯integers▯from▯2▯to▯the▯limit▯M 2.▯Take▯the▯first▯non▯crossed▯number▯and▯cross▯out▯all▯of▯its▯other▯multiples 3.▯Repeat▯step▯two▯until▯there▯is▯nothing▯else▯to▯cross You▯are▯then▯left▯with▯a▯list▯of▯primes. Here▯is▯my▯primitive▯implementation▯of▯this▯using▯tabulate▯and▯filter local val▯multi▯=▯fn▯d▯=>▯fn▯n▯=>▯(n▯mod▯d)▯<>▯0 fun▯helper▯nil▯ =▯[] |▯helper▯(h::t)▯=▯h::(List.filter▯(multi▯h)▯(helper▯t)) in fun▯sieve▯M▯=▯helper▯(List.tabulate▯(M▯1,▯fn▯x▯=>▯x+2)) end Here,▯the▯main▯function▯generates▯a▯
More Less

Related notes for COMP 302

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit