Есть ли в чистых функциональных языках алгоритм для получения обратной функции?

100

В чистых функциональных языках, таких как Haskell, есть ли алгоритм, позволяющий получить обратную функцию (редактировать), если она биективна? И есть ли какой-то особый способ запрограммировать вашу функцию?

Майя Виктор
источник
5
С математической точки зрения будет правильно сказать, что в случае f x = 1, обратное к 1 является набором целых чисел, а обратное к чему-либо еще является пустым набором. Независимо от того, что говорят некоторые ответы, то, что функция не является биективной, не является самой большой проблемой.
Karolis Juodelė
2
Правильный ответ - ДА, но это неэффективно. Пусть f: A -> B и A конечны, тогда, если b € B, вы «всего лишь» должны проверить все f (A), чтобы найти все a € A, для которых f (a) = b. В квантовом компьютере, возможно, будет сложность O (размер (a)). Конечно, вы ищете практический алгоритм. Это не (имеет O (2 ^ size (a))), но существует ...
josejuan
QuickCheck делает это точно (они ищут False в f: A -> Bool).
josejuan
4
@ KarolisJuodelė: Я не согласен; это обычно не то, что подразумевается под инверсией. Практически каждый раз, когда я встречаюсь с этим термином, обратная fфункция - gэто f . g = idи g . f = id. В этом случае ваш кандидат даже не проверяет типаж.
Ben Millwood
3
@BenMillwood, ты прав. То, что я сказал, называется обратным изображением, а не обратной функцией. Я хотел сказать, что ответы, указывающие на f x = 1отсутствие обратного, используют очень узкий подход и игнорируют всю сложность проблемы.
Karolis Juodelė

Ответы:

101

В некоторых случаях да! Есть красивая статья под названием " Двунаправленность бесплатно!" в котором обсуждается несколько случаев - когда ваша функция достаточно полиморфна - где это возможно, полностью автоматически получить обратную функцию. (Здесь также обсуждается, что усложняет проблему, когда функции не полиморфны.)

В случае, если ваша функция обратима, вы получите обратное (с ложным входом); в других случаях вы получаете функцию, которая пытается «объединить» старое входное значение и новое выходное значение.

Даниэль Вагнер
источник
3
Вот более свежая статья, в которой анализируется состояние дел в области двунаправленности. Он включает в себя три семейства техник, в том числе «синтаксический» подход и подход, основанный на комбинаторах: iai.uni-bonn.de/~jv/ssgip-bidirectional-final.pdf
sclv
И просто упомяну, что в 2008 году в -cafe было сообщение со злобным хаком для инвертирования putфункций в любые производные структуры записей Data: haskell.org/pipermail/haskell-cafe/2008-April/042193.html с использованием подхода, аналогичного который позже был представлен (более строго, в более общем плане, более принципиально и т. д.) как «бесплатно».
sclv
Сейчас 2017 год, и, конечно, ссылка на статью больше не действительна, вот обновленная: pdfs.semanticscholar.org/5f0d/…
Мина Габриэль
37

Нет, это вообще невозможно.

Доказательство: рассмотрим биективные функции типа

type F = [Bit] -> [Bit]

с участием

data Bit = B0 | B1

Предположим, у нас есть такой инвертор inv :: F -> F, что inv f . f ≡ id. Допустим, мы проверили его на функцию f = id, подтвердив, что

inv f (repeat B0) -> (B0 : ls)

Поскольку этот первый B0результат должен был появиться через некоторое конечное время, у нас есть верхняя граница nкак глубины, до которой invфактически оценивались наши тестовые входные данные для получения этого результата, так и количества раз, которое он мог вызвать f. Определите теперь семейство функций

g j (B1 : B0 : ... (n+j times) ... B0 : ls)
   = B0 : ... (n+j times) ... B0 : B1 : ls
g j (B0 : ... (n+j times) ... B0 : B1 : ls)
   = B1 : B0 : ... (n+j times) ... B0 : ls
