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

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 组合器来解决这个问题。η-reduction 是一个很好的尝试，但正如您所知道的，当变量被使用两次时，您不能 η-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

在 Haskell 中，S = (<*>)andK = 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

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

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

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

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