I struggle to understand how type declarations work... Like these ones for example:

t :: (a -> b) -> (b -> c) -> a -> c

s :: (a -> b -> c) -> (a -> b) -> a -> c

I know from just trying different things that the correct functions would look like this:

t :: (a -> b) -> (b -> c) -> a -> c 
t f g x = g (f x)

s :: (a -> b -> c) -> (a -> b) -> a -> c 
s f g x = f x (g x)

But how does this work? Why are the brackets at the end? Why is it not

t f g x = (f x) g

or

s f g x = (f x) g x 

Im so lost

CodePudding user response：

For the first example:

t :: (a -> b) -> (b -> c) -> a -> c

In a type declaration, the type1 -> type2 pattern indicates a function from type1 to type2. In type declarations, the -> operator is right-associative, so this is parsed as:

t :: (a -> b) -> ((b -> c) -> (a -> c))

This kind of construction is called "currying": providing the first argument (type a -> b) yields a function which accepts the second argument (type b -> c) which yields a function which accepts the third argument (type a).

The function declaration syntax is set up to do this automatically. The first two arguments are functions and the third is just a, so start with names that reflect that: f :: a -> b and g :: b -> c are functions, while x :: a is a fully generic type which could be anything.

t f g x = ...

Note that function application in Haskell is just concatenation: to apply function f to value x, just use f x. This syntax is left-associative, so t f g x is parsed as (((t f) g) x) to match the currying construction described above.

Anyway, given these types, you don't have much choice in how to put them together:

• the only thing you know about the type a is that it's the type of x, and the argument type of f, so the only thing you can do with them is to apply the function to the value: f x.

• the only thing you know about the type b is that it's the result type of f and the argument type of g, so the only thing you can do is apply g (f x).

• the only thing you know about the type c is that it's the result type of g and of the overall function t, so the only thing t can return is g (f x).

The reason you can't do (f x) g is that the types don't match:

f :: a -> b
x :: a
(f x) :: b

g :: b -> c

So, you can apply g :: b -> c to (f x) :: b to get a result of type c. But not the other way around, because b might not even be a function type.