Calculando el trabajo realizado por F x = (x, x)

Question

Digamos que tengo esta función: (sintaxis de Haskell)

f x = (x,x) 

Cuál es el trabajo (cantidad de cálculo) realizado por la función?

Al principio pensé que era obviamente constante, pero ¿y si el tipo de x no es finito, es decir, x puede tomar una cantidad arbitraria de memoria? Uno tendría que tener en cuenta el trabajo realizado copiando x también, ¿verdad?

Esto me llevó a creer que el trabajo realizado por la función es realmente lineal en el tamaño de la entrada.

Ésta no es la tarea por sí mismo, pero se quedó cuando tuviera que definir el trabajo realizado por la función:

f x = [x] 

que tiene un problema similar, creo.

Answer 1

Muy informalmente, el trabajo realizado depende de la semántica operativa de su idioma. Haskell, bueno, es perezoso, por lo que pagar únicos factores constantes a:

• empuje punteros a x en la pila
• asignar una célula montón de (,)
• aplicar (,) a sus argumentos
• retorno a puntero a la celda de pila

Listo. O (1) trabajo, realizado cuando la persona que llama mira el resultado de f.

Ahora, se desencadenará una evaluación adicional si nos fijamos en el interior del (,) - y que el trabajo depende de la labor de evaluar x sí. Como en Haskell se comparten las referencias a x, solo se evalúa una vez.

Así que el trabajo en Haskell es O (trabajo de x) si evalúa por completo el resultado. Su función f solo agrega factores constantes.

Answer 2

Chris Okasaki tiene un maravilloso método para determinar el trabajo cargado para llamar a la función cuando se presenta una pereza (total). Creo que está en su artículo sobre Estructuras de datos puramente funcionales. Sé que está en la versión del libro. Leí esa parte del libro el mes pasado. Básicamente, se cobra un factor constante por la promesa/procesador creado, no se cobra nada por evaluar las promesas pasadas/thunks (supongamos que ya se han forzado/están en forma normal [no solo WHNF]). Eso es una subestimación Si desea una sobreestimación, también el costo de forzar/convertir a la forma normal de cada promesa/truco creado por la función. Al menos, así es como lo recuerdo en mi estado extremadamente cansado.

Búscalo en Okasaki: http://www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis - Juro que la tesis utilizada debe ser descargable.