在纯函数式语言中，是否有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≤n ， gj是一个双射，实际上是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有一个gj与f没有区别，而且由于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是一个双射，那么一定是唯一一个这样的元素。 当然，诀窍是确保您的域枚举实际上在有限的时间内到达所有元素。 如果你正在尝试将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的types系统并不是要certificate函数是双射的，你真的想要Agda这样的东西，但它愿意相信你。
（警告：未经testing的代码如下）
那么你可以定义typesa和b之间的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 。
具有Bounded和Enum实例的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
