Estoy tratando de definir una función que tomaría una función Double -> Double y devolvería su derivada matemática. He intentado hacer lo siguiente:Igualdad de funciones en Haskell
der :: (Double -> Double) -> (Double -> Double)
der f
| f == exp = exp
| otherwise = undefined
pero Haskell no soporta == en Double -> Double valores. ¿Es lo que estoy tratando de hacer imposible en Haskell?
Sí, lo que estás tratando de hacer es imposible en Haskell, y en general: decidir si dos funciones son iguales para todas las entradas posibles (sin solo verificar cada valor de entrada, si eso es posible) es equivalente a resolver el Deteniendo el problema.
Sin embargo, en su caso específico, puede evitarlo, utilizando un tipo personalizado que simula un Double (es decir, tiene las mismas instancias y, por lo tanto, puede usarse en lugar del mismo) pero en lugar de evaluar a un número, construye una representación abstracta de las operaciones que hace la función. Expr representa el lado derecho de una definición de función matemática f(x) = ....
data Expr = X | Const Double |
Add Expr Expr | Mult Expr Expr |
Negate Expr | Inverse Expr |
Exp Expr | Log Expr | Sin Expr | ...
deriving (Show, Eq)
instance Num Expr where
(+) = Add
(*) = Mult
...
instance Fractional Expr where
recip = Inverse
...
instance Floating Expr where
pi = Const pi
exp = Exp
log = Log
sin = Sin
...
A continuación, se pueden definir las funciones de conversión que convierten entre las funciones y Expr s:
fromFunction :: Floating a => (a -> a) -> Expr
fromFunction f = f X
toFunction :: Expr -> (Double -> Double)
toFunction X = \x -> x
toFunction (Const a) = const a
toFunction (Plus a b) = \x -> (toFunction a x) + (toFunction b x)
...
También puede definir una función diff :: Expr -> Expr que diferencia la expresión:
diff X = Const 1
diff (Const _) = Const 0
diff (Plus a b) = Plus (diff a) (diff b)
diff (Exp a) = Mult (diff a) (Exp a)
...
Tener toda estas partes deben significar que puede diferenciar (algunas) funciones, por ejemplo
f x = sin x + cos x * exp x
f' = toFunction . diff . fromFunction $ f
Advertencias:
Eq instancia para Expr es complicado (que es equivalente al problema de la parada, ya que es básicamente preguntando si dos funciones son iguales),Para que esto sea general necesita más que un solo 'X' comstructor. Y de hecho, la instancia 'Eq' es difícil. Una vez lo intenté, pero mi verificación de igualdad no pudo finalizar en un tiempo visible con expresiones más complicadas que, p. Ej. '∂/∂x (a + x)/sin x'. – leftaroundabout
Dependiendo de qué funciones agregue realmente a su tipo de datos de Expr, puede o no ser equivalente al problema de detención. En algunos casos, puede normalizar sus expresiones y ver si son equivalentes. O puede hacer un sistema de reescritura (que de alguna manera es equivalente a calcular formas normales), que puede decidir si dos expresiones son iguales en la evaluación con toFunction. – danr
En general, es imposible probar las funciones para igualdad, ya que la igualdad de funciones debe ser extensional, es decir, dos funciones son iguales si dan los mismos resultados para todos los argumentos.
Pero hay otras formas de definir derivadas en Haskell que usan diferentes tipos. Por ejemplo, Automatic Differentiation, simpler version of AD.
+1 - pero los detalles sobre las otras formas de definir los derivados serían agradables. –
No estoy interesado en la diferenciación numérica. –
No es una diferencia numérica, es muy diferente de eso. No es ni numérico ni simbólico, sino la tercera alternativa misteriosa. :) – augustss
Puedes hacerlo numéricamente usando, 'f '(x) = (f (x + dx) - f (x))/dx' o diferenciación automática. Lo que intenta hacer es imposible en el caso general de los lenguajes Turing-Complete. –