Filling In Type Holes

Although the solution to this exercise is fairly straightforward, but the process of finding the solution can help us learn how to work with types more effectively. Let’s take a look at the answer, then work through how we got there:

example = mapApply $ map (lookupLetter .) offsets

So, how can we figure this out without resorting to working through the actual implementation details of the algorith? Let’s start at the beginning:

mapApply :: [a -> b] -> [a] -> [b]
mapApply toApply =
  concatMap (\input -> map ($ input) toApply)

example :: [Int] -> String
example = mapApply undefined
  where
    letters :: [Char]
    letters = ['a'..'z']

    lookupLetter :: Int -> Char
    lookupLetter n = letters !! n

    offsets :: [Int -> Int]
    offsets = [rot13, swap10, mixupVowels]

    rot13 :: Int -> Int
    rot13 n = (n + 13) `rem` 26

    swap10 :: Int -> Int
    swap10 n
      | n <= 10 = n + 10
      | n <= 20 = n - 10
      | otherwise = n

    mixupVowels :: Int -> Int
    mixupVowels n =
      case n of
        0 -> 8
        4 -> 14
        8 -> 20
        14 -> 0
        20 -> 4
        n' -> n'

When we have a problem like this, the first thing we can do is to start figuring out what types we’re working with. You’ll sometimes hear this process being called “type tetris” because you’re trying to fit the types together.

mapApply is a good starting point for this problem. Although it’s written as a polymorphic function, we know that example is returning a String. That tells us that, in our call to mapApply we’re setting [b] to String. Since String is the same as [Char], we can see that b must be Char. Let’s re-write the type with this information:

mapApply :: [a -> Char] -> [a] -> [Char]

We can follow the same process of elimination to figure out what type we’ll be using for a, but we’re going to have to do a little guessing. In theory we could ignore list of numbers we’re being passed in to example, and ignore all of the functions defined in the where clause, but it seems unlikely that we’re intended to ignore all of that and instead pass in some other type. Given the evidence at hand, let’s take a guess and try using Int in place of a:

mapApply :: [Int -> Char] -> [Int] -> [Char]

This seems like it could be reasonable. Let’s see what the compiler thinks. One option would be to change the type of mapApply and see our program still compiles. That approach would work for a small example like this, but in a larger codebase we might not be able to change the type without breaking code elsewhere, so let’s use a type hole at the call site instead:

example = mapApply _

If we try to compile this, or load it up into ghci, we’ll see that the compiler tells us that our guess was exactly right. The first argument to mapApply should be [Int -> Char], meaning a must be Int and b must be Char:

FillingInTypeHoles.hs:8:20: error: …
    • Found hole: _ :: [Int -> Char]
    • In the first argument of ‘mapApply’, namely ‘_’

Great! So far, so good, but if we look at the functions we have available to us, none of them have exactly the right type. The closest option that we have is offsets, which has the type [Int -> Int].

We might not be able to pass offsets directly, but maybe we can do something with it to make it fit the right shape. Let’s try asking the compiler. We’ll once again use a type hole, but this time we’ll use the type hole to figure out what we should apply offsets to so that we can get a function with the type we need:

example = mapApply $ _ offsets

In this version of our code, the type hole represents some function that’s accepting offsets as an argument and returning a value of the correct type. Let’s compile this version and see what the type of that function should be:

FillingInTypeHoles.hs:9:22: error: …
    • Found hole: _ :: [Int -> Int] -> [Int -> Char]
    • In the second argument of ‘($)’, namely ‘_ offsets’

This time the type hole wasn’t quite as helpful- it’s only restated what we already knew. Still, we might be able to use this output to help us move forward. The compiler has reminded us that we need something that can turn a list of one type into a list of a different type. In other worse, we should try using map:

example = mapApply $ map _ offsets

We’ve still got a type hole, but we’re slowly narrowing in on the right code. Let’s ask the compiler for help again:

FillingInTypeHoles.hs:9:26: error: …
    • Found hole: _ :: (Int -> Int) -> Int -> Char
    • In the first argument of ‘map’, namely ‘_’
      In the second argument of ‘($)’, namely ‘map _ offsets’
      In the expression: mapApply $ map _ offsets

Now we’re making a little more progress. Our type hole is giving us some more information about what we should pass to map. We need to pass in something that can take a function with the type (Int -> Int) along with some particular Int and return a Char. Looking all of our where bindings, lookupLetter is the only function that returns a Char. The question now is, how should we use lookupLetter? Let’s start by adding a new function to our where clause:

mapFunc :: (Int -> Int) -> Int -> Char
mapFunc f n = undefined

We can try to use type holes here, but they aren’t like to give us a lot of new information since we have a good sense of what types we’re working with. We just need to figure out how to put them together.

One option would be to go completely minimal. We have an Int value, and we need a Char. We already have a function that does that. Maybe we can ignore the function we’re being passed and just call lookupLetter directly?

example :: [Int] -> String
example = mapApply $ map mapFunc offsets
  where
    mapFunc :: (Int -> Int) -> Int -> Char
    mapFunc f n = lookupLetter n

    -- ...

Our program will compile and run this way, but as you might expect it gives us the wrong output:

λ example [5..15]
"fffggghhhiiijjjkkklllmmmnnnoooppp"

We should probably use the function that’s being passed in. There’s only one way that we can write this so that it will type check. We need to pass an Int into f, and the only Int we have is n. f returns an Int, and the only thing we can do with it is pass it to lookupLetters. Let’s give it a try:

example :: [Int] -> String
example = mapApply $ map mapFunc offsets
  where
    mapFunc :: (Int -> Int) -> Int -> Char
    mapFunc f n = lookupLetter (f n)

    -- ...

Let’s give this a try:

λ example [5..15]
"spftqgurhvsuwtjxukyblzcmadnbeacfp"

Success! Following the types, along with a little intuition, has let us finish implementing our application without needing to delve too deeply into the implementation details. Before we move on, let’s take a moment to do a little refactoring. Our current version of mapFunc is simply passing the output of one function into another. As you might recall, we can do that using function composition. We can use eta reduction to remove the explicit n parameter at the same time that we add function composition:

mapFunc f = lookupLetter . f

Now that we’ve factored out n and we’re using function composition, you might notice that we can eta reduce our function again to remove f:

mapFunc = (lookupLetter .)

At this point, we may as well move the definition of mapFunc to it’s call site. That leaves us with a final refactored version that looks like this:

mapApply :: [a -> b] -> [a] -> [b]
mapApply toApply =
  concatMap (\input -> map ($ input) toApply)

example :: [Int] -> String
example = mapApply $ map (lookupLetter .) offsets
  where
    letters :: [Char]
    letters = ['a'..'z']

    lookupLetter :: Int -> Char
    lookupLetter n = letters !! n

    offsets :: [Int -> Int]
    offsets = [rot13, swap10, mixupVowels]

    rot13 :: Int -> Int
    rot13 n = (n + 13) `rem` 26

    swap10 :: Int -> Int
    swap10 n
      | n <= 10 = n + 10
      | n <= 20 = n - 10
      | otherwise = n

    mixupVowels :: Int -> Int
    mixupVowels n =
      case n of
        0 -> 8
        4 -> 14
        8 -> 20
        14 -> 0
        20 -> 4
        n' -> n'