В чистых функциональных языках, таких как Haskell, есть ли алгоритм, позволяющий получить обратную функцию (редактировать), если она биективна? И есть ли какой-то особый способ запрограммировать вашу функцию?
haskell
clojure
functional-programming
ocaml
Майя Виктор
источник
источник
f x = 1
, обратное к 1 является набором целых чисел, а обратное к чему-либо еще является пустым набором. Независимо от того, что говорят некоторые ответы, то, что функция не является биективной, не является самой большой проблемой.f
функция -g
этоf . g = id
иg . f = id
. В этом случае ваш кандидат даже не проверяет типаж.f x = 1
отсутствие обратного, используют очень узкий подход и игнорируют всю сложность проблемы.Ответы:
В некоторых случаях да! Есть красивая статья под названием " Двунаправленность бесплатно!" в котором обсуждается несколько случаев - когда ваша функция достаточно полиморфна - где это возможно, полностью автоматически получить обратную функцию. (Здесь также обсуждается, что усложняет проблему, когда функции не полиморфны.)
В случае, если ваша функция обратима, вы получите обратное (с ложным входом); в других случаях вы получаете функцию, которая пытается «объединить» старое входное значение и новое выходное значение.
источник
put
функций в любые производные структуры записейData
: haskell.org/pipermail/haskell-cafe/2008-April/042193.html с использованием подхода, аналогичного который позже был представлен (более строго, в более общем плане, более принципиально и т. д.) как «бесплатно».Нет, это вообще невозможно.
Доказательство: рассмотрим биективные функции типа
с участием
Предположим, у нас есть такой инвертор
inv :: F -> F
, чтоinv f . f ≡ id
. Допустим, мы проверили его на функциюf = id
, подтвердив, чтоПоскольку этот первый
B0
результат должен был появиться через некоторое конечное время, у нас есть верхняя границаn
как глубины, до которойinv
фактически оценивались наши тестовые входные данные для получения этого результата, так и количества раз, которое он мог вызватьf
. Определите теперь семейство функцийОчевидно, что для всех
0<j≤n
,g j
биекция, на самом деле самообратных. Итак, мы сможем подтвердитьно для этого
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
.⬜
источник
Вы можете найти это в Википедии, это называется Reversible Computing .
В общем, вы не можете этого сделать, и ни один из функциональных языков не имеет такой возможности. Например:
У этой функции нет обратного.
источник
f
этого есть обратная функция, просто обратная функция является недетерминированной функцией?g :: Int -> a
которая была бы обратнойf
, даже если вы можете описать обратную функциюf
математически.f x = 2 * x
ВЕf' x = [x / 2]
, а затем обратноеf _ = 1
ISf' 1 = [minBound ..]; f' _ = []
. То есть для 1 есть много обратных значений, а для любого другого значения нет.Не в большинстве функциональных языков, но в логическом программировании или реляционном программировании, большинство функций, которые вы определяете, на самом деле являются не функциями, а «отношениями», и их можно использовать в обоих направлениях. См., Например, пролог или канрен.
источник
Подобные задачи почти всегда неразрешимы. У вас может быть решение для некоторых конкретных функций, но не в целом.
Здесь вы даже не можете распознать, какие функции имеют инверсию. Цитата Барендрегта, HP. Лямбда-исчисление: его синтаксис и семантика. Северная Голландия, Амстердам (1984) :
Возьмем A как набор лямбда-членов, которые представляют обратимые функции, а B - все остальное. Оба непусты и закрыты по бета-равенству. Таким образом, невозможно решить, является ли функция обратимой или нет.
(Это относится к нетипизированному лямбда-исчислению. ТБХ Я не знаю, можно ли напрямую адаптировать аргумент к типизированному лямбда-исчислению, если мы знаем тип функции, которую хотим инвертировать. Но я почти уверен, что это будет аналогичный.)
источник
Если вы можете перечислить область определения функции и сравнить элементы диапазона на предмет равенства, вы можете - довольно простым способом. Под перечислением я подразумеваю наличие списка всех доступных элементов. Я буду придерживаться Haskell, так как я не знаю Ocaml (или даже как правильно его использовать ;-)
Что вы хотите сделать, так это пройтись по элементам домена и посмотреть, равны ли они элементу диапазона, который вы пытаетесь инвертировать, и выбрать первый, который работает:
Поскольку вы заявили, что
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 - но она готова вам доверять.
(Предупреждение: следует непроверенный код)
Итак, можете ли вы определить тип данных
Bijection
s между типамиa
иb
:вместе с любым количеством констант (где вы можете сказать: «Я знаю, что это биекция!»), например:
и пара умных комбинаторов, таких как:
Думаю, тогда можно было сделать
invert (mapBi add1Bi) [1,5,6]
и получить[0,4,5]
. Если вы выберете комбинаторы с умом, я думаю, что количество раз, которое вам придется писатьBi
константу вручную, может быть весьма ограниченным.В конце концов, если вы знаете, что функция является биекцией, вы, надеюсь, будете иметь в своей голове схему доказательства этого факта, которую изоморфизм Карри-Ховарда сможет превратить в программу :-)
источник
Я недавно сталкивался с подобными проблемами, и нет, я бы сказал, что (а) во многих случаях это не сложно, но (б) это совсем неэффективно.
В принципе, предположим, что у вас есть
f :: a -> b
, и этоf
действительно обман. Вы можете вычислить обратноеf' :: b -> a
очень глупым способом:Если
f
это взаимное соответствие иenumerate
действительно производит все значенияa
, то в конечном итоге вы попадете вa
такое, чтоf a == b
.Типы, у которых есть a
Bounded
иEnum
экземпляр, можно создать тривиальноRecursivelyEnumerable
.Enumerable
Также могут быть составлены пары типовEnumerable
:То же самое и с дизъюнкциями
Enumerable
типов:Тот факт, что мы можем сделать это и для,
(,)
и,Either
вероятно, означает, что мы можем сделать это для любого алгебраического типа данных.источник
Не у каждой функции есть обратная. Если вы ограничите обсуждение однозначными функциями, возможность инвертировать произвольную функцию дает возможность взломать любую криптосистему. Мы как бы должны надеяться, что это невозможно даже теоретически!
источник
String encrypt(String key, String text)
без ключа вы все равно ничего не сможете сделать. РЕДАКТИРОВАТЬ: Плюс то, что сказал Делнан.В некоторых случаях можно найти обратную функцию к биективной функции, преобразовав ее в символическое представление. Основываясь на этом примере , я написал эту программу на Haskell, чтобы найти инверсии некоторых простых полиномиальных функций:
Этот пример работает только с арифметическими выражениями, но его, вероятно, можно было бы обобщить и для работы со списками.
источник
Нет, не все функции имеют даже обратные. Например, что было бы обратной этой функции?
источник