许多函数可以简化为无参数形式，但是否所有函数都可以这样做呢？
例如，我不知道如何对以下函数进行简化：
apply2 f x = f x x
3个回答
11
逻辑组合子（即S，K，I组合子）本质上是函数的无点形式，而λ演算等价于组合逻辑，因此我认为这表明答案是肯定的。
如果我没有理解错误，您的apply2函数的组合子是：
((S((S(KS))K))(K((S((SK)K))((SK)K))))
这个函数也被称为“云雀”，来自于雷蒙德·斯穆利安的组合鸟页面。
(编辑注：) 原来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)
- ErikR
22
4虽然数据略微超出λ演算的范畴，但与此相差并不是很大：有各种将数据编码为函数的方法，可以模拟求和、乘积和递归类型。 - Daniel Wagner
1@DanielWagner 显然，但是元组的编码是内置的，除了通过给定的语法之外不可用。因此，如果这个答案说“...建议对于柯里化函数是肯定的”或者类似范围的限制，我会很乐意撤回我的批评。 - AndrewC
1我认为任何原始数据构造器的任何原始选择器都应被允许用于指向无点表达式。我们承认
(+) 和 (:) 以及 fst，为什么不是 snd3(_,x,_) = x？或者像 tupsel_I_N(x_1, x_2, ..., x_i, ..., x_n) = x_i 这样呢？ - Will Ness1这就是为什么我限定了我的答案，因为我不确定我是否正确解释了lambda表达式。 - ErikR
显示剩余17条评论
11
S-K基础
正如已经提到的那样，通过一组适当的固定组合子，任何λ演算都可以被转换为只使用这些组合子和函数应用的形式 - 没有λ抽象（因此没有变量）。最著名的组合子集是S和K。详见组合逻辑/S-K基础的完备性以获取该过程的描述。这些组合子的定义如下：
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))))
因此，我们可以将任何λ项转换为二叉树，除了它的形状外不包含其他信息（所有叶子节点都包含U，节点表示函数应用）。
更高效的基础 S、K、I、B、C
然而，如果我们想要更高效并获得一个大小合理的转换，使用I并引入另外两个冗余组合子是有帮助的，它们被称为B和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，<*>和<$>是来自Applicative函子类型类的函数，我们在此针对读取器单子(->) r进行特化。
因此，在您的情况下，我们可以编写：
apply2 = (<*>) `flip` id
为什么要使用Reader Monad？
在消除抽象过程中，我们尝试将形如λx->M :: r->a（其中r是x的类型，a是M的类型）的术语转换为不包含x的形式。我们通过递归处理M来实现这一点，随后将M的每个类型为b（可能包含x）的子术语转换为类型为r->b（不包含x）的函数，并将这些子术语组合在一起。这正是Reader Monad的设计目的：将类型为r -> something的函数组合在一起。
更多细节请参见The Monad Reader，Issue 17：The Reader Monad and Abstraction Elimination。
数据结构怎么办？
对于构造数据结构，我们只需使用它们的构造函数，这里没有问题。
对于拆解它们，我们需要一些方法来摆脱模式匹配。这是编译函数式程序时编译器必须执行的操作。这个过程在Functional Programming Languages实现第5章中有所描述：有效编译模式匹配。思路是对于每种数据类型，我们都有一个case函数来描述如何拆解（折叠）该数据类型。例如，对于列表来说是foldr，对于Either来说是either，假设对于4元组它将是
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数据结构，其中介绍了如何直接将数据结构编码为函数，如果我们启用更高级别类型。
结论
是的，我们可以构建一个固定的组合器集合，然后将任何使用这些组合器和函数应用的函数转换为无点（point-free）样式。
- Petr
5
在我看来，这里唯一真正的问题是数据解构器是否被视为“函数”集合的一部分，即数据解构器是否是问题所要求的“任何函数”的有效选择？答案很快就能得出。 - John L
@JohnL 顺便说一下，
fst = uncurry const 和 snd = uncurry (const id)。但是对于 fst3 和 fstN 没有这样的东西 - 因为*没有 uncurry3 或 uncurryN*。但是为什么不呢？（我仍然认为，引入语言的原始*类型意味着提供从中选择的原始*手段。否则它是无用的。）我喜欢这个答案！ :) - Will Ness@WillNess那样做的原因在于
uncurry本身使用fst和snd，两者都是点求值（至少在ghc中）。问题在于，data引入了一种新类型和一种新的提取数据的基本方法，但该数据提取机制并不是上述所描述的case函数。因此，我们必须以点求值形式自己编写case函数。我想你可以说我在技术上有异议，然而，由于Haskell目前要求我们手动以点求值形式构建“固定的组合器集合”，我们无法将每个函数写成点无关的形式。 - John L@JohnL 这只是巧合而已。它本来也可以定义成另一种方式。此外，你为我证明了一点 - 显然
fst 和 snd 是有点的，但在点无风格的重写中仍然被广泛使用！当然，如果我们将基础限制在“真正的”Haskell中预先构建的内容上，你绝对是正确的；我已经在这个页面的其他地方同意了这一点（我在那个论点中使用了你的 data 示例）。 :) 我认为这只是惯例 - 或个人选择的问题。对我来说，选择另外一种方式（例如在这个答案中）也是完全有道理的。 - Will Ness5
有很多看起来可能不是点无样式，但实际上可以用点无样式表达的函数，但要得到一个不是这样的函数，您可以快速定义一个适用于极大元组的函数，其中没有标准函数。
我认为这种类型的东西不太可能以点无样式表达，不是因为复杂性，而是因为这么大的元组函数很少：
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
在reader monad ((->) b)中，join的作用是:
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)
我们期望的许多功能都有无参函数版本，但是有些无参函数表达式非常混乱。 有时候 显式比简洁更好。
- AndrewC
17
1这并没有解决楼主的根本问题，即任何函数都可以被简化为没有参数形式吗？你只是驳斥了楼主认为不可能的例子。 - NominSim
1也许有人可以在您的示例中尝试在GOA中运行:pl？没有（明显的）无点表示法的困难示例不是证明！ - Andy Hayden
我想你误解了我的观点。我的证明将包括展示在所有基类中都没有使用14元组作为参数的函数。我已经通过hoogle检查过了。你不能使用更小的元组来构建一个14元组，因为它不是一个列表。 - AndrewC
@JohnL非常正确，我同意你的观点，但就问题而言，我认为可以说f(x,y) = x+2可以用点无关风格表示为(+2).fst。我的回答并不是说没有本质上的点无关函数，而是有些函数无法用点无关风格来表示。 - AndrewC
@WillNess 目标柱移动警报！如果我们可以额外定义任何我们喜欢的琐碎选择器和组合器，那么问题就变得非常非常琐碎。问题中给出的示例就是这样一个琐碎的参数转换函数。如果每当有不方便的地方时都可以定义一个非点自由辅助函数来解决问题，那么问题就没有意义了。这就是为什么我在之前的评论中只提到了基础部分。 - AndrewC
显示剩余12条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
:pl \f x -> f x x（pl代表“point-less”，这是一个对point-free不太尊重的术语）。 - n. m.apply2жҳҜжүҖи°“зҡ„WcombinatorпјҢеҚі_W = join -- _W f x = f x x = CSI = SS(KI) = SS(SK)гҖӮCжҳҜflipпјӣIжҳҜidпјӣSжҳҜ(<*>)пјҢKжҳҜconstгҖӮжқҘзңӢзңӢеҗ§гҖӮ - Will NessControl.Applicative> (<*> id) (,) 4==>(4,4)。 - Will Ness[dup] dip i或dup dig2 i，具体取决于参数的顺序。在任何情况下，dup会复制该值，而i则将该函数应用于它。 - Jon Purdy