CSE 341, Winter 2005, Assignment 3Due: Thursday, February 3, 10:00 PMLast updated: 01-29-05This assignment consists of two parts; the first deals with a simple list manipulation language, and the second usesclosures in the context of calculus. In total, there are 7 functions to implement that aren’t trivial uses of other functions.Start early and make sure you are comfortable with closures and higher-order functions. The sample solution is about100 lines long.Part IList manipulation languageWe will define a small language for performing operations on lines of dominoes. Each operation acts on a pair oflines. You will use the following definitions in your solutions. A bone is represented as it was in homework 1 and 2:type bone = int * intA line is simply a list of bones:type line = bone listThere are several operations we will define on a pair of lines. We can take the first bone of the left line and push itonto the front of the right line and vice versa (think “stack”), we can swap the first bones in the lines, and we can applysome arbitrary function to the first bone in either the left or right line and replace it with the result. Formally:datatype lineop =PushRight (*Take element from left, push it onto right *)| PushLeft (*Take element from right, push it onto left*)| SwapFirst (* Take first bone from each line and swap them*)| ApplyRight of bone -> bone (*Apply function to first bone on the right*)| ApplyLeft of bone -> bone (*Apply function to first bone on the left*)A program is a list of operations, applied in order to the two lines:type lineprog = lineop listUsing these definitions, do the following:1. Write a function lineop_func that takes a lineop lop and returns a function which, when invoked with a pairof lines, returns the pair of lines that result from applying the operation lop. An operation that would attemptto manipulate (or remove) the first bone in an empty line should raise the exception Empty. For example,PushRight on the pair ([],[(1,0)]) should raise an exception, because there is no bone in the left line tomove to the right. PushLeft on the same pair is legal.12. Write a function lineprog_func that takes a lineprog prog and returns a function which, when invoked with apair of lines, returns the pair of lines that result from applying the operations in prog in order. For an elegantsolution, use SML higher-order library functions such as List.map and List.foldl and the built-in functioncomposite operator o (that’s a small letter ’o’). The sample solution is only 1 line. Solutions that work but donot make use of higher order functions will lose style points.3. Write a function pushn_right_safe that takes an integer n and returns a lineprog which pushes the first n bonesin the left line onto the right line, but also ensures that the sides of the n bones that were originally touching arestill touching afterwards. The bones that are moved will end up in reverse order; you do not have to attempt toprevent this from happening.4. Write a function pushn_right_block that takes an integer n and returns a lineprog which pushes the first nbones in the left line onto the right line as a block. That is, the bones should end up in the same order theystarted in. Keep in mind that simply doing n PushRight operations will reverse the order of the bones, so youmust somehow prevent this. Sitting down with pencil and paper and working out an algorithm before you begincoding is advisable. Use helper functions and the list append operator @ to make your life easier.5. Write a function lineprog_mirror which takes a lineprog prog and returns another lineprog which performsthe mirror image of the operations in prog; that is, an operation that operates on the left line must instead operateon the right, and vice versa.6. Use lineprog_mirror to define two more functions, pushn_left_safe and pushn_left_block, which workas you would expect. Use val bindings instead of fun bindings, and don’t introduce anonymous functions withfn. Hint: you will need to use a higher-order function.7. (Extra credit) Write a function lineprog_optimize which takes a lineprog prog and returns another lineprogwhich performs the same transformation on a pair of lines, but contains fewer operations. It may return alineprog of the same size if no optimization is possible, but the size of the lineprog must not increase. Try todetect and simplify as many optimizable patterns as possible.Sample output- lineprog_func (pushn_left_block 3) ([],[(1,2),(2,3),(3,4),(0,0)]);val it = ([(1,2),(2,3),(3,4)],[(0,0)]) : bone list * bone list2Part IICalculusYou will write two functions (and a third trivial one) that calculate the derivative or integral of a function operating onreal numbers. The algorithms to do this numerically will be presented here in case your calculus is rusty.Recall that the derivative of a function is the slope of the function at a particular point, defined as:f0(x) =ddxf(x) =lim∆x → 0f(x+ ∆x) − f(x)∆xTo approximate a derivative numerically, you can simply choose some ∆x close to 0 instead of taking the limit.Approximating an integral is somewhat more complicated:For a function f(x) over the interval [a, b], divide the interval into n subintervals of width ∆x =b−an, and choose apoint from each interval xi. The definite integral is:Zbaf(x)dx =limn → ∞n∑i=1f(xi)∆xAs n approaches infinity, the result approaches the true integral, so we can pick a very large n, iterate throughvalues of x between a and b in increments of ∆x, find the value of f at each x and multiply by ∆x, and then sum theterms. There are other methods, such as the trapezoid method, that give more accurate results; if you know them, youmay use them instead of the algorithm here. The definition of an indefinite integral is simple once the definite integralis defined. Let F(b) be the indefinite integral of f(x). It is defined as:F(b) =Zf(x)dx =Zb0f(x)dxWe can define some useful constants to make writing the functions easier:val bigNumber = 100000.0val smallNumber = 1.0 / bigNumberA module to allow you to display graphs of your functions has been provided. This is a useful visualization tool toensure that your functions are working properly. To use it, you first need to import the provided code:use "hw3-provided.sml"To print a graph to the screen, simply do:Grapher.graph (f)Where f is a function of type real -> real.1. Write a function derivative that takes a function f of type real->real and returns a
View Full Document
Unlocking...