Haskell中用于高阶函数的Lambda表达式

Question

在this book之后，Haskell中的所有内容都是λ-演算：f(x)=x+1之类的函数可以在Haskell中写为f = \x -> x+1，在λ表达式中写为λx.x+1。

• λ表达式对于像map::(a -> b) -> [a] -> [b]的高阶函数是什么？还是函数λ的($) :: (a -> b) -> a -> b表达式？
• 功能列表（即f::[a->b]）如何？具体的例子可以是h = map (\f x -> f x 5) [(-),(+)]。然后λ表示法类似于h = map (λfx.f(x(5)) [(λab.a-b),(λab.a+b)]吗？

我只是熟悉alpha转换，beta减少之类的过程，但是如果您以λ的形式细分功能列表，将不胜感激，并且无需简化。

谢谢。

Answer 1

首先，

Haskell中的一切都是λ微积分

这不是真的。 Haskell有很多东西无法代表未类型化的λ微积分。也许他们的意思是说它可能被[[compiled到λ微积分，但是这很明显，用“任何图灵完备的语言……”贾达·贾达都是。]

[像map :: (a -> b) -> [a] -> [b]等高阶函数的λ表达式是什么

这里有两个不相关的问题。对于直接的λ转换，“高阶函数”部分完全没有问题，并且正如评论所言]

($) = \f -> \x -> f x -- λf.λx.fx

或替代地
($) = \f x -> f x
($) = \f -> f  -- by η-reduction

（（在Haskell中，我们将其简称为($) = id）。
[另一件事是，map是在代数数据类型上定义的递归函数，将其转换为无类型的λ微积分将使我们与Haskell距离很远。将其转换为包含模式匹配（case）和let绑定的λ味道更具指导性，这实际上是GHC在编译程序时所做的工作。提出来很容易

map = \f l -> case l of
               [] -> []
               (x:xs) -> f x : map f xs

...或避免重复使用顶级绑定
map = \f -> let go l = case l of
                        [] -> []
                        (x:xs) -> f x : go xs
            in go

我们无法像这样摆脱let，因为λ演算不直接支持递归。但是递归
can
也可以用一个定点组合器来表示；与未类型化的λ微积分不同，我们不能自己定义Y组合器，但可以仅假设fix :: (a -> a) -> a作为基元。事实证明，这几乎完成了与递归let绑定完全相同的工作，然后立即对其求值：

fix :: (a -> a) -> a