2012-02-12 19 views
9

¿Por qué haskell requiere varias reglas de reescritura dependiendo de la técnica y longitud de composición de la función? Hay alguna manera de evitar esto?Haskell Reglas de reescritura y composición de funciones

Por ejemplo, dado el siguiente código ...

{-# RULES 
"f/f" forall a. f (f a) = 4*a 
    #-} 
f a = 2 * a 

esto funciona para

test1 = f (f 1) 

sin embargo tenemos que añadir una regla para

test2 = f . f $ 1 

y

test3 = f $ f 1 

que nos deja con las siguientes reglas

{-# RULES 
"f/f1" forall a. f (f a) = 4 * a 
"f/f2" forall a. f . f $ a = 4 * a 
"f/f3" forall a. f $ f $ a = 4 * a 
    #-} 

Sin embargo, cuando la cadena estos juntos o utilizar otras formas de composición de las reglas no se activan.

test4 = f . f . f $ 1 
test5 = f $ f $ f $ 1 
test6 = f $ 1 

¿Por qué es esto? ¿Debo escribir reglas de reescritura para cada implementación posible?

+1

No lo sé, pero supongo que es porque las reglas de reescritura no se aplican a las funciones que ha importado. Y '$' y '.' son solo funciones importadas del Preludio. –

Respuesta

13

La regla no se dispara en muchos casos debido a que la función muy sencilla f se colocarán en línea antes de la regla tuvo la oportunidad de disparar. Si se demora la expansión en línea,

{-# INLINE [1] f #-} 

la regla

{-# RULES "f/f" forall a. f (f a) = 4*a #-} 

debe disparar para todos estos casos (trabajado aquí con 7.2.2 y 7.4.1).

La razón es que el matcher de reglas no es excesivamente elaborado, solo coincide con las expresiones que tienen la forma sintáctica de la regla (no del todo cierto, el cuerpo de la regla también experimenta cierta normalización). Las expresiones f $ f 3 o f . f $ 4 no coinciden con la forma sintáctica de la regla. Para que la regla coincida, debe realizarse alguna reescritura, ($) y (.) deben estar subrayados antes de que la regla coincida con la expresión. Pero si no previene que f quede subrayado en la primera fase del simplificador, se reemplaza por su cuerpo en la misma ejecución que ($) y (.) están en línea, por lo que en la siguiente iteración, el simplificador ya no ve f, solo ve 2*(2*x), que no coincide con la regla.

3

yo habría pensado que esto funcionaría de forma predeterminada, pero se puede añadir dos más reglas de reescritura para hacer ./$ reducido a lambda/aplicación, por lo que este siempre coincidirá con:

{-# RULES 
"f/f" forall a. f (f a) = 4*a 

"app" forall f x. f $ x = f x 
"comp" forall f g. f . g = (\x -> f (g x)) 
    #-} 

f a = 3 * a -- make this 3*a so can see the difference 

Una prueba :

main = do 
    print (f . f $ 1) 
    print (f (f 1)) 
    print (f $ f 1) 
    print (f $ f $ 1) 
    print (f $ f $ f $ f $ 1) 
    print (f . f . f . f $ 1) 
    print (f $ f $ f $ 1) 
    print (f . f . f $ 1) 
    print (f $ 1) 

salida:

4 
4 
4 
4 
16 
16 
12 
12 
3 

Esto también funciona en algunos (pero no todos) c más oscura ases, debido a otras reglas de reescritura. Por ejemplo, todos estos se trabajará:

mapf x = map f $ map f $ [x] 
mapf' x = map (f.f) $ [x] 
mapf'' x = map (\x -> f (f x)) $ [x] 
Cuestiones relacionadas