在纯函数式语言中,是否有algorithm来获得反函数?

在像Haskell这样的纯函数语言中,是否有一种algorithm来获得函数的反函数,(编辑)它是否是双射的? 有没有一个特定的方式来编程你的function,所以呢?

在某些情况下,是的! 有一个漂亮的纸称为双向免费! 它讨论了一些情况 – 当你的函数足够多态时 – 在可能的地方,完全自动地派生一个反函数。 (它还讨论了当函数不是多态时,什么使得问题变得困难)。

在你的函数是可逆的情况下,你得到的是反函数(带有一个伪input)。 在其他情况下,你会得到一个函数,试图“合并”一个旧的input值和一个新的输出值。

不,一般情况下是不可能的。

certificate:考虑types的双射函数

 type F = [Bit] -> [Bit] 

 data Bit = B0 | B1 

假设我们有一个逆变器inv :: F -> F ,使得inv f . f ≡ id inv f . f ≡ id 。 假设我们通过确认函数f = idtesting它

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

由于输出中的第一个B0必定是在一定的时间之后才出现的,因此我们在inv实际评估testinginput的深度以及获得这个结果的次数上都有一个上界n f 。 现在定义一个函数族

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

显然,对于所有0<j≤ngj是一个双射,实际上是0<j≤n 。 所以我们应该能够确认

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

但为了实现这一点, inv (gj)也需要

  • 评估gj (B1 : repeat B0)至深度n+j > n
  • 评估head $ gjl至lessn不同的列表匹配replicate (n+j) B0 ++ B1 : ls

到目前为止,至less有一个gjf没有区别,而且由于inv f没有完成任何一个这样的评估,所以inv不可能把它分开 – 它本身并不做一些运行时测量,只能在IO Monad

你可以在维基百科上查看它,它被称为可逆计算 。

一般来说,你不能这样做,没有一种function语言有这个选项。 例如:

 f :: a -> Int f _ = 1 

这个function没有反转。

不是在大多数函数式语言中,而是在逻辑编程或关系式编程中,您定义的大多数函数实际上不是函数,而是“关系”,并且这些函数可以在两个方向上使用。 看例如prolog或kanren。

像这样的任务几乎总是不可判定的。 您可以为某些特定function提供解决scheme,但通常不会。

在这里,你甚至不能识别哪个函数有反函数。 引用Barendregt,HP的Lambda微积分:它的语法和语义。 北荷兰,阿姆斯特丹(1984) :

如果一组lambda-项既不是空集也不是全集。 如果A和B是两个平凡的不相交的lambda项的集合,那么A和B是recursion不可分的。

让我们把A作为表示可逆函数的lambdaexpression式的集合,其余的是B的集合。 两者都是非空的,并在beta平等下closures。 所以决定函数是否可逆是不可能的。

(这适用于无types的lambda演算TBH我不知道当我们知道我们想要反转的函数的types时,参数是否可以直接适用于types化的lambda演算,但是我很肯定它会类似。)

如果你可以枚举函数的域,并且可以比较范围的元素的相等性,你可以 – 以一种相当直接的方式。 通过枚举我的意思是有一个可用的所有元素的列表。 我会坚持Haskell,因为我不知道Ocaml(甚至如何正确使用它;-)

你想要做的是遍历域的元素,看看它们是否等于你想要颠倒的范围的元素,并采取第一个工作:

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

既然你已经说过f是一个双射,那么一定是唯一一个这样的元素。 当然,诀窍是确保您的域枚举实际上在有限的时间内到达所有元素。 如果你正在尝试将IntegerInteger ,使用[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的types系统并不是要certificate函数是双射的,你真的想要Agda这样的东西,但它愿意相信你。

(警告:未经testing的代码如下)

那么你可以定义typesab之间的Bijection的数据types:

 data Bi ab = 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 aa idBi = Bi id id invertBi :: Bi ab -> Bi ba invertBi (Bi ai) = (Bi ia) composeBi :: Bi ab -> Bi bc -> Bi ac composeBi (Bi a1 i1) (Bi a2 i2) = Bi (a2 . a1) (i1 . i2) mapBi :: Bi ab -> Bi [a] [b] mapBi (Bi ai) = Bi (map a) (map i) bruteForceBi :: Eq b => [a] -> (a -> b) -> Bi ab bruteForceBi domain f = Bi f (inv domain f) 

我想你可以做invert (mapBi add1Bi) [1,5,6]并得到[0,4,5] 。 如果你用巧妙的方式select你的组合器,我认为你必须手工编写Bi常数的次数可能非常有限。

毕竟,如果你知道一个函数是一个双射,你可能希望在你脑海中有一个这个事实的certificate,这个Curry-Howard同构应该能够变成一个程序:-)

我最近一直在处理这样的问题,不,我会说(a)在很多情况下并不困难,但(b)根本没有效率。

基本上,假设你有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 fb = find (\a -> fa == b) enumerate 

如果f是一个双射, enumerate真正产生了a所有值,那么你最终会碰到a这样的fa == b

具有BoundedEnum实例的types可以被简单地RecursivelyEnumerable化为RecursivelyEnumerable 。 成对的Enumerabletypes也可以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 

Enumerabletypes的分离也是一样的:

 instance (Enumerable a, Enumerable b) => Enumerable (Either ab) where enumerate = enumerateEither enumerate enumerate enumerateEither :: [a] -> [b] -> [Either ab] enumerateEither [] ys = map Right ys enumerateEither xs [] = map Left xs enumerateEither (x:xs) (y:ys) = Left x : Right y : enumerateEither xs ys 

事实上,我们可以为(,)Either这两者做这可能意味着我们可以做任何代数数据types。

并不是每个函数都有一个相反的 如果将讨论局限于一对一的function,反转任意函数的能力授予破解任何密码系统的能力。 我们必须希望这是不可行的,即使在理论上也是如此!

不,并不是所有的function都有倒序。 例如,这个函数的反例是什么?

 fx = 1