CIS 623   —   SPRING 2018

INFORMATION ON EXAM 2

Version 3: Wed Feb 28 12:12:16 EST 2018

Typo corrections in RED.


When: Wednesday, March 7 in class.

How: Closed book, closed notes.

Coverage: Learn You a Haskell for Great Good Chapters 1–6 and 8.

You should be familiar with all the topics from Exam 1.

Additionally, you should be familiar with the following Haskell functions/constructs:

  • concatMap,   dropWhile,   filter,   flip,   foldl,   foldl1,   foldr,   foldr1,   map,   takeWhile,   zip,   zipWith  
  • . (function composition) and $ (function application)

    You should particularly be familiar with:

    You should understand the following notions and be able to provide a definition and/or example:

    Additionally, you should be familiar with the following Haskell functions/constructs:

    Some practice questions:


    1. Fill-in the blanks
      1. Fill in the blank with a pattern such that
        • (fun1 (True,'w') returns 'w' and
        • (fun1 (False,'q') returns 'q'.
          fun1 __________ = ans
      2. Fill in the blank with a pattern such that
        • (fun2 ('a',[10,13,0])) returns 10 and
        • (fun2 ('z',[6,91,45,73])) returns 6.
          fun2 __________ = ans
      3. Fill in the blank with a pattern such that
        • (fun3 [1..10]) returns 4 and
        • (fun3 "wompus") returns 'p'.
          fun3 __________ = ans

      [show answers]


    2. Write a Haskell function
       insert:: Int -> [Int] -> [Int]
      that takes an integer n, followed by a list ms of integers in ascending order (i.e., smallest to biggest) and returns the list obtained by inserting n into its rightful place in ms. (You can assume that the list ms is in the proper order. Also, no you may not use sort.)
        For example:
        Main> insert 5 [2, 4, 6, 8]
        [2, 4, 5, 6, 8]
      
        Main> insert 0 [2, 4, 6, 8]
        [0, 2, 4, 6, 8]
      [show answers]
    3. Write a Haskell function
        rotate :: Int -> [a] -> [a]
      such that (rotate n xs) takes the list xs and rotates it n-many places to the left. (You may assume that n > 0.) For example, the function should behave as follows:
        Main> rotate 0 [10,20,30,40,50,60,70,80] 
        [10,20,30,40,50,60,70,80]
      
        Main> rotate 1 [10,20,30,40,50,60,70,80] 
        [20,30,40,50,60,70,80,10]
      
        Main> rotate 1 []
        [] 
      
        Main> rotate 3 [10,20,30,40,50,60,70,80] 
        [40,50,60,70,80,10,20,30]
      
        Main> rotate 17 [10,20,30,40,50,60,70,80] 
        [20,30,40,50,60,70,80,10]
      
      [show answers]
    4. Short answers
      1. Use foldr or else map and sum to write a Haskell function

          sumSquares :: [Int] -> Int
        such that (sumSquares ns) returns the sum of the squares of the numbers in ns. For example,
        • (sumSquares []) should return 0.
        • (sumSquares [1..3]) should return 14 (=1*1 + 2*2 + 3*3).

      2. Write a Haskell function

          zeros :: (Int -> Int) -> Int -> [Int]
        such that (zeros f n) returns the list of numbers between 0 and n on which f returns 0. If n is negative, then [] is returned. For example,
        • (zeros (\x -> x-3) 10) should return [3].
        • (zeros (\x -> (x-2)*(x-4) 6) should return [2,4].

      3. Fill in the blanks in the following to define a function

         positions :: (Eq a) => a -> [a] -> [Int]
        so that (positions x xs) returns the positions in the list xs (counting from 0) that the value x occurs. For example,
        • (positions 10 [10,20,30]) should return [0].
        • (positions 4.3 [-9.2, 4.3, 2.1, 4.3]) should return [1,3].
        • (positions 'x' "zampf") should return [].
          positions x xs = map _____ (filter _______ (zip ________ xs))

      [show answers]


    5. Suppose we have the following definitions.

        one :: (a,b,c) -> a 
        one (x,y,z) = x 
      
        two :: [a] -> a 
        two (y:ys) = y 
      
        data Item = Three Int 
                  | Four Char Bool 
      
        five :: Int -> Int 
        five x = x + 5
      
        six :: Int -> Int 
        six x = 6
      
        properSub :: Int -> Int -> Int 
        properSub x y = max 0 (x-y)
      
      Give the types of the following expressions. (E.g., (one (True,'y',17)) has type Bool.)
      1. properSub 4

      2. [five, six]

      3. Three

      4. (\ c -> Four c False)

      5. map two

      6. (two . one)

      [show answers]


    6. A binary tree is either an empty tree or a node with two children, each of which is also a binary tree. We can define (polymorphic) binary trees in Haskell using the following type definition:

      data BTree a = Empty | BNode a (BTree a) (BTree a) 
                     deriving (Show) 
      

      Write a Haskell function

      mirror :: BTree a -> BTree a 
      such that (mirror tree) reverses the tree tree by swapping each node's left and right children. In pictures:
               4       <=mirror=>        4                  
             /   \                       /   \                
            /     \                     /     \                  
           2       5                   5       2                  
          / \     / \                 / \     / \
         /   \   *   *               *   *   /   \
        1     3                             3     1 
       / \   / \                           / \   / \
      *   * *   *                         *   * *   *
      

      [show answers]


    7. The card game Bridgette—a two-player variant of Bridge—uses a standard 52-card playing deck, plus three additional cards: the Grand Colon, the Royal Colon, and the Little Colon. The game also uses the following terminology: face cards are Kings, Queens, and Jacks; spots are cards numbered two through ten. Thus, the collection of allowable cards can be represented by the following algebraic data types:
         data Card  = Std Suit Rank  | Colon CRank 
         data Suit  = Clubs | Diamonds | Hearts | Spades 
         data Rank  = Ace | Face Char | Spot Int 
         data CRank = Grand | Royal | Little
      
      For example,
      • the Queen of Hearts is represented as Std Hearts (Face 'Q'),
      • the Eight of Diamonds as Std Diamonds (Spot 8), and
      • the Royal Colon as Colon Royal.

      Caveat: None of these types belongs to the Eq class, so you will need to use pattern matching (instead of ==) for the questions that follow.

      The problems

      1. After cards are initially dealt to each player, an additional card is placed face up. This card determines how many extra cards the nondealer receives: 0 for a colon, 1 for a Diamond, 2 for Heart, 3 for a Spade, and 4 for a Club. Thus, if the card that's placed up is the Eight of Diamonds, the nondealer receives one additional card.

        Write a Haskell function

         receives :: Card -> Int
        such that (receives card) returns the number of extra cards the nondealer receives for the face-up card. For example, (receives (Std Hearts (Face 'Q'))) should return 2.

      2. One way is to determine the relative strength of a Bridgette hand is to count the number of high-card points:

        each Ace counts as 4,
        each King as 3,
        each Queen as 2,
        each Jack as 1, and
        all other cards count 0.
        For example, if a hand contains two Aces, a King, three Queens, and various spot cards, then it has (2× 4) + (1 × 3) + (3× 2) = 17 high-card points.

        Write a Haskell function

         highCardPts :: [Card] -> Int
        such that (highCardPts hand) returns the number of high-card points in hand. For example,
        highCardPts [Std Spades (Face 'J'), Std Clubs (Spot 10), 
                     Colon Grand, Std Spades Ace, Std Hearts (Face 'J')]
        should return 6.

        [show answers]


    8. Some more tree recursion problems A general tree is a rooted tree in which nodes can have any (finite) number of children. For example, the tree on the left in the figure below.

      Here is a possible Haskell representation for such trees.
       data Tree1 a = Empty | Branch a [Tree1 a]          
                      deriving (Show,Eq)
      For example, the left tree in the figure is represented by:
      t1 = Branch 'a' [Branch 'b' [Branch 'h' [Branch 'n' [],
                                               Branch 'o' []],
                                   Branch 'i' [],
                                   Branch 'j' []],
                       Branch 'c' [],
                       Branch 'd' [],
                       Branch 'e' [Branch 'k' [Branch 'p' []],
                                   Branch 'l' [Branch 'q' []]],
                       Branch 'f' [],
                       Branch 'g' [Branch 'm' []]]
      N.B. In a (Branch x [t1,...,tk]), none of the ti's should be Empty.

      Problem a. In a preorder traversal of a general tree one visits the root node of a subtree and then does a preorder traversal of each of the node's subtrees – from left to right. Write a Haskell function
      preFlatten1 :: Tree1 a -> [a]
      that given a Tree1 t, builds the list of labels of nodes in the order the nodes would be visited in a preorder traversal. For example, (preFlatten1 t1) should return "abhnoijcdekplqfgm".
      One can use a binary tree prepresentation for general trees as follows:
      • The left tree of a node n points to the leftmost child of n in the general tree (if there is no such child, the left tree is null).
      • The right tree of a node n points to the sibling of n that is immediately to the right of n in the general tree.
      The binary tree in the above figure represents the general tree on the left. Here is a possible Haskell representation for such trees.
       data Tree2 a = Null  | Node a (Tree2 a) (Tree2 a)  
                      deriving (Show,Eq)
      For example, the left tree in the figure is represented by:
      t2 = Node 'a' (Node 'b' 
                     (Node 'h' 
                      (Node 'n' Null (Node 'o' Null Null)) 
                      (Node 'i' Null (Node 'j' Null Null))) 
                     (Node 'c' Null 
                      (Node 'd' Null 
                       (Node 'e' 
                        (Node 'k' (Node 'p' Null Null) 
                         (Node 'l' (Node 'q' Null Null) Null)) 
                        (Node 'f' Null 
                         (Node 'g' (Node 'm' Null Null) Null)))))) 
                    Null 
      N.B. If (Node x tl tr) is the root of the entire tree, then tr==Null (i.e., it has no siblings).

      Problem b. Write a Haskell function
      preFlatten2 :: Tree2 a -> [a]
      that given a Tree2 t, builds the list of labels of nodes in the order the nodes would be visited in a preorder traversal of the general tree represented by t. For example, (preFlatten2 t2) should return "abhnoijcdekplqfgm".

      Problems c and d below are way too hard for this test, but are good puzzles


      Problem c. Write a Haskell function
      trans1to2 :: Tree1 a -> Tree2 a
      that given a Tree1, translates it to the equivalent Tree2. For example, (trans1to2 t1) should return t2.

      Problem d. Write a Haskell function
      trans2to1 :: Tree2 a -> Tree1 a
      that given a Tree2, translates it to the equivalent Tree1. For example, (trans2to1 t2) should return t1.

      [show answer]


    9. Additional List and Tree Questions
      Look Here.

    Back to the CIS 252 Homepage
    Jim Royer /