Haskell: Equation Expander 1+ (1+ (1+ (1+ (...)))) = ∞

Question

¿Existe un expansor de ecuación para Haskell?

Algo así como foldr.com: 1+(1+(1+(1+(…))))=∞

Soy nuevo en Haskell Estoy teniendo problemas para entender por qué ciertas ecuaciones son más preferibles que otras. Creo que ayudaría si pudiera ver expandidas las ecuaciones.

Por ejemplo, encontré foldr vs foldl difíciles de entender al principio hasta que los vi expandirse.

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr k z xs = go xs 
      where 
       go []  = z 
       go (y:ys) = y `k` go ys 

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldl f z0 xs0 = lgo z0 xs0 
      where 
       lgo z []  = z 
       lgo z (x:xs) = lgo (f z x) xs 

De las definiciones puedo ver que foldr se expande de esta manera:

foldr (+) 0 [1..1000000] --> 
1 + (foldr (+) 0 [2..1000000]) --> 
1 + (2 + (foldr (+) 0 [3..1000000])) --> 
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) --> 
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) --> 

y foldl expande como esto:

foldl (+) 0 [1..1000000] --> 
foldl (+) (foldl (+) 0 [1]) [2..1000000]) --> 
foldl (+) (foldl (+) (foldl (+) 0 [1])) [3..1000000]) --> 

o de Haskell Wiki on foldr fold foldl':

let z1 = 0 + 1 
in foldl (+) z1 [2..1000000] --> 

let z1 = 0 + 1 
    z2 = z1 + 2 
in foldl (+) z2 [3..1000000] --> 

let z1 = 0 + 1 
    z2 = z1 + 2 
    z3 = z2 + 3 
in foldl (+) z3 [4..1000000] --> 

let z1 = 0 + 1 
    z2 = z1 + 2 
    z3 = z2 + 3 
    z4 = z3 + 4 
in foldl (+) z4 [5..1000000] --> 

Sin embargo, tengo problemas con ecuaciones más grandes para entender por qué las cosas funcionan de la manera que lo hacen en Haskell. Por ejemplo, la primera función de tamiz usa 1000 filtros, mientras que la segunda función de tamiz solo toma 24 para encontrar la prima 1001.

primes = sieve [2..] 
    where 
    sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0] 



primes = 2: 3: sieve (tail primes) [5,7..] 
    where 
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0] 
            -- or: filter ((/=0).(`rem`p)) t 
         where (h,~(_:t)) = span (< p*p) xs 

Haskell Wiki on Primes

he pasado un buen tiempo trabajando y ampliando con la mano. He llegado a entender cómo funciona. Sin embargo, una herramienta automatizada para expandir ciertas expresiones mejoraría en gran medida mi comprensión de Haskell.

Además creo que también podría servir para ayudar a preguntas que buscan optimizar el código Haskell:

• Optimizing Haskell Code
• Help optimize my haskell code - Calculate the sum of all the primes below two million

¿Existe una herramienta para expandir expresiones Haskell?

Answer 1

Esto es de ninguna manera una respuesta completa a su pregunta, pero me pareció una conversación sobre Haskell-Cafe que tiene algunas respuestas:

http://www.haskell.org/pipermail/haskell-cafe/2010-June/078763.html

que los enlaces de rosca a este paquete:

http://hackage.haskell.org/package/repr que de acuerdo a la página "permite generar expresiones sobrecargados a su representación textual"

El ejemplo proporcionado es:

*Repr> let rd = 1.5 + 2 + (3 + (-4) * (5 - pi/sqrt 6)) :: Repr Double 
*Repr> show rd 
"fromRational (3 % 2) + 2 + (3 + negate 4 * (5 - pi/sqrt 6))" 

Answer 2

David V. Gracias por esos enlaces. Repr definitivamente vale la pena agregar a mi caja de herramientas. Me gustaría agregar algunas bibliotecas adicionales que encontré útiles.

HackageDB : Trace (Al 12 de diciembre de 2010)

• biblioteca de eventos y el programa de GHC: Biblioteca y herramienta para analizar archivos .eventlog de GHC
biblioteca
• capó: Depuración mediante la observación en el lugar
• biblioteca HPC-strobe: luces estroboscópicas generados-HPC para un programa Haskell corriendo
• programa HPC-trazador: trazador con interfaz AJAX

