时间戳

首页 > 解决方案 > Haskell 中高阶函数的 Lambda 表达式

haskell - Haskell 中高阶函数的 Lambda 表达式

问题描述

在这本书之后，Haskell 中的一切都是-λ演算：函数 likef(x)=x+1可以在 Haskell 中写为f = \x -> x+1和 ，λ表达式为λx.x+1。

我只熟悉 alpha 转换、beta 减少等过程，但如果您按 λ术语分解函数列表，那将不胜感激，无需简化。

谢谢。

标签： haskellfunctional-programminghigher-order-functionslambda-calculus

解决方案

首先，

Haskell 中的一切都是 λ-演算

这并不正确。Haskell 有许多与无类型 λ 演算中的东西不对应的特性。也许他们的意思是它可以编译为 λ-演算，但这很明显，“任何图灵完备的语言......” jadda jadda。

什么是高阶函数的 λ 表达式，例如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（很容易想出

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这种情况，因为 λ 演算不直接支持递归。但是递归也可以用定点组合器来表示；与无类型 λ 演算不同，我们不能自己定义 Y 组合子，但我们可以假设fix :: (a -> a) -> a为原语。结果证明它完成了与递归 let-binding 几乎完全相同的工作，然后立即对其进行评估：

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

为了为此构建一个 λ 风格的语法，

map = λ f .fix(λ g .λ l .{ l ? []⟼[]; ( x : s )⟼<i>fx: gs })

推荐阅读