haskell - 在纯函数式语言中,是否有算法来获得反函数?

在像Haskell这样的纯函数式语言中,是否存在一个算法来获取函数的逆,当它是双射的时(编辑)? 是否有一种特定的方式来编程你的功能呢?

9个解决方案
90 votes

在某些情况下,是的! 有一篇名为Bidirectionalization for free的漂亮论文! 讨论了一些情况 - 当你的函数具有足够的多态性时 - 在可能的情况下,完全自动地导出反函数。 (它还讨论了当函数不是多态时,什么使问题变得困难。)

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

Daniel Wagner answered 2019-08-13T21:12:22Z
31 votes

不,一般来说,这是不可能的。

证明:考虑类型的双射函数

type F = [Bit] -> [Bit]

data Bit = B0 | B1

假设我们有一个g j这样的逆变器f。假设我们已经测试了它的功能inv f,通过确认

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

由于输出中的第一个g j必须在一段有限时间之后出现,因此我们在inv f实际评估我们的测试输入以获得此结果的深度上都有一个上限f,以及它可以调用的次数 inv.现在定义一系列函数

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

显然,对于所有g j,f是一个双射,实际上是自反。 所以我们应该能够证实

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

但为了实现这一点,g j也需要

  • 评估g j,深度为f
  • 评价g j,价格至少f不同的清单匹配inv f

到目前为止,g j中至少有一个与f无法区分,并且由于inv f没有完成这些评估中的任何一个,inv不可能将它分开 - 除了自己做一些运行时测量之外, 这是唯一可能在IO Monad

leftaroundabout answered 2019-08-13T21:13:53Z
16 votes

你可以在维基百科上查找它,它叫做可逆计算。

一般情况下,您无法执行此操作,并且没有一种功能语言具有该选项。 例如:

f :: a -> Int
f _ = 1

此功能没有反转。

mck answered 2019-08-13T21:14:31Z
13 votes

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

amalloy answered 2019-08-13T21:14:57Z
8 votes

像这样的任务几乎总是不可判定的。 您可以为某些特定功能提供解决方案,但不是一般的。

在这里,您甚至无法识别哪些函数具有逆。 引用Barendregt,H。P. Lambda微积分:它的语法和语义。 北荷兰,阿姆斯特丹(1984年):

如果一组lambda-terms既不是空集也不是全集,那么它们是非常重要的。 如果A和B是在(β)相等下关闭的两个非平凡的,不相交的lambda项集合,那么A和B是递归不可分的。

让我们将A表示为表示可逆函数的lambda项,将B表示为其余部分。 两者都是非空的,并且在beta等式下关闭。 因此,无法确定某个功能是否可逆。

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

Petr Pudlák answered 2019-08-13T21:15:51Z
8 votes

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

你想要做的是运行域的元素,看看它们是否等于你试图反转的范围的元素,并采取第一个有效的范围:

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

既然你已经说过invert (mapBi add1Bi) [1,5,6]是一个双射,那么必然只有一个这样的元素。 当然,诀窍是确保域的枚举实际上在有限时间内到达所有元素。 如果你试图将双射从[0,4,5]转换为Bi,那么使用-4将无法正常工作,因为你永远不会得到负数。 具体而言,inv ([0,1 ..] ++ [-1,-2 ..]) (+1) (-3)永远不会产生价值。

但是,invert (mapBi add1Bi) [1,5,6]将工作,因为它按以下顺序运行整数[0,4,5]。确实Bi及时返回-4

Control.Monad.Omega包可以帮助您以一种好的方式运行元组等列表; 我确定还有更多类似的套餐 - 但我不了解它们。


当然,这种方法相当低调和蛮力,更不用说丑陋和低效! 因此,我将在您的问题的最后部分,关于如何撰写&#39;双射。 Haskell的类型系统并不能证明一个函数是一个双向函数 - 你真的想要像Agda这样的东西 - 但它愿意相信你。

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

您能否在种类[0,4,5]Bi之间定义invert (mapBi add1Bi) [1,5,6]的数据类型:

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

以及尽可能多的常数(你可以说&#39;我知道他们&#39;重新注射!&#39;)如你所愿,例如:

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常数的次数可能非常有限。

毕竟,如果你知道一个函数是一个双射函数,那么你希望在你的头脑中有一个关于这个事实的证明草图,Curry-Howard同构应该能够变成一个程序:-)

yatima2975 answered 2019-08-13T21:17:37Z
4 votes

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

基本上,假设你有(,),那Either确实是一个bjiection。 你可以用一种非常愚蠢的方式计算逆RecursivelyEnumerable

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

如果(,)是双射并且Either真正产生了所有值RecursivelyEnumerable,那么你最终会遇到Enumerable这样的Enumerable

具有(,)Either实例的类型可以轻松制作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

对于(,)类型的析取也是如此:

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这样做的事实可能意味着我们可以为任何代数数据类型执行此操作。

Luis Casillas answered 2019-08-13T21:18:41Z
3 votes

并非每个函数都有反转。 如果将讨论限制为一对一函数,则反转任意函数的能力可以破解任何密码系统。 我们有点希望这是不可行的,即使在理论上也是如此!

Jeffrey Scofield answered 2019-08-13T21:19:10Z
2 votes

不,并非所有功能都具有逆转功能。 例如,这个函数的反函数是什么?

f x = 1
Dirk Holsopple answered 2019-08-13T21:19:38Z
translate from https://stackoverflow.com:/questions/13404208/in-pure-functional-languages-is-there-an-algorithm-to-get-the-inverse-function