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:
\ x -> x+1
)
map
, filer
, etc.)
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,
Card
from the homework)- recursive algebraic types (e.g.,
Expr
from class)- polymorphic recursive algebraic types (e.g.,
(BTree a)
from class and homework)
Some practice questions:
(fun1 (True,'w')
returns 'w'
and
(fun1 (False,'q')
returns 'q'
.
fun1 __________ = ans
(fun2 ('a',[10,13,0]))
returns 10
and
(fun2 ('z',[6,91,45,73]))
returns 6
.
fun2 __________ = ans
(fun3 [1..10])
returns 4
and
(fun3 "wompus")
returns 'p'
.
fun3 __________ = ans
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]
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]
Use foldr
or else map
and 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 0
.
(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 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]
.
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))
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
.)
properSub 4
[five, six]
Three
(\ c -> Four c False)
map two
(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
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.
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 Empty
.
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 aTree1
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"
.
n
points to the leftmost child of n
in the general tree (if there is no such child, the left
tree is null).
n
points to the sibling
of n
that is immediately to the right
of n
in 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 aTree2
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 functiontrans1to2 :: Tree1 a -> Tree2 athat given aTree1
, translates it to the equivalentTree2
. For example,(trans1to2 t1)
should returnt2
.
Problem d. Write a Haskell functiontrans2to1 :: Tree2 a -> Tree1 athat given aTree2
, translates it to the equivalentTree1
. For example,(trans2to1 t2)
should returnt1
.