g j l = l

Очевидно, что для всех 0<j≤n, g jбиекция, на самом деле самообратных. Итак, мы сможем подтвердить

inv (g j) (replicate (n+j) B0 ++ B1 : repeat B0) -> (B1 : ls)

но для этого inv (g j)потребовалось бы либо

  • оценить g j (B1 : repeat B0)до глубиныn+j > n
  • оценить head $ g j lпо крайней мере nсоответствие различных списковreplicate (n+j) B0 ++ B1 : ls

До этого момента, по крайней мере, одно из g jних неотличимо от f, и, поскольку inv fне было выполнено ни одной из этих оценок, invневозможно было отличить его отдельно - за исключением выполнения некоторых измерений времени выполнения самостоятельно, что возможно только в IO Monad.

                                                                                                                                   ⬜

слева
источник
19

Вы можете найти это в Википедии, это называется Reversible Computing .

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

f :: a -> Int
f _ = 1

У этой функции нет обратного.

mck
источник
1
Было бы неправильно сказать, что у fэтого есть обратная функция, просто обратная функция является недетерминированной функцией?
Мэтт Фенвик
10
@MattFenwick В таких языках, как Haskell, например, функции просто не являются недетерминированными (без изменения типов и способа их использования). Не существует никакой функции Haskell, g :: Int -> aкоторая была бы обратной f, даже если вы можете описать обратную функцию fматематически.
Бен
2
@Matt: Посмотрите "снизу" в функциональном программировании и логике. «Дно» - это «невозможное» значение либо потому, что оно противоречиво, не прекращается, либо потому, что оно является решением неразрешимой проблемы (это больше, чем просто противоречие - мы можем методично «преследовать» решение, исследуя дизайн пробел с использованием «undefined» и «error» во время разработки). «Нижний» x имеет тип a. Он «обитает» (или является «ценностью») любого типа. Это логическое противоречие, поскольку типы суть предложения, и не существует значения, которое удовлетворяет каждому предложению. Ищите хорошие обсуждения в Haskell-Cafe
nomen
2
@Matt: Вместо того, чтобы характеризовать отсутствие инверсий в терминах недетерминизма, нужно охарактеризовать его в терминах дна. Обратное к f _ = 1 - это дно, поскольку оно должно населять каждый тип (в качестве альтернативы, это дно, поскольку f не имеет обратной функции для любого типа с более чем одним элементом - я думаю, аспект, на котором вы сосредоточились). Пребывание внизу можно воспринимать как положительно, так и отрицательно как утверждения о ценностях. Можно разумно говорить об инверсии произвольной функции как о «ценностном» дне. (Хотя это «не совсем» значение)
nomen
1
Заглянув сюда намного позже, я думаю, что понимаю, что Мэтт имеет в виду: мы часто моделируем недетерминизм с помощью списков, и мы могли бы сделать то же самое для обратных. Пусть обратное f x = 2 * xВЕ f' x = [x / 2], а затем обратное f _ = 1IS f' 1 = [minBound ..]; f' _ = []. То есть для 1 есть много обратных значений, а для любого другого значения нет.
amalloy 04
16

Не в большинстве функциональных языков, но в логическом программировании или реляционном программировании, большинство функций, которые вы определяете, на самом деле являются не функциями, а «отношениями», и их можно использовать в обоих направлениях. См., Например, пролог или канрен.

сплав
источник
1
Или Mercury , который в остальном во многом разделяет дух Haskell. - Хорошее замечание, +1.
leftaround примерно
11

Подобные задачи почти всегда неразрешимы. У вас может быть решение для некоторых конкретных функций, но не в целом.

Здесь вы даже не можете распознать, какие функции имеют инверсию. Цитата Барендрегта, HP. Лямбда-исчисление: его синтаксис и семантика. Северная Голландия, Амстердам (1984) :

