10

许多函数可以简化为无点形式——但这对所有函数都适用吗？

例如，我看不出它是如何做到的：

apply2 f x = f x x
4

3 回答 3

11

逻辑组合器（即 S、K、I 组合器）本质上是无点形式的函数，而 lambda 演算相当于组合逻辑，所以我认为这表明答案是肯定的。

您的功能的组合器apply2是（如果我正确阅读内容）：

((S((S(KS))K))(K((S((SK)K))((SK)K))))

也被称为“云雀”，来自Raymond Smullyan 的 Combinatory Birds页面。

（编辑：）原来上面的1等价于\f x -> f (x x). 根据下面“@gereeter”的评论，它确实被称为“云雀”，而\f x -> f x x问题中要求的功能是上述书中的“莺”（又名“ W”组合器）W f x = S(S(K(S(KS)K))S)(KK)SI f x = S(S(KB)S)(KK)SI f x = CSI f x = SfIx = f x x。

1这里：

((S((S(KS))K))(K((S((SK)K))((SK)K)))) f x =
  S( S(KS) K) (K( S( SK K) ( SK K)))  f x =   -- SKK    == I
  S (S(KS) K) (K( S  I       I    ))  f x =   -- S(KS)K == B
  S B         (K( S  I       I    ))  f x =
  Bf (K(SII)f) x = Bf (SII) x = f (SII x) = f (x x)
于 2012-11-01T20:04:14.063 回答
11

SK基础

如前所述，使用适当的固定组合子集，任何 lambda 项都可以转换为仅使用那些组合子和函数应用程序的形式 - 没有 lambda 抽象（因此没有变量）。最著名的组合子集是S和K。Se组合逻辑/SK 基础的完整性，用于描述程序。组合子定义为

K x y    = x
S x y z  = (x z) (y z)

有时包含身份组合I器，但它是多余的，因为I = S K K.

单个组合子基

有趣的是，即使使用单个组合器，您也可以做到这一点。Iota语言使用

U f = (f S) K

并且可以证明

I = (UU)
K = (U(U(UU)))
S = (U(U(U(UU))))

因此，我们可以将任何 lambda 项转换为除了形状之外没有其他信息的二叉树（所有叶子都包含U和，节点表示函数应用程序）。

更有效的基础 S、K、I、B、C

但是，如果我们想提高效率并获得合理大小的转换，则使用Iand 引入另外两个冗余组合子会很有帮助，它们称为Band C：

C f x y  = f y x
B f g x  = f (g x)

这里C颠倒了参数的顺序f并且B是函数组合。

这个添加显着减少了输出的长度。

Haskell 中的这些组合器

实际上，Haskell 已经以某种形式包含了所有这些标准组合子。尤其：

I = id
K = const
  = pure :: a -> (r -> a)
S = (<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
B = (.)
  = (<$>) :: (a -> b) -> (r -> a) -> (r -> b)
C = flip
  = \k x -> k <*> pure x

其中pure和是来自函子类型类的函数<*>，我们在这里专门为读者 monad 提供。<$>Applicative(->) r

所以在你的情况下，我们可以写

apply2 = (<*>) `flip` id

为什么是读者单子？

在抽象消除的过程中，我们尝试将形式的项λx -> M :: r -> a（其中r是 的类型x和a的类型M）转换为没有 的形式x。我们通过递归处理来做到这一点，M然后我们将其每个类型的子项b（可能包含x）转换为类型的函数r -> b（不包含x），然后将这些子项组合在一起。这正是 reader monad 的设计目的：将类型的函数组合r -> something在一起。

有关更多详细信息，请参阅Monad Reader，第 17 期：Reader Monad 和抽象消除。

数据结构呢？

对于构造数据结构，我们只需使用它们的构造函数，这里没有问题。

为了解构它们，我们需要一些方法来摆脱模式匹配。这是编译器在编译函数式程序时必须做的事情。函数式编程语言的实现第 5 章：模式匹配的高效编译中描述了这样的过程。这个想法是，对于每种数据类型，我们都有一个案例函数来描述如何解构（折叠）数据类型。例如，对于列表 it foldr，对于Eitherits either，假设对于 4-tuples 它是

caseTuple4 :: (a -> b -> c -> d -> r) -> (a,b,c,d) -> r
caseTuple4 f (a,b,c,d) = f a b c d

等等。因此，对于每种数据类型，我们添加它的构造函数、解构case函数，并将模式编译到这个函数中。

举个例子，让我们表达

map :: (a -> b) -> [a] -> [b]
map f []        = []   
map f (x : xs)  = f x : map f xs

这可以表示为foldr：

map f = foldr (\x xs -> f x : xs) []

然后使用我们之前讨论过的组合器进行转换：

map = (foldr . ((.) (:))) `flip` []

你可以验证它确实做了我们想要的。

另请参阅System F 数据结构，它描述了如果我们启用更高级别的类型，数据结构如何直接编码为函数。

结论

是的，我们可以构造一组固定的组合器，然后将任何函数转换为仅使用这些组合器和函数应用程序的无点样式。

于 2012-11-02T17:08:40.300 回答
5

有很多函数看起来可能不是，但可以以无点风格表达，但要获得一个不是的，您可以快速定义一个适用于没有任何标准的非常大的元组的函数职能。

我认为这种事情不太可能是无点表达的，不是因为复杂，而是因为这种大小的元组的函数并不多：

weird (a,b,c,d,e,f,g,h,i,j) = (a<*>b,c++d,e^f+a,g ()-h 4+e,j <*> take f i)

你的例子：

apply2 :: (b -> b -> a) -> (b -> a)
apply2 = join

它join在读者单子中((->) b)

join :: Monad m => m (m a) -> m a

所以在这种情况下

join :: ((->) b) ((->) b a) -> ((->) b) a
join :: ((->) b) (b -> a) -> (b -> a)
join :: (b -> (b -> a)) -> (b -> a)
join :: (b -> b -> a) -> (b -> a)

无点版本的功能比我们预期的要多得多，但一些无点表达式完全是一团糟。有时，明确比简洁​​更好。

于 2012-11-01T19:45:20.980 回答