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 and accepted. So I'll ask 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 ]

Someone pease help 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

If you substitute

type Parse a b = [a] -> [(b,[a])]

into

build :: Parse a b -> ( b -> c ) -> Parse a c

you get

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

Remember that x -> y -> z is shorthand for x -> (y -> z) which is very different from (x -> y) -> z. The first is a function that takes two arguments x, y and returns z [precisely it takes one argument x and returns a function, that takes y and returns z]; the second is something that takes a function x -> y and returns z.

Answer 3

The important thing to remember here is that the arrow -> in type signatures is right associative. The type a -> (b -> c) is the same as the type a -> b -> c.

So the type

Parse a b -> ( b -> c ) -> Parse a c

resolves to

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

By associativity, you can remove the last parens, but not the first. That gives you

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

which allows you to write a formula for build with 3 arguments.

Answer 4

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:

f 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!