2023 Sem I Final Exam B

Definitions: a “higher order function” is a function that takes another function as input. Chapter 6 contains the main discussion of these functions.

Locate

1. The Locate class has two methods loc and moveto.

   • The method loc that takes in a single thing in the class and puts out a pair of integers (Int,Int).
   • The moveto method takes in an (Int,Int) and an item in the class, and puts out an item of the same type.

   Write the class declaration for Locate.

2. Write code so that Block is in the Locate class

    data Block = Block (Int,Int)
   

Inexact

The definition of Inexact below is intended to tag results with a plus or minus tolerance (like in science class).

data Inexact a = Inexact {val :: a, tolerance :: Double}

3. Write code to make an inexact point ept at $(3.5, 7.03)$ with a tolerance of $\pm 0.05$.

    type Point = (Double, Double)
   

4. Write code to make Inexact into a Functor.

Stone Age and Beyond

The substitutor function sbt, takes in a list of ordered pairs and one integer x-coordinate that is supposed to be changed to another.

sbt :: Int -> Int -> [(Int, Int)] -> [(Int,Int)]
sbt origval newval xs = []
ex_sbt = sbt 10 5 [(10,15),(30,10),(10,40),(40,15)] ==
                  [( 5,15),(30,10),( 5,40),(40,15)]

5. Write substitutor using nothing but recursion, pattern matching, and basic functions from early in the book. Avoid fst, snd, head, and tail for full credit.

6. Write the same function using a higher order function.

Random

A Trap is a block that triggers other blocks tagged with the same string to fall. Trap is also in the Locate class, but you do not need to write that code.

    data Trap = TrapBlock String (Int. Int)
    data TrapGame = TrapGame {myrng :: StdGen, traps :: [Trap]}

7. The function newtrap :: String -> TrapGame -> TrapGame that adds a new trap with the given name to the game. The x and y coordinates for the trap should be random numbers from 4 through 20.

    before_tg = TrapGame ... -- code omitted
    before_check = (traps tg) == [TrapBlock "FireArrow" (4,8)]
    after = newtrap "PressurePad" tg
   

   Write the newtrap function.

Misc

8. The uncurry function has a signature

    uncurry :: (a->b->c) -> (a,b) -> c
   

   1. Briefly explain the meaning of this signature.
   2. Give an example of one way this function could work.

9. In this question, ideally you will demonstrate you understand how to use higher order functions (LYAH, Chapter 6).

   The function below takes in two positive integers $(r,s)$ with $s$ less than $r$ and produces a Pythagorean triple.

    p2A :: (Integer, Integer) -> (Integer, Integer, Integer)
    p2A (r,s) = ((r-s)*(r+s), 2*r*s, r*r+s*s)
   
    [(3,4,5),(6,8,10),(5,12,13),(8,15,17),(12,16,20),(7,24,25), ...]
   

   Using that function, do each of the following:

   1. List some Pythagorean triples: Create a list pB that has p2A applied to every integer value of $1 \le r \le 10$ and $1 \le s < r$.

   2. (p2B) Some of the Pythagorean triples come out not in ascending order, like $r=4$ paired with $s=1$ gives (15,8,17). Mathematically, the third element of the ordered triple is always greater than either of the other two. Write a function fixp2 that will put a triple in ascending order.

   3. Show how to use each of the approaches listed below to apply the fixp2 function to the elements of p2.

      1. list comprehension
      2. advanced function from chapter 6

   4. (p2C) Some of the triples have a greatest common divisor that is not 1. We want to get rid of those. Do this with a higher order function.

      A reminder that the signature of gcd is:

       gcd :: Integer -> Integer -> Integer
      

   5. Next time ask students to write the gcd function as well.

Programming

10. (diagonalRun) A diagonal run is a list of coordinates $(x_i, y_i)$ so that $x_{i+1} = 1 + x_i$ and similarly $y_{i+1} = 1 + y_{i}$. In the coordinate plane these would be points along a line of slope one.

    Given a list of ordered pairs of ints, find the length of the longest diagonal run.

Examples:

easy = [(0,0),(1,1),(2,2),(3,3),(4,4)] ++ [(1,-2),(2,-1),(3,0)]
easy_result = (diagonalRun easy == 5)

hard = [(4,4),(2,-1),(0,0),(1,-2),(1,1),(3,0),(2,2),(3,3)]
hard_result = (diagonalRun hard == 5)