Exam Review 1

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.

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.

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.

Solutions

Solution 1-1

Solution 1-2

data Maybe a = Just a | Nothing
instance Monad (Maybe a) where
    return x        =  Just x

    Nothing  >>= f  =  Nothing
    (Just x) >>= f  =  Just (f x)

Solution 1-3

main = do
        first <- getLine
        second <- getLine
        putStrLn second
        putStrLn first

Solution 1-4

In a straightforward implementation of a lazy language such as Haskell, each reference to a parameter identifier must be first checked to see whether it is a thunk and reduced if so, before the value can be used. This checking process is quite inefficient. Through analyzing whether a function is strict, the compiler can identify identifiers that it is sure will be eventually referenced, and these parameters can be thawed from their thunk form immediately so that generated machine code for later references can avoid checks to see whether the thunk is thawed yet.

Solution 1-5

sibling(A, B) :- parent(X, A), parent(X, B).