Recognizing haskell types

Question

I'm having some difficulties in understanding the types in haskell. Let's consider the following functions and look at their types.

reduce f s [] = s
reduce f s (x:xs) = f x (reduce f s xs)

for m n f s = if m>n then s else for (m+1) n f ( f m s )

comp f g x y = f x (g x y)

iter 0 f s = s
iter n f s = iter (n-1) f (f s)

We'd have something like:

reduce :: (t1 -> t -> t) -> t -> [t1] -> t
for :: (Ord a, Num a) => a -> a -> (a -> t -> t) -> t -> t
comp :: (t -> t2 -> t3) -> (t -> t1 -> t2) -> t -> t1 -> t3
iter :: (Num t) => t -> (t1 -> t1) -> t1 -> t1

What I don't clearly understand is that in reduce function f takes two parameters, and in for function f again takes two parameters. All I can see is that it takes only one. Well if it would be something like that:

for m n f s = if m>n then s else for (m+1) n f m n

It would be more obvious and easy to recognize that f indeed takes two parameters.

I'm wondering if there exist some ways or method to deduce the types for functions in haskell. In addition to these examples I'd ask for some different examples, so that I can overcome that hardship.

EDIT: In my case function definitions are given, I am just trying to infer their types

Answer 1

Where you're making a thought mistake is in even considering f ( f m s ). That is not a subexpression of the for definition: recall that function application is parsed from the left. So

for (m+1) n f ( f m s )
 ≡ (for (m+1)) n f ( f m s )
 ≡ (for (m+1) n) f ( f m s )
 ≡ (for (m+1) n f) ( f m s )
 ≇ (for (m+1) n ) (f ( f m s ))
 ≇ for (m+1) (n f ( f m s ))
 ≇ for ((m+1) n f ( f m s ))

The last inequality is probably most obvious, because you'd be applying the function (m+1) to three arguments... that sure looks very unlikely.

If you need any "mental parenthesising" for understanding the function, it's normally best to put them around each function argument:

for (m+1) n f ( f m s )
 ≡ for (m+1) 
       (n)
       (f)
       (f m s)

and, if that helps you because it looks more like what you'd have in mainstream languages, you can also uncurry everything:

 ≅ for ( m+1, n, f, f(m,s) )

(though you'd better forget about that one quickly)

---

By the way: if you see a function applied to only one argument, it doesn't mean the function type has only one argument. In fact, the main strength of Haskell's curried syntax is that you can easily do partial application: e.g.

Prelude> :t take
take :: Int -> [a] -> [a]
Prelude> :t take 3
take 3 :: [a] -> [a]
Prelude> map (take 3) ["looooong", "even loonger", "terribly long"]
["loo","eve","ter"]

You see I've only applied take to one argument, the other one is automatically taken from the list by map.

Another example, with operator sections,

Prelude> :t (+)
(+) :: Num a => a -> a -> a
Prelude> :t (+ 1)
(+ 1) :: Num a => a -> a
Prelude> map (+ 1) [4,5,6]
[5,6,7]

Answer 2

The type of f in the following definition is quite easy to infer

for m n f s = if m>n then s else for (m+1) n f ( f m s )

This could be rewritten (for clearity) as

for m n f s 
    | m>n       = s
    | otherwise = for (m+1) n f ( f m s )

1. for (m+1) n f (f m s) is a call of for,

2. which means f m s needs has the same type as s,

3. this requires f to have type t1 -> t -> t
   (t1 for m, and t for s)