Final 14/10/2008 (Paradigmas)

Ejercicio 1

Tipar "map map" sabiendo que

map :: (a->b)->[a]->[b]

Respuesta

Comenzamos con el "map" de más adentro

$\mathbb {W} (map)=\emptyset \triangleright map:(a'\rightarrow b')\rightarrow [a']\rightarrow [b']$

Luego para tipar "map map" usamos la regla de la aplicación

$\mathbb {W} (map)=\Gamma _{1}\triangleright map:\tau$

$\mathbb {W} (map)=\Gamma _{2}\triangleright map:\rho$

$S={\textrm {MGU}}\{\tau \doteq \rho \rightarrow {\textrm {t}}\}={\textrm {MGU}}\{(a'\rightarrow b')\rightarrow [a']\rightarrow [b']\doteq ((a\rightarrow b)\rightarrow ([a]\rightarrow [b]))\rightarrow {\textrm {t}}\}$

$S=\{a'\mapsto (a\rightarrow b),b'\mapsto ([a]\rightarrow [b]),{\textrm {t}}\mapsto ([a']\rightarrow [b'])\}$

entonces

$\mathbb {W} (map\ map)=S\Gamma _{1}\cup S\Gamma _{2}\triangleright S(map\ map):S{\textrm {t}}$

$\mathbb {W} (map\ map)=\emptyset \triangleright map\ map:[a'\rightarrow b']\rightarrow [([a']\rightarrow [b'])]$

Ejercicio 2

Explicar el concepto de Currificación y dar un ejemplo

Respuesta

Ejercicio 3

Hacer inferencia de tipos sobre ( \x \y -> x (y x) )

Respuesta

W(\x \y -> x (y x))= 
      {}> \x:t3->t5 \y:(t3->t5)->t3  -> x (y x) :t3->t5)->(((t3->t5)->t3)->t5
Si
  W(\y -> x (y x))={x:t3->t5} > \y:(t3->t5)->t3 -> x (y x) :((t3->t5)->t3)->t5
  Si
    W(x (y x))=S({x:t4}) U S({y:t2->t3,x:t2}) > S(x (y x) : S(t5)
              ={x:t3->t5, y:(t3->t5)->t3 } > x (y x) : t5
    Si
      S2=MGU{t4=t3->t5}U{t2=t4}= {t4<-t3->t5,t2<-t3->t5} t5 fresca
      W(x)    = {x:t4}> x:t4
      W((y x))=S({y:t1}) U S({x:t2}) > S(y x) :S(t3)
              = {y:t2->t3,x:t2} > y x : t3 
      Si
        S=MGU{t1=t2->t3}={t1<-(t2->t3)}  t3 fresca 
        W(y)={y:t1}>y:t1
        W(x)={x:t2}>x:t2

Ejercicio 4

Escribir en Prolog los predicados que determinan una una lista es sublista de otra y el que obitnene la raiz de un árbol binario.

Respuesta

sublista([],_).

sublista(S,L) :- sublista_inicial(S,L).

sublista([S|SS],[L|LS]) :- sublista([S|SS],LS).

sublista_inicial([],_).

sublista_inicial([S|SS],[L|LS]) :- S == L, sublista_inicial(SS,LS).

Voy a suponer que los arboles se forman con "nil" y "bin(izq, v, der)"

raiz(bin(_, V, _), V).

Ejercicio 5

Explicar tipos polimórficos

Respuesta

Ejercicio 6

Explicar las reglas de subtipado para funciones.

Respuesta