CSE 130 
Sample Solutions: Individual Assignment 3

Problem 1

For all of these problems, there are different explanations. Here are
some of them (only one valid explanation per equation was necessary!).
Also: you can use the types of the lhs and rhs to show that an
equation is wrong (it is a necessary but not sufficient condition that 
type(lhs) = type(rhs). So to show that an equation is true, it is not
sufficient to say that the types are OK. For example, the types of the 
equation [1,2] = [2,3] are OK, yet the equation is false!)

(a)	[] : xs = xs

False!  

Reason: the lhs (left hand side) is a list with head (first element)
'[]' and restlist 'xs'. The rhs (right hand side) is the list
'xs'. Hence they are different!
Similarly: if the list on the rhs has length n, then the list on the
lhs has length n+1 => lhs and rhs are different!
Finally (using a counter example): 
Let xs = [1]. Then []:xs = [[],1] != [1]
(aside: the list on the lhs is not well-typed)

(b)	[] : xs = [ [] , xs ]

False!

Reason: let length xs == n. The lhs is a list with HEAD (=FIRST
ELEMENT) '[]' and RESTLIST 'xs' 
	=> length []:xs == n+1.
The rhs is a list with HEAD '[]' and SECOND ELEMENT 'xs' 
	=> length [ [], xs ] == 2
So not only are the lengths different (in general) but also the 'xs'
occurs once as a restlist (lhs) and once as an element (rhs).

Example: let xs = [1]. Then []:[1] = [[],1] != [[],[1]]
(again: the list on the lhs is not well-typed, while the one on the
rhs is; either way: they are different!)


(c)	xs : [] = xs
False! 
The lhs is a list with one element: xs : [] == [xs]
The rhs is the list 'xs' => [xs] != xs

Example: xs = [1]; then [1]:[] = [[1]] != [1]

(d)	xs : [] = [xs]
True! 
since the restlist on the lhs is '[]' we have
	xs : [] = [xs]

(e) x : y = [x,y] 

False!  
Reasons:
lhs: y is the RESTLIST, rhs: y is an ELEMENT
Another reason: 
lhs: length (x:y) = length y + 1
rhs: length [x,y] = 2

(f)	 (x:xs) ++ ys = x : ( xs++ys)

True!  
This is true according to the definition of the append (++) function!


Problem 2
(a)	leftmost  innermost
sqr ( first ( sqr 2 ) ( sqr 3) )
=> sqr ( first 2*2 ( sqr 3) )
=> sqr ( first 4 ( sqr 3) )
=> sqr ( first 4 3*3 ) )
=> sqr ( first 4 9 ) )
=> sqr ( 4 )
=> 16

(b)	leftmost  outermost

sqr ( first ( sqr 2 ) ( sqr 3) )
=> ( first ( sqr 2 ) ( sqr 3) ) * ( first ( sqr 2 ) ( sqr 3) )
=> ( sqr 2 ) * ( first ( sqr 2 ) ( sqr 3) )
=> ( 2*2 ) * ( first ( sqr 2 ) ( sqr 3) )
=>  4 * ( first ( sqr 2 ) ( sqr 3) )
=>  4 *  ( sqr 2 ) 
=>  4 * ( 2*2 )
=>  4 * 4
=> 16