This is a makeup problem for Quiz #1. You can optionally upload your solution on Gradescope to this problem, and we will use your score on this problem in place of your score on Problem #2 on Quiz #1. We will not accept regrade requests for this question, and we will use whichever score is higher between your original score on Problem #2 and this new makeup problem.

Logistics:

  • Due date: Friday March 15
  • Turn in on Gradescope
  • Starter code: here
  • Upload a single file called code.rkt to Gradescope. Your upload should be valid Plait: be sure your upload runs in Dr Racket without errors. Use the provided starter code.
  • This is to be completed on your own. Please do not consult with classmates. You are permitted to use the course notes and Dr Racket. Only ask questions relating to the quiz as private Piazza questions.
  • Note: The autograder score is not your final score.

Problem 2: Fix the code [25 Points]

A Pokemon is a datatype that is either is a final evolution or a pre-evolution. A pre-evolution evolves into another Pokemon; the Pokemon it evolves into is called evo. Each Pokemon has its name as an additional data element:

(define-type Pokemon
  (pre-evo (name : String) (evo : Pokemon))
  (final-evo (name : String)))

For example, for a Pokemon (pre-evo "charmander" (pre-evo "charmeleon" (final-evo "charizard"))), we would say charmeleon is a pre-evolution of charizard, but charmander is not a pre-evolution of charizard.

A Pokedex is a list of Pokemon. You can assume that all Pokemon have distinct names in the Pokedex:

(define-type-alias Pokedex (Listof Pokemon))

Your friend wants to design a function get-pre-evo of type (String (Listof Pokemon) -> Pokemon)) that takes arguments pkmn and dex that returns the pokemon in dex that is a pre-evolution of pkmn, or raises a NoPkmn error if there is no such Pokemon. They have the following implementation which isn’t doing what they expect, and they ask your for help debugging their code:

(define (get-name p)
  (type-case Pokemon p
    [(pre-evo n evo) n]
    [(final-evo n) n]))

; buggy implementation: fix this
(get-pre-evo : (String (Listof Pokemon) -> Pokemon))
(define (get-pre-evo pkmn dex)
  (type-case Pokedex dex 
    [empty (error 'NoPkmn "Not found")]
    [(cons p l) (if (equal? (get-name (pre-evo-evo p)) pkmn) p (get-pre-evo pkmn l))]))
  1. (5 Points) Give test cases for which the above implementation of get-pre-evo violates the provided specification. There many be more than one problem that you can identify; you should provide a test case for each problem. Include a brief comment above your test case that quotes directly from the problem description and explains how your test shows that get-pre-evo does not match the specification. We will grade your solution based on test coverage: you should provide one test for each kind of failing input.
  2. (20 Points) In code.rkt, fix get-pre-evo so that it is correct. It should pass all of your provided test cases in (1) and match the above specification. We will grade your solution based on the fraction of our internal test cases that your solution passes. You may need to define a helper function.

Note: Read this problem carefully. It is similar to last time, but different in some subtle ways.