CODEWITHSUNDEEP
haskelltypes
Sili
Sili

Reputation: 967

why Haskell can deduce [] type in this function

rho x = map (((flip mod) x).(\a -> a^2-1)) (rho x)

This function will generate an infinite list. And I tested in GHCi, the function type is

*Main> :t rho
rho :: Integral b => b -> [b]

If I define a function like this

fun x = ((flip mod) x).(\a -> a^2-1)

The type is

*Main> :t fun
fun :: Integral c => c -> c -> c

My question is, how can Haskell deduce the function type to b -> [b]? We don't have any [] type data in this function. Thanks!

Upvotes: 2

Views: 264

Answers (2)

pat
pat

Reputation: 12749

map has the following type:

map :: (a -> b) -> [a] -> [b]

So, we can deduce the types of the arguments to map:

(((flip mod) x).(\a -> a^2-1)) :: (a -> b)
(rho x) :: [a]

But the result of map is also the result of rho x, so:

(rho x) :: [b]

Which implies that a and b are the same type, so:

rho :: ? -> [b]

If we examine the mapping function, and make x free, we find the type:

\x -> ((flip mod) x).(\a -> a^2-1) :: Integral b => b -> (b -> b)

The Integral b => b gives us the type of x, and the (b -> b) unifies with the type of the function composition, so we know that this b is the same as the previous one.

rho :: Integral b => b -> [b]

Upvotes: 14

Kaz
Kaz

Reputation: 58617

(rho x) must return a list because it is being passed to map and the type of the list element can be deduced from what is going on in the mapping.

Upvotes: 6

Related Questions