许多函数可以简化为无参数形式,但是否所有函数都可以这样做呢?
例如,我不知道如何对以下函数进行简化:
apply2 f x = f x x
许多函数可以简化为无参数形式,但是否所有函数都可以这样做呢?
例如,我不知道如何对以下函数进行简化:
apply2 f x = f x x
逻辑组合子(即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)
(+)
和 (:)
以及 fst
,为什么不是 snd3(_,x,_) = x
?或者像 tupsel_I_N(x_1, x_2, ..., x_i, ..., x_n) = x_i
这样呢? - Will Ness正如已经提到的那样,通过一组适当的固定组合子,任何λ演算都可以被转换为只使用这些组合子和函数应用的形式 - 没有λ抽象(因此没有变量)。最著名的组合子集是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
,节点表示函数应用)。
然而,如果我们想要更高效并获得一个大小合理的转换,使用I
并引入另外两个冗余组合子是有帮助的,它们被称为B
和C
:
C f x y = f y x
B f g x = f (g x)
在这里,C
将f
的参数顺序颠倒,B
是函数组合。
这种加法显著减少了输出的长度。
实际上,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
在消除抽象过程中,我们尝试将形如λ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)样式。
fst = uncurry const
和 snd = uncurry (const id)
。但是对于 fst3
和 fstN
没有这样的东西 - 因为*没有 uncurry3
或 uncurryN
*。但是为什么不呢?(我仍然认为,引入语言的原始*类型意味着提供从中选择的原始*手段。否则它是无用的。)我喜欢这个答案! :) - Will Nessuncurry
本身使用fst
和snd
,两者都是点求值(至少在ghc中)。问题在于,data
引入了一种新类型和一种新的提取数据的基本方法,但该数据提取机制并不是上述所描述的case函数。因此,我们必须以点求值形式自己编写case函数。我想你可以说我在技术上有异议,然而,由于Haskell目前要求我们手动以点求值形式构建“固定的组合器集合”,我们无法将每个函数写成点无关的形式。 - John Lfst
和 snd
是有点的,但在点无风格的重写中仍然被广泛使用!当然,如果我们将基础限制在“真正的”Haskell中预先构建的内容上,你绝对是正确的;我已经在这个页面的其他地方同意了这一点(我在那个论点中使用了你的 data
示例)。 :) 我认为这只是惯例 - 或个人选择的问题。对我来说,选择另外一种方式(例如在这个答案中)也是完全有道理的。 - Will Ness有很多看起来可能不是点无样式,但实际上可以用点无样式表达的函数,但要得到一个不是这样的函数,您可以快速定义一个适用于极大元组的函数,其中没有标准函数。
我认为这种类型的东西不太可能以点无样式表达,不是因为复杂性,而是因为这么大的元组函数很少:
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)
我们期望的许多功能都有无参函数版本,但是有些无参函数表达式非常混乱。 有时候 显式比简洁更好。
:pl \f x -> f x x
(pl代表“point-less”,这是一个对point-free不太尊重的术语)。 - n. m.apply2
жҳҜжүҖи°“зҡ„W
combinatorпјҢеҚі_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