Estoy aprendiendo Haskell para un curso universitario y tengo una pregunta sobre expresiones reducibles (redexes). Entiendo el concepto, pero todavía tengo algunas preguntas que parece que no puedo resolver por mi cuenta.
Digamos que le gustaría encontrar todas las expresiones reducibles en una expresión, como esta:
head (map (+1) (3:repeat 3)) En esta expresión, un redex obvio sería map (+1) (3:repeat 3)) porque coincide con la definición de map , por lo que Haskell "reduciría" la expresión y map incrementaría 3 y 4:map (+1) (repeat 3) . se reduciría a continuación.
La pregunta que tengo es:
¿La head (map (+1) (3:repeat 3)) ya es un redex, antes de que se evalúe el map ?
Debido a que la "entrada" de head no coincide con el constructor de una lista (que es lo que busca head ), estoy confundido acerca de si todavía es un redex porque lógicamente aún no se puede reducir, pero las definiciones en línea parecen estar diciendo que sería.
La evaluación de Haskell es perezosa: procede con la estrategia de redex más a la izquierda (al menos conceptualmente): reduce la de más a la izquierda entre las redex más altas.
Presumiblemente, la head se define como
head xs = case xs of (x:_) -> x entonces su aplicación a cualquier expresión es de hecho un redex, una expresión que necesita reducirse. Que procede según la definición de head ,
head (map (+1) (3:repeat 3)) = case (map (+1) (3:repeat 3)) of (x:_) -> x = (o podríamos decir que la head en sí es el redex superior izquierdo, que se reduce a su definición, primero; y si hubiéramos escrito lo anterior como ((\xs -> case xs of (x:_) -> x) (map (+1) (3:repeat 3))) llegaríamos al mismo resultado, solo que un poco más tedioso).
Una primitiva de fuerza primaria es case . Ahora necesita realizar la coincidencia de patrones, por lo que debe averiguar el valor de su expresión de escrutinio (solo en la medida en que la coincidencia de patrones sea posible). Para hacer eso, ahora debe funcionar de acuerdo con la definición de map que presumiblemente es
map f xs = case xs of { (x:ys) -> fx : map f ys ; [] -> [] }por lo que se convierte
case (map (+1) (3:repeat 3)) of (x:_) -> x = case (case (3:repeat 3) of { (x:ys ) -> (+1) x : map (+1) ys ; [] -> [] } ) of (x:_) -> x = En este punto, la expresión del case interno se puede reducir,
case (let { x=3 ; ys=repeat 3} in (+1) x : map (+1) ys ) of (x : _ ) -> x = y ahora la coincidencia de patrones de la case exterior se vuelve posible,
case (let { x=3 } in (+1) x ) of (x ) -> x = let { x=3 } in (+1) x = (+1) 3 = 4