El paquete Hook parece ser lo que estoy buscando. Voy a publicar más muestras más tarde hoy.

Hood

main = runO ex9 

ex9 = print $ observe "foldl (+) 0 [1..4]" foldl (+) 0 [1..4] 

salidas

10 

-- foldl (+) 0 [1..4] 
    { \ { \ 0 1 -> 1 
     , \ 1 2 -> 3 
     , \ 3 3 -> 6 
     , \ 6 4 -> 10 
     } 0 (1 : 2 : 3 : 4 : []) 
     -> 10 
    } 

no era consciente de la biblioteca Hackage (como me acaba de entrar en Haskell). Me recuerda al CPAN de Perl. Gracias por proporcionar esos enlaces. Este es un gran recurso.

Answer 3

Esta es una respuesta a una pregunta no formulada, considéralo como un comentario largo.

(Por favor downvote sólo entonces por debajo de 0, si y sólo si usted piensa que no encaja. Voy a quitar entonces.)

---

Tan pronto como usted es un poco más experimentado, puede que no quiero ver la forma en que las cosas se expanden, nunca más. Querrá comprender CÓMO funcionan las cosas, lo cual reemplaza la pregunta ¿POR QUÉ funciona? no ganarás mucho simplemente observando cómo se expande, nunca más.

La forma de analizar el código es mucho más simple de lo que podría pensar: simplemente etiquete cada parámetro/variable como "evaluado" o "no evaluado" o "por evaluar", según la progresión de sus conexiones causales .

Dos ejemplos:

---

1.) fibs

La lista de todos los números de Fibonacci es

fibs :: (Num a) => [a] 
fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

ya se evalúan Los dos primeros elementos; por lo tanto, etiquete el tercer elemento (que tiene el valor 2) como para ser evaluado y todo lo restante como no evaluado. El tercer elemento será la combinación (+) de los primeros elementos de fibs y fibs de la cola, que serán el primer y el segundo elemento de fibs, que ya están etiquetados como evaluados. Esto funciona con el n-ésimo elemento a ser evaluado y los elementos (n-2) -nd y (n-1) -st ya evaluados respectivamente.

Puede visualizar esto de diferentes maneras, es decir:

fibs!!(i+0) 
+ fibs!!(i+1) 
= fibs!!(i+2) 

      (fibs) 
zipWith(+) (tail fibs) 
     = (drop 2 fibs) 

      1 : 1 : 2 : 3 ... 
    (1 :)1 : 2 : 3 : 5 ... 
(1 : 1 :)2 : 3 : 5 : 8 ... 

---

2.) Su ejemplo "tamiz (p: p) xs"

primes = 2: 3: sieve (tail primes) [5,7..] 
    where 
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0] 
            -- or: filter ((/=0).(`rem`p)) t 
         where (h,~(_:t)) = span (< p*p) xs 

En "tamiz (p: p) xs",

• p se evalúa,
• ps no se ha evaluado, y
• xs es una lista infinita dividida parcialmente dividida (no contiene p pero contiene p²), que puede adivinar leyendo la recursión y/o reconociendo que los valores de h deben ser primos.

Sieve debe devolver la lista de primos después de p, por lo que al menos el siguiente primo debe ser evaluado.

• El próximo primer estará en la lista h, que es la lista de todos los números (ya tamizados) k donde p < k < p²; h contiene solo números primos porque xs no contiene p ni ningún número divisible por ningún primo debajo de p.
• t contiene todos los números de xs por encima de p². t debe evaluarse como flojo en lugar de tan pronto como sea posible, porque puede que ni siquiera sea necesario evaluar todos los elementos en h. (Solo se evaluará el primer elemento de h)

El resto de la definición de función es la recursión, donde la siguiente x es t con todo n * p filtrado.

---

En el caso de foldr, un análisis mostrará que el "Go" se define sólo para acelerar el tiempo de ejecución, no la legibilidad. Aquí es una definición alternativa, que es más fácil de analizar:

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr (.:) e (x:xs) = x .: (foldr (.:) e xs) 
foldr (.:) e []  = e 

que he descrito su funcionalidad here (sin análisis).

Para entrenar este tipo de análisis, es posible que desee leer las fuentes de algunas bibliotecas estándar; es decir, scanl, scanr, unfoldr en el source de Data.List.