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:
.(function composition) and
You should particularly be familiar with:
You should understand the following notions and be able to provide a definition and/or example:
\ x -> x+1)
Here you should understand that they provide a mechanism for overloading, and you should know what a type definition such as
Eq a => a -> [a] -> [a]means, but I won't ask you to define instances or recite details about classes)
In particular, you should be able to program with them, and you should be able to use them to define a new type given certain constraints.
I will expect you to be able to work with the various forms of algebraic types. That is:
- non-recursive algebraic types (e.g,
Cardfrom the homework)
- recursive algebraic types (e.g.,
- polymorphic recursive algebraic types (e.g.,
(BTree a)from class and homework)
Some practice questions:
fun1 __________ = ans
fun2 __________ = ans
fun3 __________ = ans
insert:: Int -> [Int] -> [Int]that takes an integer
n, followed by a list
msof integers in ascending order (i.e., smallest to biggest) and returns the list obtained by inserting
ninto its rightful place in
ms. (You can assume that the list
msis in the proper order. Also, no you may not use
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]
rotate :: Int -> [a] -> [a]such that
(rotate n xs)takes the list
xsand 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]
foldr or else
sum to write a Haskell function
sumSquares :: [Int] -> Intsuch that
(sumSquares ns)returns the sum of the squares of the numbers in
ns. For example,
(sumSquares )should return
(sumSquares [1..3])should return
14(=1*1 + 2*2 + 3*3).
Write a Haskell function
zeros :: (Int -> Int) -> Int -> [Int]such that
(zeros f n)returns the list of numbers between 0 and
freturns 0. If
nis negative, then
is returned. For example,
(zeros (\x -> x-3) 10)should return
(zeros (\x -> (x-2)*(x-4) 6)should return
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
xoccurs. For example,
(positions 10 [10,20,30])should return
(positions 4.3 [-9.2, 4.3, 2.1, 4.3])should return
(positions 'x' "zampf")should return
positions x xs = map _____ (filter _______ (zip ________ xs))
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
(\ c -> Four c False)
(two . one)
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 asuch 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 / \ / \ / \ / \ * * * * * * * *
data Card = Std Suit Rank | Colon CRank data Suit = Clubs | Diamonds | Hearts | Spades data Rank = Ace | Face Char | Spot Int data CRank = Grand | Royal | LittleFor example,
Std Hearts (Face 'Q'),
Std Diamonds (Spot 8), and
Caveat: None of these types belongs to the
class, so you will need to use pattern
matching (instead of
==) for the questions that follow.
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 -> Intsuch 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.
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,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.
each King as 3,
each Queen as 2,
each Jack as 1, and
all other cards count 0.
Write a Haskell function
highCardPts :: [Card] -> Intsuch 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.
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
One can use a binary tree prepresentation for general trees as follows:
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 functionpreFlatten1 :: Tree1 a -> [a]that given a
Tree1t, 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
npoints to the leftmost child of
nin the general tree (if there is no such child, the left tree is null).
npoints to the sibling of
nthat is immediately to the right of
nin the general tree.
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)))))) NullN.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 functionpreFlatten2 :: Tree2 a -> [a]that given a
Tree2t, 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
Problems c and d below are way too hard for this test, but are good puzzles
Problem c. Write a Haskell functiontrans1to2 :: Tree1 a -> Tree2 athat given a
Tree1, translates it to the equivalent
Tree2. For example,
(trans1to2 t1)should return
Problem d. Write a Haskell functiontrans2to1 :: Tree2 a -> Tree1 athat given a
Tree2, translates it to the equivalent
Tree1. For example,
(trans2to1 t2)should return