Comisión 1 (Docente: Pedro Sánchez Terraf)
Estrategias para definir funciones.
Planteamos problema similar a uno inventado por un compañero:
Dado una lista de productos con sus existencias, dar cuántos hay del primer producto listado
Ejemplo: existPrim.[(“a”,2), (“b”,1), (“c”,3)] = 2
Usando diagramas,
[(“a”,2), (“b”,1), (“c”,3)] 2
podemos descomponer la tarea en dos pasos: sacar el primer par, y luego sacar la segunda componente del par
[(“a”,2), (“b”,1), (“c”,3)](“a”,2)2.
Modularizar: descomponer un problema en otros más pequeños.
En nuestra notación,
existPrim.[(“a”,2), (“b”,1), (“c”,3)] = segComp.(sacarPar.[(“a”,2), (“b”,1), (“c”,3)])
En general, nuestra definición de existPrim será:
existPrim.xs ≐ segComp.(sacarPar.xs).
Ejercicio: encontrar definiciones para segComp y sacarPar. Solución
Una vez que tenemos las dos funciones, hacemos análisis por casos para determinar si hay algún producto en stock, sino damos un error. Para empezar lo escribo informalmente, en castellano.
existPrim.xs ≐ |
si xs=[ ] |
da error “No hay stock” |
|
o si xs≠[ ] |
da segComp.(sacarPar.xs) |
|
fin |
|
En Formalismo Básico (en papel) escribiremos:
existPrim.xs ≐ |
( xs=[ ] |
→ error “No hay stock” |
|
☐ xs≠[ ] |
→ segComp.(sacarPar.xs) |
|
) |
|
Notar: nuestro formalismo no contiene manejo de errores, así que la expresión anterior no pertenece estrictamente al Formalismo Básico. Pero nos tomamos la libertad de hacerlo así por esta vez.
Y por último, en Haskell
existPrim xs | xs==[] = error "No hay stock"
| xs/=[] = segComp (sacarPar xs)
Nota: hay que dejar los espacios en blanco que aparecen en la segunda línea para que funcione.
Ejercicio:
Dada
una lista de números, dar su suma.
Ejemplo: sum.[2, 1, 3] = 6
Idea: separar el problema en pasos. Si ya tengo la suma de [1,3], ¿qué debo hacer para obtener la suma de [1,2,3]?
En general, vamos sacando el primer número y se lo debo sumar al resto. Esto lo tengo que hacer con todos los elementos de la lista.
Cuando llegamos a la lista vacía, ya sumé 2 + 1 + 3 = 6, así que obtenemos
sum.[ ] ≐ 0
Como siempre se repite la operación cada vez que tenga un primer elemento, puedo tratar todos los casos con el patrón (x ▷ xs) y escribir
sum.(x ▷ xs) ≐ x + sum.xs
Entonces nuestra definición de suma se condensa así:
sum : [Num] → Num
sum.[ ] ≐ 0
sum.(x ▷ xs)
≐ x + sum.xs
Para usar esta definición vamos recorriendo los patrones uno a uno y aplicamos el que corresponda (ya sabemos que toda lista corresponde a alguno de esos dos patrones). Por ejemplo, calculamos sum.[4,3]:
sum.[4,
3]
={
Definición de lista }
sum.(
4 ▷ [3])
={
Definición de sum }
4 +
sum.[3]
={
Definición de lista }
4 +
sum.(
3 ▷ [ ])
={
Definición de sum }
4 + 3 +
sum.[
]
={
Definición de sum }
4 + 3 +
0
={ Aritmética }
7
Hace lo que tiene que hacer.
Ejercicio: definir la función duplica (Ejercicios Seleccionados, 2a). Para este ejercicio, tomamos como modelo lo que hicimos con sum. Supongamos que tenemos una definición con dos casos:
duplica : [Int] → [Int]
duplica.[ ] ≐
???
duplica.(x ▷ xs) ≐ ???
Sabemos, por ejemplo, que la función debe cumplir duplica.[3, 2, 5] = [6, 4, 10]. Hagamos trampa y trabajemos como si supiéramos la solución. Mientras, voy comparando con sum:
duplica.[3,
2, 5]
|
<--------------------- |
sum.[3,
2, 5]
|
En este punto, observemos que queremos que duplica.[2, 5] sea igual a [4, 10], y pongamos el resultado total al final:
duplica.[3,
2, 5]
|
|
sum.[3,
2, 5]
|
Entonces, queremos obtener [6, 4, 10] usando los datos 3 y [4, 10]. Terminar la definición queda como ejercicio.
Una vez resuelto este problema, uno puede abordar nuestro problema original:
Dada una lista de productos con sus existencias, dar
la cantidad total de productos.
Ejemplo: total.[(“a”,2),
(“b”,1), (“c”,3)] = 6
Ejercicio: Descubrir qué hace la función
h : Num → Num
h.0
≐ 0
h.(n+1)
≐ 2*n
+ 1 + h.n
calculando los valores de h.1, h.2, h.3 y h.4.
En este caso, tenemos dos patrones: 0 y (n+1). Calculamos h.1:
h.1
={
Aritmética (lo pongo de acuerdo al patrón (n+1)}
h.(0+1)
={
Definición de h }
2*0
+
1 + h.0
={
Definición de h }
2*0 + 1 +
0
={ Aritmética }
1
Una vez que tenemos una conjetura, podemos demostrarla usando inducción (es la misma que usan en Matemática Discreta). Solución
También se puede hacer inducción en listas. A diferencia con los naturales, donde los casos son 0 y (n+1) (o bien 1y (n+1)), los casos de listas son [ ] y (x ▷ xs). Para hacer un ejemplo, escribamos la definición de concatenar y repitamos la de sum:
(++)
: [A] → [A] → [A] |
sum
: [Num] → Num |
Probaremos que
sum.(xs ++ ys) = sum.xs + sum.ys
Receta para hacer una prueba por inducción en listas:
Elijo
una variable
para
hacer la inducción
En el ejemplo que elegimos, los casos vacío
y
no
vacío
aparecen
siempre en la variable xs, así que elegimos esa para hacer la
inducción.
Caso
Base:
reemplazo la variable elegida por [ ] y pruebo lo que
obtengo:
sum.([ ] ++ ys) = sum.[ ] + sum.ys
Caso
inductivo:
Copio el teorema tal como venía, y le llamo Hipótesis
Inductiva (HI):
(HI)
sum.(xs ++ ys) = sum.xs + sum.ys
reemplazo ahora (x ▷ xs)
en lugar de xs en todos lados:
sum.((x ▷ xs) ++ ys) =
sum.(x ▷ xs) + sum.ys
y demuestro lo que obtuve
usando las definiciones y la HI.
Hacemos un ejemplo en el que probamos un caso particular de la hipótesis inductiva, suponiendo que ya probamos el caso base. Es decir, tenemos
(HI) sum.([ ] ++ ys) = sum.[ ] + sum.ys
Usando esto, voy a probar que sum.([4] ++ ys) = sum.[4] + sum.ys
sum.([4]
++
ys)
={ Definición de lista }
sum.((4
▷ [ ])++ ys)
={ Definición de ++}
sum.(
4 ▷ ([ ]++ ys))
={ Definición de sum }
4
+ sum.([
]++ ys)
={
HI }
4
+ sum.[ ]
+
sum.ys
={ Definición de sum }
sum.(4
▷ [ ])
+ sum.ys
={ Definición de lista }
sum.[4]
+ sum.ys
Ejercicio: Completar la prueba por inducción de este teorema, siguiendo la receta de más arriba. Solución