(* $Id: intro.ML,v 1.1 1997/10/14 13:34:47 lcp Exp lcp $ *) (**** LECTURE 1: Algorithms ****) val pi = 3.14159; fun area (r) = pi*r*r; fun toSeconds (minutes, seconds) = seconds + 60*minutes; fun fromSeconds seconds = (seconds div 60, seconds mod 60); (*exercise: version including hours--needs "let"!*) fun toSeconds (hours, minutes, seconds) = seconds + 60*(minutes + 60*hours); fun fromSeconds seconds = let val minutes = seconds div 60 val hours = minutes div 60 in (hours mod 60, minutes mod 60, seconds mod 60) end; (**** LECTURE 2: Recursive Functions ****) fun npower(x,n) = if n=0 then 1.0 else x * npower(x, n-1); (** Overloading and type constraints **) (*fun square x = x*x; ILLEGAL*) fun square(x : real) = x*x; fun square x : real = x*x; fun square x = x*x : real; (*A boolean-valued function to test whether a number is even*) fun even n = (n mod 2 = 0); (*raising to an integer power--fast version*) fun power(x,n) : real = if n=1 then x else if even n then power(x*x, n div 2) else x * power(x*x, n div 2); (*the sum of the first n integers*) fun nsum n = if n=0 then 0 else n + nsum (n-1); fun summing (n,total) = if n=0 then total else summing (n-1, n + total); (*** Example: real square roots ***) fun nextApprox (a,x) = (a/x + x) / 2.0; fun findRoot (a, x, espilon) = let val nextx = (a/x + x) / 2.0 in if abs (x-nextx) < espilon*x then nextx else findRoot (a, nextx, espilon) end; fun sqroot a = findRoot (a, 1.0, 1.0E~10); sqroot 2.0; it*it; sqroot 9.0; fun sqroot a = let val acc = 1.0E~10 fun findRoot x = let val nextx = (a/x + x) / 2.0 in if abs (x-nextx) < acc*x then nextx else findRoot nextx end in findRoot 1.0 end; sqroot 1234.56789; it*it; (*EXERCISE. Compute reciprocals using Newton-Raphson. Initial approximation needs to be fairly good.*) fun recipNext d x = x*(2.0 - x*d); (**** LECTURE 3: Estimating Costs in the Limit ****) (*exponential runtime*) fun nthApprox (a,x,n) = if n=0 then x else (a / nthApprox (a,x,n-1) + nthApprox (a,x,n-1)) / 2.0; fun nsumsum n = if n=0 then 0 else nsum n + nsumsum (n-1);