Option Traduction de Programmes TD Mercredi 25 avril Langages fonctionnels

1. Appliquer l’algorithme de détermination des types afin de décider le type des fonctions suivantes:

(a)

f 0 = [ ]; f n = (n : f (n − 1))

(b)

inv [ ] y = y; inv (h : t) y = inv t (h : y)

(c)

g [ ] [ ] = [ ]; g (h1 : t1) (h2 : t2) = (h1 h2 : g t1 t2)

(d)

p a [ ] = a; p a (b : c) = conc (p a c) (p (b : a) c)
where conc [ ] y = y; conc (hx : tx) y = (hx : conc tx y)

(e)

f f = [ ]

2. Evaluation paresseuse et structures infinies:

Définir un type Miranda capable de représenter un graphe fini ou infini et écrire une expression qui “s’évalue” à un graphe infini dont les sommets sont les entiers supérieurs à 1 et deux sommets sont reliés par une arête ssi l’un des deux entiers est multiple de l’autre. Définir une fonction qui renvoie un chemin entre deux sommets d’un graphe (s’il y en a).