Instructions

All the questions refer to Haskell programs. Submit the answers that are programs in a *.hs file. For the written questions, you can include them in the *.hs file as as {- multi-line comments -}, or you can include them in a separate file, zip the two of them together and submit the zip file.

Questions [100 points total]

Written Problems

1. [8 = 4 * 2 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. as types, a -> [a] and b -> [b] are equivalent).

f1a = \(x, y) -> (y, x) -- (Hint: You need two type variables)

f1b = \x y -> [[x], y] f1c = \x y z -> [x : z, y : z]

f1d f = length . (filter f)

2. [4 points] What are the two differences between the datatypes D1 and D2 below? Discuss briefly and give a short example of each difference.

data D1 a = Const1 | Fcn1 a Int

data D2 a = Const2 | Fcn2 a Int deriving (Eq, Show)

Programming Problems

3. [6 points] Make the function definition below syntactically correct by repairing the indentation and identifiers. (Keep it three lines long, though.)

F3 X y = Abc * z where

Abc = X + y

z = Abc + 2

For Questions 4 and 5, be sure to import Data.Char in your *.hs file so that you can use its utility functions. In ghci, you can do the import or the use command :m + Data.Char.

4. [8 points] Consider the (incomplete) definition f4 = foldl (???) True.

a. [5 points] Give a lambda expression to use in place of the ??? so that f4 takes a String and returns true iff all the characters of the string are letters*.

b. [3 points] What is the type of your lambda expression?

5. [6 points] Write a function trim so that f5 numbers = filter trim numbers returns the sublist of numbers that are multiples of 5 or 7. To practice using guards, 2 of the 6 points are for writing trim using guards, not if-else expressions or logical and/or. (If you can't do that way, turn in your version that uses if-else or logical and/or.)

6. [8 points] Write a function iterate as follows: iterate n f x (where n is an integer) should take a function and value and applies the n-fold composition of the function f to x. (If n 0, the n-fold composition of f is the identity function.)

Examples:

iterate 3 (8 +) 5 = 8+8+8+5 = 29

iterate (-5) sqrt (-2) = -2.0

Two of the points are for writing iterate n f = functional expression using a higher-order function. (Hint: Consider the list of n copies of f.) If you can't write it that way, then just define iterate n f x recursively.

For Questions 7 and 8, use the datatype Tree below, which defines a binary tree with values attached to each leaf and interior node.

data Tree a = L a | Br a (Tree a) (Tree a) deriving (Eq, Show)

sample1 = Br 'a' (L 'b') (Br 'c' (L 'd') (L 'e'))

sample2 = Br 9 (Br 7 (L 6) (Br 7 (L 7) (L 6))) (L 9)

7. [14 = 11 + 3 points]

a. [11 points] Write a function pre' such that pre' tree list returns the list you get if you prepend the preorder traversal of the tree to the list. For example, pre' (L 'q') "rs" is "qrs" and pre' (Br 'h' (L 'i') (L ' ')) "there" is "hi there". (A regular preorder traversal function pre can be defined then as pre tree = pre' tree [].) For fullest credit, don't use the (++) operator on lists in pre', just use the (:) operator.

b.[3 points] What is the type of pre' ?

More precisely, return true if there are no non-letter characters in the string. That way f4 "" = True.

8. [20 = 6 + 10 + 4 points] Let's define a heap to be a tree of numbers where the number at each node is all the values in the subtree beneath it. A one-node tree (i.e., a leaf) is automatically a heap.

a. [6 points] Write a function top :: Tree a -> a that returns the top value of a tree: For a leaf, it's the value of the leaf; for an interior node, it's the value on the interior node.

b. [10 points] Using top, write an isHeap function that takes a tree and returns true iff it's a heap.

d. [4 points] What is the type of isHeap? Explain briefly why the type is not Tree a -> Bool.

9. [26 = 8 + 18 points] The following definitions are for a stack of values with operations push and pop type Stack a = [a] data StackOp a = Push a | Pop deriving (Eq, Show) type Config a = (Stack a, [Maybe a]) -- A configuration is the current stack and list of Pop results

a. [8 points] Define a function apply :: StackOp a -> Config a -> Config a

Applying (Push x) (Config stack results) add (i.e., cons) x onto the stack and Nothing onto the results.

If the stack has head x, then Pop removes x from the stack and adds Just x to the results.

If the stack is empty, then Pop simply adds Nothing to the results.

b. [18 points] Define a function applyList :: [StackOp a] -> Config a

applyList should take a list of stack operations and apply them in sequence to the starting configuration (which has an empty stack and empty list of results).

Four of the points are for defining applyList not recursively but using higher-order functions like map and foldl. (So applyList ops = functional expression.) [If you can't write it this way, write it tail-recursively. [9/3] Hint: Write an applyList' ops config helper function that applies the operations to the config and returns the resulting config.

Example of execution: [9/3: changed to use given types]

applyList [Push 1] = Config [1] [] -- pushed 1

applyList [Push 1, Push 2] = Config [2,1] [] -- pushed 2 on top of 1

applyList [Push 1, Push 2, Pop]

= Config [1], [Just 2] -- popped 2 from stack

applyList [Push 1, Push 2, Pop, Pop]

= Config [], [Just 1, Just 2] -- popped 1 from stack

applyList [Push 1, Push 2, Pop, Pop, Pop]

= Config [], [Nothing, Just 1, Just 2] -- popped empty stack