Type infererence by hand

IPI asked this how #haskell:

How can I mentally infer the type of the composition of these functions?

    a :: [[Char]] -> [([Char],Int,Int)]
    b :: [Int] -> [(Int,Bool)]
    c :: [([Char],Int,Int)] -> ([Char],Int)
    d :: [(Int,Bool)] -> [[Char]]

That is, what is the type of:

    c . a . d . b

The first thing I’d do is rename the tricky types:

    a :: [String] -> [(String,Int,Int)]
    b :: [Int] -> [(Int,Bool)]
    c :: [(String,Int,Int)] -> (String,Int)
    d :: [(Int,Bool)] -> [String]

and then introduce some type synonyms:

    type A = [String]
    type B = [(String,Int,Int)]
    type C = [(Int,Bool)]

Now we can rename the complex types to a more symbolic form:

    a :: A -> B
    b :: [Int] -> C
    c :: B -> (String,Int)
    d :: C -> A

and now we can see how to combine the pieces. It’s a little jigsaw puzzle!

    b :: [Int] -> C

so there’s only one option to compose with b, namely

    b :: [Int] -> C
    d :: C -> A

composing these, and we hide the intermediate result:

    d . b :: [Int] -> A

now, we need something that takes an A:

    a :: A -> B

So the result of something composed with a, will be a value of type B:

    a . d . b :: [Int] -> B

and finally, something that takes a B:

    c :: B -> (String,Int)

leading to:

    c . a . d . b :: [Int] -> (String,Int)

and we’re done!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s