Las respuestas hasta ahora se han centrado abrumadoramente en la inducción sobre los números naturales. Este es un caso importante, pero no necesariamente el más intuitivo. En términos más generales, la inducción se trata de razonar desde casos más simples a casos más complejos, siempre que la propiedad bajo investigación viaje hacia arriba.
¿Qué diablos quiero decir con “viajes hacia arriba”? Construyamos un pequeño ejemplo para que pueda explicar.
Imaginemos un lenguaje de programación con cuatro tipos incorporados: un tipo int , un tipo char , una list y un tipo abstracto de tuple , donde cada tipo de tupla concreta tiene que especificar su longitud y los tipos de sus miembros. El tipo de list es mutable, y los otros tres son inmutables.
Ahora, el lenguaje no viene con una función hash incorporada, pero queremos una. Sabemos que no debemos mezclar contenedores mutables, o contenedores que contengan contenedores mutables, o contenedores que contengan contenedores que contengan contenedores mutables, o …
Pero eso solo nos dice qué no hacer hash. ¿Cómo determinamos que algo es seguro para el hash, y luego cómo lo hacemos? Necesitamos una definición por inducción:
Diremos que un tipo es helter si es
- el tipo
int ,
- el tipo
char , o
- es de la forma
tuple(type_1, ..., type_k) donde todos los type_1, ..., type_k son type_1, ..., type_k .
Cualquier tipo que no sea helter es skelter .
Ahora, detengámonos aquí para pensar en lo que tenemos: un conjunto de cosas (tipos) que son más o menos complejas. Las cosas menos complejas son los tipos primitivos int y char : simplemente se sientan allí. (Son como 0 cuando estás haciendo inducción en los números naturales). Entonces todo lo demás tiene una mayor complejidad. ¡Pero podemos decir más!
tuple(int,char,int)
es un tipo complejo y
tuple(list(int),tuple(char,char),tuple(int,char,int))
es un tipo complejo, pero en realidad podemos comparar la complejidad de varios tipos. Por ejemplo, los únicos tipos que tienen una complejidad menor que la tuple(int,char,int) son int y char . Por otro lado, los tipos que son menos complejos que el segundo tipo que escribí son
list(int)
int
tuple(char,char)
char
tuple(int,char,int)
(¿Ves por qué los escribí en este orden?)
Aparte: no todos los tipos son comparables. Ni la tuple(char,int) ni la tuple(int,char) son más o menos complejas que la otra. De hecho, char no tiene una complejidad menor que la tuple(int,int) , aunque es intuitivamente “más simple”. La complejidad solo mide qué tipos necesita antes de poder construir otros tipos.
OK, genial, ¿y qué? Bueno, ahora podemos definir una función hash (nota: en realidad no use esta en el código de producción):
función hash (x helter) int:
case x int:
volver x
caso x char:
retorno ord (x)
caso x tupla:
b = 3
hashval = 0
para y en x:
hashval + = b ** (1 + hash (y))
b + = 2
hashval de retorno
Tenga en cuenta las similitudes con la inducción en los números naturales: hay un par de casos base, y luego cada dos casos aprovecha el resultado de niveles más simples. En este ejemplo, la hashability y la inconhability viajan hacia arriba. Y solo hay un número finito de casos debajo de cualquier helter x particular, aunque, a medida que los helters se vuelven más complejos, el hashing implica más y más llamadas recursivas para caminar por las capas de complejidad.
Esta es la idea fundamental de la inducción: si podemos demostrar que, cuando estamos viendo una cosa “más compleja”, el valor de alguna propiedad solo depende de lo que sucede a escalas “menos complejas”, entonces somos la mayoría de el camino a una prueba o un algoritmo.
