CIS505/705   Exercise      SAMPLE SOLUTIONS

Scoring: 
  +1   if at least one answer is correct, or both answers showed rewritings that were "half right"
  +0.5 if answers to both problems do not show correct rewritings

1. Calculate this expression's normal form:
     (tl ("a"::nil)) :: (hd (tl ("b"::nil::"c"::nil)))

Right to left:

= (tl ("a"::nil)) :: (hd (nil::"c"::nil))
= (tl ("a"::nil)) :: nil
= nil :: nil          <--- in python, this is  [[]]

Left to right:

= nil :: (hd (tl ("b"::nil::"c"::nil)))
= nil :: (hd (nil::"c"::nil))
= nil :: nil

In parallel:

= nil :: (hd (nil::"c"::nil))  
=  nil :: nil

All answers will be the same.


2. For these definitions:

fun plustwo(N) = "s"::"s"::N .
fun pred(nil) = nil .
fun pred("s"::N) = N .
val two = "s"::"s"::nil .

Calculate the normal form of this expression:
  pred(plustwo(two))

Inside out ("right to left", "eager evaluation"):

= pred(plustwo("s"::"s"::nil))
= pred("s"::"s"::"s"::"s"::nil)
= "s"::"s"::"s"::nil

Outside in ("left to right", "lazy evaluation"):

= pred("s"::"s"::two)
= "s"::two  =  "s"::"s"::"s"::nil

All answers will be the same.