Clase 18/03/2015.

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]
={ Definición de lista }
      
duplica.( 3 ▷ [2, 5])
={ Definición de duplica }
      
algo con 3 y duplica.[2,5]

<---------------------

      sum.[3, 2, 5]
={ Definición de lista }
      
sum.( 3 ▷ [2, 5])
={ Definición de sum }
      3 + sum.
[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]
={ Definición de lista }
      
duplica.( 3 ▷ [2, 5])
={ Definición de duplica }
      
algo con 3 y [4, 10]
={              }
      [6, 4, 10]


      sum.[3, 2, 5]
={ Definición de lista }
      
sum.( 3 ▷ [2, 5])
={ Definición de sum }
      3 + sum.
[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]
[ ] ++ ys ≐ ys
(x ▷ xs) ++ ys ≐ x ▷ (xs ++ ys)

sum : [Num] → Num
sum.
[ ]0
sum.
(x ▷ xs)x + sum.xs

Probaremos que

sum.(xs ++ ys) = sum.xs + sum.ys

Receta para hacer una prueba por inducción en listas:

  1. 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.

  2. Caso Base: reemplazo la variable elegida por [ ] y pruebo lo que obtengo:
    sum.([ ] ++ ys) = sum.[ ] + sum.ys

  3. 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