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

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

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

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.

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

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

f :: a -> Int
f _ = 1

эта функция не имеет обратной.

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

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

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

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

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

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

если вы можете перечислить домен функции и можете сравнить элементы диапазона для равенства, вы можете - довольно простым способом. Под перечислением я подразумеваю наличие списка всех доступных элементов. Я буду придерживаться 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!

The управление.Монада.Омега пакет может помочь вам запустить списки кортежей и т. д. В хорошем смысле; я уверен, что таких пакетов больше, но я их не знаю.

---

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

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

так что вы можете определить тип данных Bijection s между типами 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 константа вручную может быть довольно ограниченной.

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

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

в принципе, предположим, что у вас есть f :: a -> b и f это действительно bjiection. Вы можете вычислить обратное 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.

типы, которые имеют 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 вероятно, это означает, что мы можем сделать это для любого алгебраического типа данных.

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

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

f x = 1