Haskell Higher order function Type

Question

I am studying haskell now. But I am struggling with 'Type'.

For example, type of f function is

f g (x,y)= g x y

(a -> b -> c) -> (a, b) -> c

type of the following Haskell function h

h f g x y = f (g x y) x

(a -> b -> c) -> (b -> d -> a) -> b -> d -> c

How can I understand how to guess type of function?

Why do you call it "guessing"? There's no guesswork involved. — Robin Zigmond
– Robin Zigmond, Commented Nov 1, 2019 at 18:16
But to be more constructive: have you attempted to figure out for yourself what the types must be? (Start with the first one, as its easier, although exactly the same reasoning applies for both.) How much can you say in words about the type of the first argument g for example? — Robin Zigmond
– Robin Zigmond, Commented Nov 1, 2019 at 18:19
The type signatures are perfectly clear. f :: (a -> b -> c) which means the first parameter of f is of type a yields the return value of g has to be of type a. The second parameter of f which is x, is of type b which yields the first parameter of g which is also x to become of type b which yields g to take a type signature like (b -> d -> a) whereas the type parameter d is assigned for the y parameter of the function h. So the type of h function turns out to be (a -> b -> c) -> (b -> d -> a) -> b -> d -> c — Redu
– Redu, Commented Nov 1, 2019 at 18:32

K. A. Buhr · Accepted Answer · 2019-11-01 19:39:53Z

4

I'll walk you through the first one: hopefully this gives you enough of an idea that you can figure out the second one by yourself.

So the function definition is:

f g (x,y)= g x y

f is the function we're interested in, and we can see from the above - just from the left hand side in fact - that it takes 2 arguments: g and the tuple (x,y). So let's use some type variables:

we'll use a for the type of g
b for the type of x
c for the type of y
and d for the type that f outputs when given the two arguments.

This gives us

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

and further that is all the information that we can get from the left of the =. We can learn more by looking at the right hand side - the g x y which must be of type d.

Well the expression g x y itself tells us that g is a function which can take 2 arguments. And further we have already assigned types to those arguments - and to its return value (since this is the same value that f g (x,y) outputs, which we already said has type d).

Writing it all out, we find that the type of g is simply b -> c -> d. Substituting that in the type of f which we wrote down above, we get:

f :: (b -> c -> d) -> (b, c) -> d

If we cared, we could rename the type variables now so that this matches the signature you were given - but hopefully you can see that they're the same without having to do that.

As I said, although slightly more involved, the second exercise can be solved using exactly the same logic.

edited Nov 1, 2019 at 19:39

K. A. Buhr

52.7k3 gold badges56 silver badges82 bronze badges

answered Nov 1, 2019 at 19:32

Robin Zigmond

18.3k2 gold badges25 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

dasogom Over a year ago

Thank I figure it out second one with the same logic!

Collectives™ on Stack Overflow

Haskell Higher order function Type

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related