Question 1
Part 1: Implementing recursive functions
Consider the following definition of a binary tree data type that stores elements only in “nooks”.
data Tree a
= Nook a (Tree a)
| Node (Tree a) (Tree a)
| Leaf
Here are some examples of trees defined using this data type.
ex1 :: Tree Int
ex2 :: Tree Int
ex3 :: Tree String
ex3 = Nook “hey” (Nook “adora” End)
Define the following function nooks, which returns the number of nooks in a tree. Be sure to include the type of nooks as part of your definition. Your definition should be able to satisfy the included doctest cases.
To make your solution easier to read and grade, I recommend submitting your answer as “Preformatted” text using the Canvas drop down menu (by default it will show “Paragraph”).
ex1 = Nook 3 (Nook 4 (Node (Nook 2 End) (Node (Nook 5
End) End)))
ex2 = Node (Node (Nook 3 End) (Nook 4 (Nook 5 End)))
(Node End End)
— | Count the number of nooks in a tree.
—
— >>> nooks End
— 0
—
— >>> nooks ex1
— 4
—
— >>> nooks ex2
— 3
—
— >>> nooks ex3
— 2
—
nooks = undefined
Answer:
nooks :: Tree a -> Int
nooks End = 0
nooks (Nook _ t) = 1 + nooks t
nooks (Node l r) = nooks l + nooks r
Question 2
Part 1 (continued): Implementing recursive functions
Define the following function mapTree, which maps a function over values of the Tree data type defined above. Be sure to include the type of mapTree as part of your definition. Your definition should be able to satisfy the included doctest cases.
As before, I recommend submitting your answer as “Preformatted” text using the Canvas drop down menu.
—
— >>> mapTree (+10) ex1
—
— >>> mapTree odd ex2
—
— >>> mapTree length ex3
— Nook 3 (Nook 5 End)
—
mapTree = undefined
Answer:
— | Map a function over a tree, preserving its
structure.
— Nook 13 (Nook 14 (Node (Nook 12 End) (Node (Nook
15 End) End)))
— Node (Node (Nook True End) (Nook False (Nook
True End))) (Node End End)
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree _ End = End
mapTree f (Nook a t) = Nook (f a) (mapTree f t)
Question 3
Part 2: Type inference
Below are several type definitions. You do not need to know the implementations of the functions or the undefined ‘Glob’ type in order to solve the problems.
data Result a = OK a | Error String
show :: Glob -> String
build :: Int -> Glob
(.) :: (b -> c) -> (a -> b) -> a -> c
Part 2.1: Determine the type of a sub-expression
For each of the following problems, determine what the type of the unknown value must be in order for the overall expression to have the given type.
For example, given the following facts:
build foo :: Glob
bar True :: Int -> Int
mapTree f (Node l r) = Node (mapTree f l) (mapTree f
r)
Then it must be the case that ‘foo’ and ‘bar’ have the following types:
foo :: Int
bar :: Bool -> Int -> Int
(Brief explanation: ‘foo’ must be an ‘Int’ since it’s passed as an argument to ‘build’, and ‘bar’ is a function that returns a function from ‘Int -> Int’ when given one ‘Bool’.)
1. Giventhefollowingfact,whatisthetypeof’foo’?
OK (show foo) :: Result String
foo ::
Answer: Glob
2. Given the following fact, what is the type of ‘baz’? show . bar :: String -> String
bar ::
Answer: String -> Glob
Part 2.2: Construct a value of the given type
For each of the following problems, create an expression of the indicated type using only the types and functions defined above.
1. Result (Int -> Glob) Answer: OK build
2. Glob -> Result a Answer: Error . show