我们可以在 Haskell 中始终使用 <$> 来定义“point free”函数吗？

Question

<$>我一直在学习 Haskell 中的and运算符有多么强大<*>，以及如何在通常需要的地方定义一些没有参数的函数。我按照以下步骤更改我的doThing函数并逐渐删除它的三个参数：

1) doThing x y z = (x + y) * z
2) doThing x y = ((x + y) *)
3) doThing x = (*) <$> (x +)
4) doThing = ((*) <$>) <$> (+)

所有这些函数都采用三个数字x、y、 、z和 计算(x + y) * z。我知道这在实际意义上既不漂亮，也不是一个好的编程实践，但我仍然想知道是否有可能任何具有 N 个变量的数学表达式都可以被描述为一个函数，而无需显式命名这 N 个变量。我尝试过更复杂的表达方式，但没有取得多大成功；即使是上面的第四步对我来说也很难理解。

Answer 1

是的，这总是可能的。这是一种特别简单的算法：

[[\x -> x]] ~> id
[[\x -> e]] ~> const e -- when x does not appear in e
[[\x -> e1 e2]] ~> [[\x -> e1]] <*> [[\x -> e2]]

例如，以下是z从表达式中删除的方式。

   \x y -> [[\z -> (x + y) * z]]
~> \x y -> [[\z -> (*) (x + y)]] <*> [[\z -> z]]
~> \x y -> const ((*) (x + y))   <*> id

然后我们可以再次进行，这次消除y.

   \x ->  [[\y -> const ((*) (x + y)) <*> id]]
~> \x ->  [[\y -> (<*>) (const ((*) (x + y)))]]                                                            <*> [[\y -> id]]
~> \x -> ([[\y -> (<*>)]] <*>  [[\y -> const ((*) (x + y))]]                                             ) <*> const id
~> \x -> (const (<*>)     <*> ([[\y -> const]] <*> [[\y -> (*) (x + y)]]                                )) <*> const id
~> \x -> (const (<*>)     <*> (const const     <*> ([[\y -> (*)]] <*> [[\y -> x + y]]                  ))) <*> const id
~> \x -> (const (<*>)     <*> (const const     <*> (const (*)     <*> ([[\y -> (+) x]] <*> [[\y -> y]])))) <*> const id
~> \x -> (const (<*>)     <*> (const const     <*> (const (*)     <*> (const ((+) x)   <*> id         )))) <*> const id

我们可以再去消除x，但这已经够乱的了。关键是这一切都可以纯粹机械地完成，不需要进行点自由翻译的人（或机器）的洞察力。

为了好玩，如果您遵循此算法，这就是最终形式：

const (<*>) <*> (const ((<*>) (const (<*>))) <*> (const ((<*>) (const const)) <*> (const ((<*>) (const (*))) <*> (const (<*>) <*> (const const <*> (const (+) <*> id)) <*> const id)))) <*> const (const id)

很明显，该算法更注重简单性而不是结果的可读性！

生成该答案的代码的完整列表：

{-# LANGUAGE LambdaCase #-}

type Var = String
data Term
    = S | K | I
    | Variable Var
    | Lambda Var Term
    | App Term Term
    deriving (Eq, Ord, Read, Show)

free :: Var -> Term -> Bool
free v = \case
    Variable v' -> v == v'
    Lambda v' t -> v /= v' && free v t
    App t t' -> free v t || free v t'
    _ -> False

translate :: Term -> Term
translate = \case
    Lambda v t -> case t of
        _ | not (free v t) -> App K t
        Variable{} -> I
        App e1 e2 -> App (App S (translate (Lambda v e1))) (translate (Lambda v e2))
        Lambda{} -> translate (Lambda v (translate t))
        _ -> error "The impossible happened: variable is not free, but term is not a variable, app, or lambda"
    App t t' -> App (translate t) (translate t')
    t -> t

doThing :: Term
doThing = Lambda "x" . Lambda "y" . Lambda "z" $
    App
        (App
            (Variable "(*)") 
            (App
                (App (Variable "(+)") (Variable "x"))
                (Variable "y")
            )
        )
        (Variable "z")

pp :: Term -> String
pp = \case
    S -> "(<*>)"
    K -> "const"
    I -> "id"
    Variable v -> v
    Lambda v t -> "\\" ++ v ++ " -> " ++ pp t
    App (App S t) t' -> ""
        ++ case t of
            Lambda{} -> "(" ++ pp t ++ ")"
            _ -> pp t
        ++ " <*> "
        ++ case t' of
            App (App S _) _ -> "(" ++ pp t' ++ ")"
            _ -> pp t'
    App t t' -> ""
        ++ case t of
            Lambda{} -> "(" ++ pp t ++ ")"
            _ -> pp t
        ++ " "
        ++ case t' of
            App{} -> "(" ++ pp t' ++ ")"
            _ -> pp t'