STEP 2: Metrics A metric function is a function ( ),m x y that takes two arguments x and y and defines the distance between x and y. To be a metric function, m must satisfy 1. ( ), 0m x y ! 2. ( ), 0m x y x y= ! = 3. ( ) ( ), ,m x y m y x= 4. ( ) ( ) ( ), , ,y m x z m x y m y z! " + The following are metrics: ( )0,1discretex ym x yotherwise=!="# ( )1 1, max , ,square n nm x y x y x y! "= # #$ %K (a) In LISP write the functions metric-discrete and metric-square. These functions should work for: i. Real-valued numbers x and y. ii. Lists (of equal length) x and y (representing points). (b) [ DIFFICULT ]. Given two metrics m1 and m2 the function ( ) ( ) ( )1 2, , ,addm x y m x y m x y= + is also a metric. Write a function that takes two metric functions as arguments and returns a new metric function metric-add. STEP 3: Tree Flattening A binary tree is a data structure often used in computer science and graph theory. It can be defined recursively as follows: A binary tree contains a root node, and two children, the right child and the left child, where each child is a binary tree itself. We could represent a binary tree in LISP using nested list. For example, the following tree would be represented as (1 (2) (5 (3) (4))) Note here that the first element of the list is the root node, followed by the right sub-tree(as a list), and the left sub-tree(also a list). Each of the subtree is represented in the same manner using a nested list. Now you need to write a recursive function called tree2list that convert a tree into a flattened list. For example, in the above case, the result of the tree2list function will be (1 2 5 3 4). 1 2 3 5 4STEP 4. Center of Mass 1. Create a new (Cartesian) point type using defstruct with fields x and y. 2. Write a function that takes a list of points and returns a list of their x coordinates using mapcar. 3. The center of mass (xcm, ycm) of a set of n points is the point defined as ! xcm=xii=1n"nycm=yii=1n"n Write a function that takes a list of points and returns the center of mass (as a point). 4. Create a second point type with fields r and theta that defines a point in polar coordinates. 5. Write a function that will reflect either type of point over the x-axis. For Cartesian points, multiply y by -1. For polar coordinates, multiply theta by -1.SOLUTIONS Step 2: Metrics ; For the discrete metric, we check for equality (defun metric-discrete (x y) (if (equalp x y) 0 1)) ; For the square metric, we test whether our arguments are values or lists. ; With two values, we compare them using the abs-dist helper function. ; With two lists, we generate a list of abs-dist values and then apply the ; max function. NOTE: You must use 'apply' because 'max' does not take ; a list as an argument. (defun metric-square (x y) (if (atom x) (abs-dist x y) (apply #'max (mapcar #'abs-dist x y)))) (defun abs-dist (x y) (abs (- x y))) ; To create a new metric function from two component functions, we use ; 'lambda'. Thus, we create a new, unnamed function that adds the ; results of the functions we pass in. defun metric-add (m1 m2) #'(lambda (x y) (+ (funcall m1 x y) (funcall m2 x y)))) ( Step 3: Tree Flattening ; Each sub-tree in a tree will either be a single node (e.g. '(2) ) or three nodes ; (e.g. '(4 (5) (6)). With three nodes, we append each together to form a ; flat list. With one node, we want to keep it the way it is. However, if ; we append nil, nothing will change. Therefore, we are always safe treating ; each sub-tree as having three parts. ; Note: cadr and caddr will not error on lists of length one because ; (car nil) = nil and (cdr nil) = nil in Lisp. (defun tree2list (tr) (if (null tr) '() (append (list (car tr)) (tree2list (cadr tr)) (tree2list (caddr tr))))) ; Or if you're shy about long strings of a's and d's... (defun tree2list (tr) (if (null tr) '() (append (list (first tr)) (tree2list (second tr)) (tree2list (third tr)))))Step 4: Point Structures ; 1. A homework freebie... (defstruct Point x y) ; 2. We use mapcar with the access function point-x. (defun list-all-x (l) (mapcar #'point-x l)) ; 3. We make a new point with our constructor function, summing over x and y ; values. l is a list of points. (defun center-of-mass (l) (let ((n (length l))) (make-point :x (/ (apply #'+ (mapcar #'point-x l)) n) :y (/ (apply #'+ (mapcar #'point-y l)) n)))) ; 4. Polar point (defstruct Polar-point r theta) ; 5. Method declarations for reflection are going to use set-f ; Note that setf returns only the value it changed, not the structure ; containing that value. Thus, we must explicitly return p. (defmethod reflect-x-axis ((p point)) (setf (point-x p) (* -1 (point-x p))) p) (defmethod reflect-x-axis ((p polar-point)) (setf (polar-point-theta p) (* -1 (polar-point-theta p)))
View Full Document
Unlocking...