haskell代写: CS 440: Programming Languages and Translators

程序代写 CS代考 / Haskell代写代考

Illinois Institute of Technology

Homework 4

4/2 p.3

Instructions

Haskell Programming

CS 440: Programming Languages and Translators Due Wed Apr 4, 11:59
No late assignments — Solution will be posted Thu Apr 5

  • You can work together in groups of ≤ 4. Submit your work on Blackboard. Submit one copy. Include the names and A-IDs of everyone in the group on that copy. Submit under the name of one person in the group (doesn’t matter who).
  • All the questions refer to Haskell programs; we’ll run them on fourier to test them. Write your answers into a *.hs file and submit that. If necessary, write non-code items as comments {- possibly over multiple lines -}

    Questions [100 points total]

  1. [4 = 4 * 1 points] Give the (polymorphic) types of the following functions. (Figure them out yourself first, then enter them into ghci to make sure you’re right.) It’s ok to uniformly rename variables (e.g. a -> [a] and b -> [b] are equivalent).

    :{
    f = \x -> [x]
    g = \x y z -> (x:y, y:z) S f g x = f x (g x) Kxy=x
    :}

  2. [3 points] Rewrite the following binding to make it syntactically correct. (Keep the num and denom names — don’t just start with 17 mod 3 and continue on from there.) 
          :{
      X = num mod denom

:}

where
num = 17

denom = 3

3. [5 points] Fix the incorrect definition of function flipcase below. It’s supposed to take a character and flip it from lowercase to uppercase (or vice versa). If the character is not a letter, flipcase should just return its argument. E.g., we should get

      map flipcase "abCDE0123;?!" == "ABcde0123;?!"

If you’re working in ghci, you should add the module Data.Char using :m + Data.Char at the ghci prompt before trying to define flipcase. (Or be forced to type in names like Data.Char.isLower.) Don’t use if-else expressions: Practice using patterns and guards.

CS 440: Programming Languages and Translators – 1 – © James Sasaki, 2018

Illinois Institute of Technology

Homework 4

      :{
      flipcase (isLower c) -> toUpper c

         | isLower c = toUpper c

         otherwise = c
      :}
  1. [10 points] Give the definition of a function nmap n f xs that works like map f xs but instead of calling f once on each member of xs, it does n calls of f. E.g., nmap 2 sqrt [16.0, 81.0] = [2.0, 3.0], since 16 = (2 ^ 2) ^ 2 and 81 = (3 ^ 2) ^ 2. Ifn≤0,nmapshould just returnxs.
  2. [10 = 2 + 8 points]
    1. Give a one-sentence description of what f defined below does. (Try running it on some data.)
    2. Rewrite f so that it doesn’t use dot (function composition) but does use an unnamed lambda. 
                  :{
            f :: ??? -- fill in the type of f, too
            f x = length . filter (== x)  -- change this definition
            :}
  3. [7 points] Using reverse, tail, and function composition, write a definition for an init2 function that behaves like init. You don’t need recursion; the answer is one line long. In Haskell, function composition is done with infix dot (as in f . g).
  4. [10 points] Write a routine isAllDigits str that returns True iff the string is nonempty and all the characters in the string are decimal digits. You can use the Data.Char function isDigit c to see if a character is a digit. You can write your function recursively if you want, but it’s not required — check out the Data.List routines map and and. (In ghci, you’ll want to use :m + Data.Char Data.List)
  5. [20 points] The datatype Tree a below defines a binary tree with values of type a attached to the leaves and no values attached to interior nodes: 
                :{
            -- we'll use :^: as an infix operator for constructing trees
            infixl :^:
            data Tree a = L a | Tree a :^: Tree a deriving (Eq, Show)
            sampleTree = L 1 :^: L 2 :^: (L 3 :^: L 4)
            :}

    Write a function frontier :: Tree a → [a] that returns all the values of the leaves of a tree, in preorder. E.g., frontier sampleTree = [1,2,3,4].

  6. [31 = 6 + 25 points]

CS 440: Programming Languages and Translators – 2 – © James Sasaki, 2018

Illinois Institute of Technology Homework 4

  1. What are the two differences between the datatype declarations below? Discuss briefly and give a short example of each difference. 
            :{
        data QueueOp a = ENQ a | DEQ
        data QueueOp a = ENQ a | DEQ deriving (Eq, Show)
        :}
  2. We’re going to model a queue of values, a list of queue operations, and a list of the results of the operations. First, take the second definition of QueueOp above and add the following type declarations. 
            :{
        type Queue a = [a]
        type QInstrs a = [QueueOp a]
        type QResults a = [a] -- change [4/2]
        :}

We’re aiming for an evaluation function eval qInstrs that starts with an empty queue and applies a sequence of queue operations to it. It should return a pair: the queue that remains at the end and a list of the dequeue results. E.g., the code below should eventually set test = ([3], [1,2]).

  :{
  testInstrs = [ENQ 1, DEQ, ENQ 2, ENQ 3, DEQ]
  test = eval testInstrs
  :}

To do its work, eval calls a helper routine eval’: The call eval’ queue qInstrs qResults should apply the queue instructions to the given queue, appending dequeue results as it goes. For example,
eval’ [2,3] [DEQ] [1] should yield ([3], [1,2]) because dequeueing [2,3] results in a queue of [3], and the dequeue operation yields 2, which gets added to the partial results [1] to get [1,2].

  -- [changes 4/2]

  :{
  eval :: QInstrs a -> (Queue a, QResults a)
  eval' :: Queue a -> QInstrs a -> QResults a -> (Queue a, QResults a)

  eval qinstrs = eval' [] qinstrs [] where
  eval' queue [] results = (queue, results)
  :}

The eval routine above is actually complete; you need to add extend eval’ to handle ENQ and DEQ. Note: Dequeueing an empty queue should cause an error “Dequeue of empty queue” (or some such message).

CS 440: Programming Languages and Translators – 3 – © James Sasaki, 2018

Related Posts