Набор лямбда-членов нетривиален, если он не является ни пустым, ни полным. Если A и B два нетривиальных непересекающихся набора лямбда-членов, замкнутых относительно (бета) равенства, то A и B рекурсивно неразделимы.

Возьмем A как набор лямбда-членов, которые представляют обратимые функции, а B - все остальное. Оба непусты и закрыты по бета-равенству. Таким образом, невозможно решить, является ли функция обратимой или нет.

(Это относится к нетипизированному лямбда-исчислению. ТБХ Я не знаю, можно ли напрямую адаптировать аргумент к типизированному лямбда-исчислению, если мы знаем тип функции, которую хотим инвертировать. Но я почти уверен, что это будет аналогичный.)

Петр Пудлак
источник
11

Если вы можете перечислить область определения функции и сравнить элементы диапазона на предмет равенства, вы можете - довольно простым способом. Под перечислением я подразумеваю наличие списка всех доступных элементов. Я буду придерживаться Haskell, так как я не знаю Ocaml (или даже как правильно его использовать ;-)

Что вы хотите сделать, так это пройтись по элементам домена и посмотреть, равны ли они элементу диапазона, который вы пытаетесь инвертировать, и выбрать первый, который работает:

inv :: Eq b => [a] -> (a -> b) -> (b -> a)
inv domain f b = head [ a | a <- domain, f a == b ]

Поскольку вы заявили, что fэто биекция, обязательно должен быть один и только один такой элемент. Уловка, конечно же, состоит в том, чтобы гарантировать, что ваше перечисление домена действительно достигнет всех элементов за конечное время . Если вы пытаетесь инвертировать биекцию с Integerна Integer, использование [0,1 ..] ++ [-1,-2 ..]не сработает, так как вы никогда не доберетесь до отрицательных чисел. Конкретно, inv ([0,1 ..] ++ [-1,-2 ..]) (+1) (-3)никогда не даст значения.

Однако 0 : concatMap (\x -> [x,-x]) [1..]это сработает, поскольку целые числа проходят в следующем порядке [0,1,-1,2,-2,3,-3, and so on]. Действительно inv (0 : concatMap (\x -> [x,-x]) [1..]) (+1) (-3)оперативно возвращается -4!

Пакет Control.Monad.Omega может помочь вам хорошо просмотреть списки кортежей и так далее; Я уверен, что таких пакетов много, но я их не знаю.


Конечно, это довольно простой и грубый подход, не говоря уже о безобразном и неэффективном! Итак, я закончу несколькими замечаниями по последней части вашего вопроса о том, как «писать» биекции. Система типов Haskell не способна доказать, что функция является взаимно однозначной - для этого вам действительно нужно что-то вроде Agda - но она готова вам доверять.

(Предупреждение: следует непроверенный код)

Итак, можете ли вы определить тип данных Bijections между типами aи b:

data Bi a b = Bi {
    apply :: a -> b,
    invert :: b -> a 
}

вместе с любым количеством констант (где вы можете сказать: «Я знаю, что это биекция!»), например:

notBi :: Bi Bool Bool
notBi = Bi not not

add1Bi :: Bi Integer Integer
add1Bi = Bi (+1) (subtract 1)

и пара умных комбинаторов, таких как:

idBi :: Bi a a 
idBi = Bi id id

invertBi :: Bi a b -> Bi b a
invertBi (Bi a i) = (Bi i a)

composeBi :: Bi a b -> Bi b c -> Bi a c
composeBi (Bi a1 i1) (Bi a2 i2) = Bi (a2 . a1) (i1 . i2)

mapBi :: Bi a b -> Bi [a] [b]
mapBi (Bi a i) = Bi (map a) (map i)

bruteForceBi :: Eq b => [a] -> (a -> b) -> Bi a b
bruteForceBi domain f = Bi f (inv domain f)

Думаю, тогда можно было сделать invert (mapBi add1Bi) [1,5,6]и получить [0,4,5]. Если вы выберете комбинаторы с умом, я думаю, что количество раз, которое вам придется писать Biконстанту вручную, может быть весьма ограниченным.

