4

Wolfgang Jeltsch撰写的关于基于 Haskell 的KiCS2实现Curry的相当引人入胜的 2013 年介绍性文章A Taste of Curry为组合器提供了以下定义inverse：

inverse :: (a -> b) -> (b -> a)
inverse f y | f x =:= y = x where x free

（注意：对于不熟悉库里的路人来说，这会做类似inverse (+1) 3 == 2and inverse (*3) 12 == 4and之类的事情，以及无数其他令人难以置信的很棒的事情）inverse htmlHodeToStr == parseHtmlNode

此外，它还提供了 2 个替代但等效的（非确定性）split :: [a] -> ([a], [a])函数定义：

split :: [a] -> ([a],[a])
split list | front ++ rear =:= list = (front,rear)

和

split' :: [a] -> ([a],[a])
split' (xs ++ ys) = (xs,ys)

以及其他一些颇具启发性的定义，但是超出了本文的范围。

然而，我的想法使我尝试了一种替代的、紧凑的定义，inverse本着splitand的精神split'：

inverse' :: (a -> b) -> (b -> a)
inverse' f (f x) = x

另一方面，这会导致以下错误：

Undefined data constructor `f'

我的问题：为什么 Curryf将潜在功能模式中的 in解释(f x)为数据构造函数，而++将（也是功能性）模式中的 in 解释(xs ++ ys)为函数名称？

换句话说，xsand ysinsplit' (xs ++ ys) = (xs,ys)似乎与 in 完全x类似inverse' f (f x) = x。

或者，如果与的类比split'不是很明显，请考虑prefix (xs ++ _) = xs等等orig (1 + x) = x，它们都可以编译和运行。

PS与原始帖子相比，我对名称和类型签名进行了一些调整，以使这个问题更容易理解。

4

2 回答 2

4

这种限制有语义上的原因（因此自动脱糖是不合理的）。从概念上讲，功能模式的语义是通过将功能模式评估（通过缩小）数据项并用这些数据项替换功能模式来定义的，以便它们充当标准模式。为了将此想法用作构造定义，需要在功能模式中使用的功能定义在比包含功能模式的功能“更低的级别”上。因此，必须存在所有功能的级别映射。这在有关功能模式的论文中进行了详细描述（但当前编译器未检查）。因此，函数模式中的函数变量是不允许的。

人们可能会考虑扩展它，但这超出了当前功能模式的基础。

于 2015-11-05T12:54:30.113 回答
3

简而言之，函数模式的语法f x 要求函数f是在 范围内可访问的已定义函数inverse'，这就是为什么xs ++ ys有效，而在哪里f x无效。

这是由功能模式的实现所激发的。它们被转换为对=:<=执行一种“惰性”统一的原始运算符的调用（惰性是因为它可能将自由变量绑定到表达式而不是值），其中模式中出现的变量作为新的逻辑变量引入。因此，函数

f (id x) = x

变成

f y | id x =:<= y = x  where x free

如果函数模式中的函数现在是一个变量，那么就必须猜测任意函数，这在 Curry 中是不支持的。

您现在可能会遇到它f不是真正的自由变量，因为它是由 的第一个参数确定的inverse'，这确实是正确的。的定义inverse'也使用了非线性模式的语法（因为f出现了两次），它的翻译用新鲜的变量替换了循环变量，然后通过严格统一来统一以前的循环变量。例如，

pair (x, x) = success

等价于定义

pair' (x, y) | x =:= y = success

这样你的例子就会变成

inverse' f y | f =:= g & g x =:<= y = x where g, x free

请注意，这需要严格统一功能，目前 KiCS2 不支持。但是，此定义适用于 PAKCS。

然而，如果我们进一步简化这个定义，我们得到

inverse' f y | f x =:<= y = x where x free

这个定义最终在 PAKCS 和 KiCS2 中都可以正常工作。

请注意，=:<=一般不建议显式使用原始运算符，因为它可能将逻辑变量绑定到表达式而不是值，因此违反了逻辑变量的语义（包含某种类型的所有值，但不包含表达式）。功能模式的翻译确保了这种违规行为不会被观察到，但如果=:<=直接使用它可能会出现这种情况。

最后，还有一个FunctionInversion用于 PAKCS 和 KiCS2 的库，它提供了invf1用于invf5反转具有不同数量的函数的函数。

于 2015-11-05T08:27:14.970 回答