Midterm Sample Solutions

--=============
-- PROBLEM 1 a)
--=============

-- an enumeration type
data MyColor	= Red | Green | Blue 
		deriving (Enum, Show)

-- a fancy example (not required)
mycols0		= map (toEnum::Int->MyColor) [fromEnum Red .. fromEnum Blue]


-- a product type (defines a new type: data constructor = "Pers")
data Person1	= Pers String Int

-- a product type (doesn't define a new type, but just type synonyms)

type Person2	= (Name, Age)
type Name	= String
type Age	= Int


-- a list type (new user-defined list type)
data MyPolyList1 a = EmptyList | Cons a (MyPolyList1 a)

-- a list type (type synonym)
type MyPolyList2 a = [a]

-- a list type (example type and value declaration for a constant)
mylist0	:: [Int]
mylist0 = [1..10]


-- a record (tuple) type
-- (same as product type.... here polymorphic for a change...)

data MyRecord a	= Rec a [a]  

-- a recursive type
-- (same as MyPolyList1 above)

-- a non-recursive type
-- (same as Person1/2 above)

-- an algebraic type
data XML	= EmptyXML | Leaf Tag | Node Tag [XML]

type Tag	= String

{- 

=============
PROBLEM 1 (b) 
=============

"MyPolyList1 a" from above is an example of a
polymorphic type. The type variable "a" stands for a set of types.
When a value of type "MyPolyList1 a" is constructed (either at
compile-time, e.g.

	list0 = Cons 1 (MyPolyList1 EmptyList) 

or at runtime, the type variable "a" will become instantiated with a
concrete type, say "Int".  More interesting than constants like list0
are in fact polymorphic functions that work on polymorphic types
(e.g., the length of a list can be computed in the same way for all
types "a").

=============
PROBLEM 1 (c)
=============

in both cases, the result type is arbitrary. The difference is in the
index/key type: 

regular array: the index/key type is  (subrange of) Integer or some
other enumerated type (e.g., MyColor above)

associative array: the index/key type is any type (often "String")

Note: a common way to implement associative arrays is via hashes

=============
PROBLEM 1 (d)
=============

Arrays can be seen as (*are*)  finite functions:
E.g. the array arr :: Integer -> Char
	arr[1] = 'f', arr[2] = 'o', arr[3] = 'o'
and the function g :: Integer -> Char 
	g(1) = 'f', g(2) = 'o', g(3) = 'o' 
obviously denote the same function.

The other way round: finite functions can be implemented as array.


=========
PROBLEM 2
=========

(a) add1 3 4 
  type : Integer
  value : 7

(b) add1 -1
  type : Integer -> Integer ( function )
  value : decrement function ( \x. x-1 )

(c) add2 -1
  compile time error.
  Because this is an uncurried function, and it requires two argument as
  input explicitly.

=========
Problem 3
=========

(a) leftmost outermost reduction
  double ( second ( double 2 ) ( double 3 ) )
=> ( second ( double 2 ) ( double 3 ) ) + ( second ( double 2 ) ( double 3 ) )
=> ( double 3 ) + ( second ( double 2 ) ( double 3 ) )
=> ( 3 + 3 ) + ( second ( double 2 ) ( double 3 ) )
=> 6 + ( second ( double 2 ) ( double 3 ) )
=> 6 + ( double 3 )
=> 6 + ( 3 + 3 )
=> 6 + 6
=> 12

(b) f 4 6 = f 6 4 = f 4 (6-4) = f 4 2 = f 2 (4-2) = f 2 2 = 2
    f 7 12 = f 12 7 = f 7 (12-7) = f 7 5 = f 5 (7-5) = f 5 2 = f 2 (5-2)
           = f 2 3 = f 3 2 = f 2 (3-2) = f 2 1 = f 1 (2-1) = f 1 1 = 1

(c) f computes the greatest common denominator (GCD) of the two arguments.
    f 0 3 = f 3 0 = f 0 (3-0) = f 0 3 ....
    It will loop forever!



=========
PROBLEM 5
=========

a)
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs


b)


Using a helper function:

inc x y = 1 + y

Thus the function that calculates the length of the list:

	length xs = foldr (inc) 0 xs
OR
	length = foldr (inc) 0     



=========
PROBLEM 6
=========

a)		
	 20
	/  \
       10   5
      /  \
     1    3


b)
The types of foo and mytree0 are:

foo :: MyTree a -> [a]
mytree0 :: MyTree Int


c)
[ 1, 3, 10, 5, 20 ]
The function returns a list of  nodes of the tree in postorder.

-}