В конце концов, если вы знаете, что функция является биекцией, вы, надеюсь, будете иметь в своей голове схему доказательства этого факта, которую изоморфизм Карри-Ховарда сможет превратить в программу :-)

yatima2975
источник
6

Я недавно сталкивался с подобными проблемами, и нет, я бы сказал, что (а) во многих случаях это не сложно, но (б) это совсем неэффективно.

В принципе, предположим, что у вас есть f :: a -> b, и это fдействительно обман. Вы можете вычислить обратное f' :: b -> aочень глупым способом:

import Data.List

-- | Class for types whose values are recursively enumerable.
class Enumerable a where
    -- | Produce the list of all values of type @a@.
    enumerate :: [a]

 -- | Note, this is only guaranteed to terminate if @f@ is a bijection!
invert :: (Enumerable a, Eq b) => (a -> b) -> b -> Maybe a
invert f b = find (\a -> f a == b) enumerate

Если fэто взаимное соответствие и enumerateдействительно производит все значения a, то в конечном итоге вы попадете в aтакое, что f a == b.

Типы, у которых есть a Boundedи Enumэкземпляр, можно создать тривиально RecursivelyEnumerable. EnumerableТакже могут быть составлены пары типов Enumerable:

instance (Enumerable a, Enumerable b) => Enumerable (a, b) where
    enumerate = crossWith (,) enumerate enumerate

crossWith :: (a -> b -> c) -> [a] -> [b] -> [c]
crossWith f _ [] = []
crossWith f [] _ = []
crossWith f (x0:xs) (y0:ys) =
    f x0 y0 : interleave (map (f x0) ys) 
                         (interleave (map (flip f y0) xs)
                                     (crossWith f xs ys))

interleave :: [a] -> [a] -> [a]
interleave xs [] = xs
interleave [] ys = []
interleave (x:xs) ys = x : interleave ys xs

То же самое и с дизъюнкциями Enumerableтипов:

instance (Enumerable a, Enumerable b) => Enumerable (Either a b) where
    enumerate = enumerateEither enumerate enumerate

enumerateEither :: [a] -> [b] -> [Either a b]
enumerateEither [] ys = map Right ys
enumerateEither xs [] = map Left xs
enumerateEither (x:xs) (y:ys) = Left x : Right y : enumerateEither xs ys

Тот факт, что мы можем сделать это и для, (,)и, Eitherвероятно, означает, что мы можем сделать это для любого алгебраического типа данных.

Луис Касильяс
источник
5

Не у каждой функции есть обратная. Если вы ограничите обсуждение однозначными функциями, возможность инвертировать произвольную функцию дает возможность взломать любую криптосистему. Мы как бы должны надеяться, что это невозможно даже теоретически!

Джеффри Скофилд
источник
13
Любая криптосистема (за исключением нескольких странных, таких как одноразовые блокноты, которые невозможны по другим причинам) может быть взломана грубой силой. Это не делает их менее полезными, и это не будет непрактично дорогой функцией инверсии.
Это правда? если вы думаете о функции шифрования, как о том, что String encrypt(String key, String text)без ключа вы все равно ничего не сможете сделать. РЕДАКТИРОВАТЬ: Плюс то, что сказал Делнан.
mck
@MaciekAlbin Зависит от вашей модели атаки. Атаки на выбранный открытый текст, например, могут позволить извлечь ключ, который затем позволит атаковать другие зашифрованные тексты, зашифрованные этим ключом.
Под «выполнимым» я имел в виду то, что можно сделать в любое разумное время. Я не имел в виду «вычислимый» (я почти уверен).
Джеффри Скофилд
@JeffreyScofield Я понимаю вашу точку зрения. Но я должен сказать, что меня смущает «выполнимое в теории» - разве (наше определение) осуществимость не относится только к тому, насколько сложно это сделать практически?
5

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

