Explicit type signatures for polymorphic types. Part II

Question

This is a follow up to a previous question; I got an answer I didn't really understand, but accepted. So I'll ask it again.

I still don't understand how this makes sense:

type Parse a b = [a] -> [(b,[a])]
build :: Parse a b -> ( b -> c ) -> Parse a c
build p f inp = [ (f x, rem) | (x, rem) <- p inp ]

Now, obviously, p binds to the first argument of type Parse a b. And, again obviously f binds to the second argument (b -> c). My question remains what does inp bind to?

If Parse a b is a type synonym for [a] -> [(b,[a])] I thought from the last question I could just substitute it:

build :: [a] -> [(b,[a])] -> ( b -> c ) -> [a] -> [(c,[a])]

However, I don't see that making any sense either with the definition:

build p f inp = [ (f x, rem) | (x, rem) <- p inp ]

Would someone explain type synonyms?

Answer 1

Now, obviously, p binds to the first argument of type Parse a b. And, again obviously f binds to the second argument (b -> c). My question remains what does inp bind to?

The argument of type [a]

If Parse a b is a type synonym for [a] -> [(b,[a])] I thought from the last question I could just substitute it:

build :: [a] -> [(b,[a])] -> ( b -> c ) -> [a] -> [(c,[a])]

Almost; you need to parenthesize the substitutions:

build :: ([a] -> [(b,[a])]) -> ( b -> c ) -> ([a] -> [(c,[a])])

Because -> is right-associative you can remove the parentheses at the end, but not at the beginning, so you get:

build :: ([a] -> [(b,[a])]) -> ( b -> c ) -> [a] -> [(c,[a])]

This should make it obvious why inp has type [a].

Answer 2

You can substitute -- but don't forget to bracket! That should be:

build :: ( [a] -> [(b,[a])] ) -> ( b -> c ) -> ( [a] -> [(c,[a])] )

Because the function arrow is right-associative you can dump the right-hand set of brackets, but crucially you cannot discard the new ones on the left:

build :: ( [a] -> [(b,[a])] ) -> ( b -> c ) -> [a] -> [(c,[a])]

So now when you have the line build p f inp, you can see that:

p :: ( [a] -> [(b,[a])] )
f :: ( b -> c )
inp :: [a]

So then we can see that:

p inp :: [(b, [a])]

And thus:

x :: b
rem :: [a]

And:

f x :: c
(f x, rem) :: (c, [a])

And hence the whole list comprehension has type [(c, [a])] -- which neatly matches what build should return. Hope that helps!