Exam Review 1

One-page version suitable for printing.

Question 1-1

Suppose we use a skew binary tree representation for a list. When the list contains the data [10,20,30,...,100], its internal structure is as follows.

Draw the list's internal structure after each of the following insertions, in sequence.

Solution

Question 1-2

Complete the following class definition by writing the >>= function for the Maybe type. 

data Maybe a = Just a | Nothing
instance Monad (Maybe a) where
    return x        =  Just x
For this type, the expression x >>= f operator should yield Just (f(data)) if x is Just data, and it should yield Nothing if x is Nothing.

Solution

Question 1-3

Write a function main with type IO () which reads two lines from the user and prints them back in reverse.

Question 1-4

Explain the significance of strictness analysis to compiling Haskell programs into efficient code.

Question 1-5

Suppose we have a parent predicate defined in Prolog. 

parent(Cheri, Carl).
parent(Cheri, Hal).
parent(Chuck, Carl).
parent(Dorothy, Cheri).
parent(Dorothy, Vicki).
Define a Prolog predicate sibling(A,B) based on the parent predicate that represents whether A and B are siblings.

Solution