bijective_function x = x*2+1

main = do
    print $ bijective_function 3
    print $ inverse_function bijective_function (bijective_function 3)

data Expr = X | Const Double |
            Plus Expr Expr | Subtract Expr Expr | Mult Expr Expr | Div Expr Expr |
            Negate Expr | Inverse Expr |
            Exp Expr | Log Expr | Sin Expr | Atanh Expr | Sinh Expr | Acosh Expr | Cosh Expr | Tan Expr | Cos Expr |Asinh Expr|Atan Expr|Acos Expr|Asin Expr|Abs Expr|Signum Expr|Integer
       deriving (Show, Eq)

instance Num Expr where
    (+) = Plus
    (-) = Subtract
    (*) = Mult
    abs = Abs
    signum = Signum
    negate = Negate
    fromInteger a = Const $ fromIntegral a

instance Fractional Expr where
    recip = Inverse
    fromRational a = Const $ realToFrac a
    (/) = Div

instance Floating Expr where
    pi = Const pi
    exp = Exp
    log = Log
    sin = Sin
    atanh = Atanh
    sinh = Sinh
    cosh = Cosh
    acosh = Acosh
    cos = Cos
    tan = Tan
    asin = Asin
    acos = Acos
    atan = Atan
    asinh = Asinh

fromFunction f = f X

toFunction :: Expr -> (Double -> Double)
toFunction X = \x -> x
toFunction (Negate a) = \a -> (negate a)
toFunction (Const a) = const a
toFunction (Plus a b) = \x -> (toFunction a x) + (toFunction b x)
toFunction (Subtract a b) = \x -> (toFunction a x) - (toFunction b x)
toFunction (Mult a b) = \x -> (toFunction a x) * (toFunction b x)
toFunction (Div a b) = \x -> (toFunction a x) / (toFunction b x)


with_function func x = toFunction $ func $ fromFunction x

simplify X = X
simplify (Div (Const a) (Const b)) = Const (a/b)
simplify (Mult (Const a) (Const b)) | a == 0 || b == 0 = 0 | otherwise = Const (a*b)
simplify (Negate (Negate a)) = simplify a
simplify (Subtract a b) = simplify ( Plus (simplify a) (Negate (simplify b)) )
simplify (Div a b) | a == b = Const 1.0 | otherwise = simplify (Div (simplify a) (simplify b))
simplify (Mult a b) = simplify (Mult (simplify a) (simplify b))
simplify (Const a) = Const a
simplify (Plus (Const a) (Const b)) = Const (a+b)
simplify (Plus a (Const b)) = simplify (Plus (Const b) (simplify a))
simplify (Plus (Mult (Const a) X) (Mult (Const b) X)) = (simplify (Mult (Const (a+b)) X))
simplify (Plus (Const a) b) = simplify (Plus (simplify b) (Const a))
simplify (Plus X a) = simplify (Plus (Mult 1 X) (simplify a))
simplify (Plus a X) = simplify (Plus (Mult 1 X) (simplify a))
simplify (Plus a b) = (simplify (Plus (simplify a) (simplify b)))
simplify a = a

inverse X = X
inverse (Const a) = simplify (Const a)
inverse (Mult (Const a) (Const b)) = Const (a * b)
inverse (Mult (Const a) X) = (Div X (Const a))
inverse (Plus X (Const a)) = (Subtract X (Const a))
inverse (Negate x) = Negate (inverse x)
inverse a = inverse (simplify a)

inverse_function x = with_function inverse x

Этот пример работает только с арифметическими выражениями, но его, вероятно, можно было бы обобщить и для работы со списками.

Андерсон Грин
источник
4

Нет, не все функции имеют даже обратные. Например, что было бы обратной этой функции?

f x = 1
Дирк Холсоппл
источник
Ваша функция является константой, здесь речь идет о биективных функциях.
Soleil - Матье Прево