Question 1

1.          Type                  Type 
            / | \                 / | \
           /  |  \               /  |  \
        Type  -> Type         Type  -> Type
        / | \     |             |      / | \
       /  |  \    |             |     /  |  \
    Type -> Type TVar         TVar  Type -> Type
      |       |                      |       |
      |       |                      |       |
    TVar    TVar                    TVar    TVar
   
   
   
            Type                  Type 
            / | \                 / | \
           /  |  \               /  |  \
        Type  * Type         Type  -> Type
        / | \     |             |      / | \
       /  |  \    |             |     /  |  \
    Type -> Type TVar         TVar  Type *  Type
      |       |                      |       |
      |       |                      |       |
    TVar    TVar                    TVar    TVar
   
   
        
            Type                  Type 
            / | \                 / | \
           /  |  \               /  |  \
        Type  * Type         Type   *  Type
        / | \     |             |      / | \
       /  |  \    |             |     /  |  \
    Type  * Type TVar         TVar  Type *  Type
      |       |                      |       |
      |       |                      |       |
    TVar    TVar                    TVar    TVar
   
   

2.    Type    ::=  CarType -> Type  |  CarType
      CarType ::=  CarType * TVar   |  TVar
   

Question 3

1. One DP to the stack, no ML
2. No DP, no ML
3. One DP to the heap, no ML
4. No DP, no ML
5. No DP, one ML
6. No DP, no ML

Question 2

1. False
2. False
3. True
4. False
5. False
6. False
7. False
8. True, if we want that all suspended threads are waken up when y is set to a value different from 0
9. True
10. False
11. True
12. True
13. False

Question 4

1.    datatype 'a tree = emp | nod of 'a * 'a tree list;
   

2.    fun pre_trav emp = []
        | pre_trav (nod(x,L)) = x :: aux L
      and
          aux [] = []
        | aux (T :: L) = pre_trav T @ aux L;
   

Question 5

1.    fun altnfold f g 0 x = x
        | altnfold f g n x = f(g(altnfold f g (n-1) x));
   
   
   The result is 6. reduce (op +) 0 L  computes the sum of the elements of L
   The result is 6. reduce (op *) 1 L  computes the product of the elements of L
   The result is [1,2,3]. reduce (op @) [] L  flattens the list Lcomputes the product of the elements of L
   The expression gives error. (op <)  is of type int * int -> bool, while it should be a type compatible with
   alpha * beta -> beta
   The result is false. reduce (fn (x,y) => x=0 orelse y) false L tests whether the list L contains 
   at least one 0.
   The result is [1,2,3]. reduce (fn (x,y) => if x>0 then x::y else y) [] L eliminates all the non-positive
   elements from the list L.
   
   

Question 6

1. (alpha * alpha -> beta) -> alpha -> beta
2. (alpha * beta -> gamma) -> alpha -> beta -> gamma
3. (alpha -> beta -> gamma) -> alpha -> beta -> gamma
4. (alpha -> beta) -> (gamma -> alpha) -> gamma -> beta
5. Untypable: the result in the fist case is an int, while in the second case is a list.
6. (int -> alpha) -> int -> alpha list

Question 7

1.    in(X,nod(_,X,_)).
      in(X,nod(T,_,_)) :- in(X,T).
      in(X,nod(_,_,T)) :- in(X,T).
   

2.    in_trav(emp,[]).
      in_trav(nod(T1,X,T2),L) :- in_trav(T1,L1), in_trav(T2,L2), append(L1, [X|L2], L).
   

3.    sum_tree(emp,0).
      sum_tree(nod(T1,X,T2),N) :- sum_tree(T1,N1), sum_tree(T2,N2), N is N1 + N2 + X.
   

4.    symmetric(emp,emp).
      symmetric(nod(T1,X,T2), nod(U2,X,U1)) :- symmetric(T1,U1), symmetric(T2,U2).