高阶函数和括号

Question

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

我认为这两种类型是不同的:前者采用函数列表并返回函数,后者采用函数列表和参数,然后最终返回一个值.

也就是说,当函数(高阶函数)将另一个函数作为参数或作为结果返回函数时,不应省略参数(结果)周围的括号,例如,如果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你会看到转储的核心代码,其中所有函数都是用lambdas定义的.这是因为Haskell使用的是法律

f x = <expr>

相当于

f = \x -> <expr>

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

也就是说,当函数(高阶函数)将另一个函数作为参数或作为结果返回函数时,不应省略参数(结果)周围的括号,例如,如果filter :: (a -> Bool) -> [a] -> [a]删除括号,其含义将是更改.

你认为你不能从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]))

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