Подтвердить что ты не робот

Равенство функций в Haskell

Я пытаюсь определить функцию, которая возьмет функцию Double -> Double и вернет ее математическую производную. Я попытался сделать следующее:

der :: (Double -> Double) -> (Double -> Double)
der f
    | f == exp = exp
    | otherwise = undefined

но Haskell не поддерживает == на Double -> Double значениях. Я пытаюсь сделать невозможным в Haskell?

4b9b3361

ОТВЕТЫ

Ответ 1

Да, то, что вы пытаетесь сделать, невозможно в Haskell, и в целом: решение о том, равны ли две функции для всех возможных входов (без проверки только каждого входного значения, если это вообще возможно), эквивалентно решению проблемы остановки.

Тем не менее, в вашем конкретном случае вы можете обойти это, используя пользовательский тип, который имитирует Double (то есть имеет те же экземпляры, и поэтому может использоваться вместо него), но вместо вычисления числа он создает абстрактный представление операций, выполняемых функциями. Expr представляет правую часть определения математической функции 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
    ...

Затем, используя типы ранга 2, вы можете определить функции преобразования, которые преобразуют между функциями, которые принимают любые Floating и Expr ы:

{-# LANGUAGE Rank2Types #-}

fromFunction :: (forall a. Floating a => (a -> a)) -> Expr
fromFunction f = f X

toFunction :: Expr -> (Double -> Double)
toFunction X = \x -> x
toFunction (Const a) = const a
toFunction (Add a b) = \x -> (toFunction a x) + (toFunction b x)
...

Вы также можете определить функцию diff :: Expr → Expr которая дифференцирует выражение:

diff X = Const 1
diff (Const _) = Const 0
diff (Add a b) = Add (diff a) (diff b)
diff (Exp a) = Mult (diff a) (Exp a)
...

Наличие всех этих частей должно означать, что вы можете различать (некоторые) функции, например,

f x = sin x + cos x * exp x
f' = toFunction . diff . fromFunction $ f

Предостережения:

  • это не сработает вообще,
  • определить полный экземпляр Eq для Expr сложно (это эквивалентно проблеме Остановки, так как он в основном спрашивает, равны ли две функции),
  • Я на самом деле не проверял ни один из этого кода,
  • дифференцирование и реконструкция выполняются во время выполнения, поэтому очень вероятно, что результирующая функция будет очень медленной.

Ответ 2

В общем случае невозможно проверить функции для равенства, так как равенство функции должно быть экстенсиональным, т.е. две функции равны, если они дают одинаковые результаты для всех аргументов.

Но есть и другие способы определения производных в Haskell, которые используют разные типы. Например, Автоматическое дифференцирование, более простая версия AD.