I'm currently doing a course in Haskell, and I have a lot of difficulty understanding the types of functions, particularly when there's function application or lambda expressions. Say for instance the following:

f = (\x -> \y -> \z -> [x (y z), y z])

or

g = \x -> \y -> \z -> x.y.z

I can sort of make some assumptions about the fact that x and y are functions, but I don't have a concrete method for figuring out the types of these functions.

Similarly for the following:

h = foldr (&&)

I try to guess and then check via :t in the interpreter, but I'm usually off by quite a bit. Is there any particular method I can use to find the types of such functions?

CodePudding user response：

You start by assigning type variables to the inputs and the result

f = (\x -> \y -> \z -> [x (y z), y z])

and conclude

f :: a -> b -> c -> d   --  (A0)
-- or even (f is not needed)
\x -> \y -> \z -> [x (y z), y z] :: a -> b -> c -> d

that is

x :: a                -- (1)
y :: b                -- (2)
z :: c                -- (3)
[x (y z), y z] :: d   -- (4)

You can continue with (4) and conclude

• that the type d is a list of d1s, i.e. d ~ [d1] (5)

  f :: a -> b -> c -> [d1] -- (A1)
  

• and that the values of the list are of type d1, i.e.

  x (y z) :: d1  -- (6)
  y z :: d1      -- (7)
  

From (6) you learn that

x :: e -> d1   -- (8)
y z :: e       -- (9)

(1) and (8) unify, i.e. a ~ (e -> d1) and

f :: (e -> d1) -> b -> c -> [d1] -- (A2)

You play this game until you get bored and use GHCi to arrive at

f :: (d1 -> d1) -> (f -> d1) -> f -> [d1] -- (A3)
-- and renaming
f :: (a -> a) -> (b -> a) -> b -> [a]     -- (A4)

If you want to learn more and read a paper you can start with Principal type-schemes for functional programs.

CodePudding user response：

Prelude> :t h
h :: Foldable t => Bool -> t Bool -> Bool
Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
Prelude> :t (&&)
(&&) :: Bool -> Bool -> Bool
Prelude> 

By "plugging in" (&&) you have removed (a -> b -> b) so you need to provide the rest to the function

b -> t a -> b

That is restricted by (&&) to be a bool as second param to it, and the second parameter is the t a which is also restricted to being a bool. since a and b needs to be the same type as in the (a->b->b) function.