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

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

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

为了

p x y = x*x + y

它给你

p = (+) . join (*)

Answer 2

我问了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)（如果我们可以left section types这可以写成(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 3

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

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

runState get 简单地从初始 x 生成一对 (x, x)； get 将状态复制到结果，runState returns 状态和结果。

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

Answer 4

既然你提到了 Lambda 微积分，我将建议如何使用 SK 组合器解决这个问题。 η-reduce 是一个很好的尝试，但正如你所知，当变量被使用两次时你不能 η-reduce。

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

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

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

让我们从这里开始。 Any lambda term can be algorithmically transformed to a SK term.

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

在Haskell、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)

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

How to rewrite in point-free style with a repeating variable?

haskell

pointfree

tacit-programming