高阶函数和括号

Question

根据https://wiki.haskell.org/Compose处的compose类型，可以写成
compose :: [a -> a] -> (a -> a) 或 compose :: [a -> a] -> a -> a

我认为这两种类型是不同的：前者接受一个函数列表和 returns 一个函数，后者接受一个函数列表和一个参数，最后 returns 一个值。

也就是说，当一个函数（高阶函数）将另一个函数作为参数或returns一个函数作为结果时，不应省略参数（结果）周围的括号，例如，如果filter :: (a -> Bool) -> [a] -> [a]去掉括号，它的意思会改变。

我是对还是错？

Answer 1

这两个是一样的：

compose1 :: [a -> a] -> (a -> a)
compose1 [] = \x -> x
compose1 [f] = \x -> f x
compose1 (f1:f2:fs) = compose1 ((f2 . f1):fs)

compose2 :: [a -> a] -> a -> a
compose2 [] x = x
compose2 [f] x = f x
compose2 (f1:f2:fs) x = compose2 ((f2 . f1):fs) x

请注意这些定义实际上是相同的，只是 lambda 从 = 的一侧移到了另一侧。事实上，您始终可以进行以下转换：

f x y z = <expr x y z>
f x y = \z -> <expr x y z>
f x = \y -> \z -> <expr x y z> = \y z -> <expr x y z>
f = \x -> \y -> \z -> <expr x y z> = \x y z -> <expr x y z>

这实际上是编译器对所有函数所做的。如果您使用 -ddump-simpl 进行编译，您将看到转储的核心代码，其中所有函数都是根据 lambda 表达式定义的。这是因为Haskell使用了

的规律

f x = <expr>

相当于

f = \x -> <expr>

lambda 语法可以被认为是比使用显式参数定义函数更基本的语法。

Namely, when a function(higher-order function) takes another function as an argument or returns a function as a result, the parentheses around the argument(the result) shouldn't be omitted, e.g., if filter :: (a -> Bool) -> [a] -> [a] removes the parentheses, its meaning will change.

您认为不能从 filter 的类型签名中删除括号是正确的，这是因为函数应用程序仅是右结合的。这意味着以下签名是等效的：

f :: a -> b -> c -> d -> e
f :: a -> (b -> (c -> (d -> e)))

这就是靠右关联的意思，在添加嵌套括号时从右到左。然而，f的签名不等同于

-- Not equivalent!
f :: (((a -> b) -> c) -> d) -> e

只是因为 -> 不是完全结合运算符。例如，+ 你有

x + (y + z) = (x + y) + z

但是->你有

x -> (y -> z) /= (x -> y) -> z

这类似于 : 运算符，例如

1:2:3:4:[] == 1:(2:(3:(4:[])))
           /= (((1:2):3):4):[]

最后一个表达式不会进行类型检查，因为 1:2 类型错误，2 不是列表！

Answer 2

箭头是右结合的，所以[a -> a] -> a -> a和[a -> a] -> (a -> a)是等价的。

如果删除 filter 类型签名中的括号，您将得到：

a -> Bool -> [a] -> [a]
a -> Bool -> ([a] -> [a])
a -> (Bool -> ([a] -> [a]))

... 这与 正确的 类型签名不同。

高阶函数和括号

Higher-order function and parentheses

haskell