## 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).
```