CODEWITHSUNDEEP
haskell
selfPointer
selfPointer

Reputation: 349

Haskell - Determining the annotation type of `map` and a `function`

I was going over a self-graded quizes for Haskell MOOC and could not figure out the following question:

If f :: a -> b, then what is the type of map (.f)?

where the answer is the following:

[b -> c] -> [a -> c] -- correct answer

-- below are wrong answers
[c -> a] -> [c -> b]
(b -> c) -> [a -> c]
[a] -> [b]

I understand that map's type is (a -> b) -> [a] -> [b] according to the map's documentation so I can sort of see why you would get a list ([a -> c]) for the output.

However, I don't understand why the input for this becomes a list ([b -> c]) given that the function f is a -> b. Since the input is a function, why wasn't the input type (b -> c)? (also, why is it using b -> c instead of a -> b?)

Furthermore, I was wondering why it's .f rather than f; I thought that the function composition (.) needed to be in the following format: map . f, but does .f mean something else in this case?

Thank you in advance for your assistance.

Upvotes: 0

Views: 63

Answers (1)

lsmor
lsmor

Reputation: 5063

Deducing the type of some expression is a mechanical work, and kind of fun!

-- You can use :t exp in ghci to cheat, but is worth doing it by hand a few times
-- suggestion: For each expression use different set of variables

-- 1) write every part and its type
(.) :: (b -> c) -> (a -> b) -> a -> c
f   :: x -> z 
map :: (m -> n) -> [m] -> [n]


-- 2) build small steps. 
-- In ( . f) you are applying f as the second argument of .
-- you only need to be carefull with variable names.
-- Align arguments as they are applied
(.) :: (b -> c) -> (a -> b) -> a -> c
f   ::              x -> z 
-- Hence (symbol a ~ b means a is the same type as b)
a ~ x
b ~ z
-- Consuming the second output and use the names of f to make it clearer
(.)    :: (b -> c) -> (a -> b) -> a -> c
f      ::              x -> z 
( . f) :: (z -> c)             -> x -> c 


-- 3) do the same with the whole expresion
-- map ( . f) uses (. f) as its first argument
-- Tricky. Notice that the WHOLE expression (. f) is just the first argument of map
map    :: ( m        -> n      ) -> [m] -> [n]
( . f) :: ( (z -> c) -> x -> c )
-- Hence. Notice that m and n are 
m ~ z -> c
n ~ x -> c
-- Hence, comsume the first parameter and substite variable names
map        :: ( m        -> n      ) -> [m]      -> [n]
( . f)     :: ( (z -> c) -> x -> c )
map ( . f) ::                           [z -> c] -> [x -> c]


-- 4) make var names more digestive. Keep in mind that in step 2) x ~ a and b ~ z
map ( . f) :: [b -> c] -> [a -> c]

Upvotes: 2

Related Questions