Higher-order function and parentheses

Question

According to compose's type at https://wiki.haskell.org/Compose, it can be written as
compose :: [a -> a] -> (a -> a) or compose :: [a -> a] -> a -> a

I think these two types is different: the former takes a list of functions and returns a function,the latter takes a list of functions and an argument,then finally returns a value.

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.

Am I right or wrong?

Not an expert, but I think both cases are the same. The reason for this is currying (wiki.haskell.org/Currying) — Max
What will the resulting type be in each case if you curry compose by only giving it the first argument, e.g. the list of functions? Does that help explain what is going on? In both cases after currying, if you supply just one more argument (type a) what will happen? — ely
I encourage you to think about what observations you would expect to be able to make to differentiate these two types, and try making those observations in ghci. Were they different? (I encourage you in this way because the moment I understood what was happening in this space, my mind exploded, and I have not been able to leave Haskell since.) — Daniel Wagner
You're wrong - -> is right-assocative, so a -> foodiebar automatically becomes (->) (a) (foodiebar). This is the same for functions: a -> b -> c is a -> (b -> c). — AJF

bheklilr bheklilr · Accepted Answer · 2015-01-29T17:02:09

These are both the same:

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

Notice how these definitions are virtually identical, except the lambda gets moved from one side of the = to the other. In fact, you can always do the following transformations:

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>

This is actually what the compiler does to all your functions. If you compile with -ddump-simpl you will see the Core code dumped where all functions are defined in terms of lambdas. This is because Haskell uses the law that

f x = <expr>

Is equivalent to

f = \x -> <expr>

The lambda syntax could be considered a more basic syntax than defining a function using explicit arguments.

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.

You are correct in thinking that you can't remove the parentheses from filter's type signature, and this is because function application is right associative only. This means that the following signatures are equivalent:

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

This is what is meant by associating to the right, you go from right to left when adding nested parentheses. However, f's signature is not equivalent to

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

Simply because -> is not a fully associative operator. For example, with + you have

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

But with -> you have

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

This is similar to the : operator, e.g.

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

The last expression would not type check since 1:2 is ill typed, 2 is not a list!

Higher-order function and parentheses

2 Answers