如何使用重复变量以无点样式重写

Question

如何以无点样式重写以下表达式？

p x y = x*x + y

使用lambda演算，我做了以下事情：

p = x -> y -> (+) ((*) x x) y
  = x -> (+) ((*) x x) -- here start my problem
  = x -> ((+) . ((*) x )) x
  ... ?

Answer 1

我问lambdabot

<Iceland_jack> @pl p x y = x*x + y
<lambdabot> p = (+) . join (*)

join来自Control.Monad，通常具有此类型

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

但是使用 instance Monad ((->) x)(如果我们可以留下部分类型，这可以写(x ->) (，我们得到以下类型/定义

join :: (x -> x -> a) -> (x -> a)
join f x = f x x

让我们让GHCi确认类型：

>> import Control.Monad
>> :set -XTypeApplications 
>> :t join @((->) _)
join @((->) _) :: (x -> x -> a) -> x -> a

Answer 2

既然你提到了Lambda演算，我将建议如何使用SK组合器解决这个问题。 η-reduce是一个很好的尝试，但正如您可以告诉的那样，当变量使用两次时，您无法η-reduce。

S = λfgx.fx(gx)
K = λxy.x

重复的特征由S编码。您将问题简化为：

λx.(+)((*)xx)

因此，让我们从那里开始。任何 lambda 项都可以通过算法转换为 SK 项。

T[λx.(+)((*)xx)]
= S(T[λx.(+)])(T[λx.(*)xx])        -- rule 6
= S(K(T[(+)]))(T[λx.(*)xx])        -- rule 3
= S(K(+))(T[λx.(*)xx])             -- rule 1
= S(K(+))(S(T[λx.(*)x])(T[λx.x]))  -- rule 6
= S(K(+))(S(*)(T[λx.x]))           -- η-reduce
= S(K(+))(S(*)I)                   -- rule 4

在哈斯克尔，S = (<*>)和K = pure和I = id.因此：

= (<*>)(pure(+))((<*>)(*)id)

并重写：

= pure (+) <*> ((*) <*> id)

然后我们可以应用我们知道的其他定义：

= fmap (+) ((*) <*> id)     -- pure f <*> x = fmap f x
= fmap (+) (join (*))       -- (<*> id) = join for Monad ((->)a)
= (+) . join (*)            -- fmap = (.) for Functor ((->)a)

Answer 3

如果你去 http://pointfree.io/

为

p x y = x*x + y

它给你

p = (+) . join (*)

Answer 4

只是为了好玩，你可以用State monad 来写

p = (+) . uncurry (*) . runState get

runState get只是从初始x生成一对(x, x); get将状态复制到结果中，runState返回状态和该结果。

uncurry (*)采用一对值而不是 2 个单独的值 ((uncurry (*)) (3, 3) == (*) 3 3 == 9 (。