Getting Started with Types

There are four obvious ways that we might write this function using undefined:

-- With all three arguments bound to variables
addThree a b c = undefined

-- With the first two arguments bound to variables
addThree a b = undefined

-- With the first argument bound to a variable
addThree a = undefined

-- With no arguments bound to a variable
addThree = undefined

All of these implementations assume that we’re replacing the entire body of addThree with undefined, but we can replace individual parts of the body as well. For example, we might create a function called op that represents some binary operation that will eventually be defined as (+) but for now we leave it undefined:

addThree :: Int -> Int -> Int -> Int
addThree a b c = op a (op b c)
  where
    op :: Int -> Int -> Int
    op = undefined

Or, we could write a pointfree version of this function, with the undefined inline:

addThree = (undefined .) . undefined

Be careful though! We can also use undefined to write functions that compile, but won’t really make sense if we try to define the undefined expressions. For example, we could write:

addThree :: Int -> Int -> Int -> Int
addThree = undefined . undefined

Although this will compile, there isn’t a reasonable definition we could provide for undefined that would do what we want. undefined. We can address that by factoring the use of undefined out into a function and giving it an explicit type annotation, as we did in our earlier example using op:

addThree :: Int -> Int -> Int -> Int
addThree = op . op
  where
    op :: Int -> Int -> Int
    op = undefined

Now if we try to compile our program, we’ll get a useful error message:

Undefined.hs:4:12-13: error: …
    • Couldn't match type ‘Int’ with ‘Int -> Int’
      Expected: Int -> Int -> Int -> Int
        Actual: Int -> Int -> Int
    • In the first argument of ‘(.)’, namely ‘op’
      In the expression: op . op
      In an equation for ‘addThree’:
          addThree
            = op . op
            where
                op :: Int -> Int -> Int
                op = undefined
  |
Undefined.hs:4:17-18: error: …
    • Couldn't match type ‘Int -> Int’ with ‘Int’
      Expected: Int -> Int
        Actual: Int -> Int -> Int
    • Probable cause: ‘op’ is applied to too few arguments
      In the second argument of ‘(.)’, namely ‘op’
      In the expression: op . op
      In an equation for ‘addThree’:
          addThree
            = op . op
            where
                op :: Int -> Int -> Int
                op = undefined
  |
Compilation failed.

This gets to the heart of the question “why are there so many different ways to define an expression using undefined”. Since undefined can be used anywhere, for an expression of any type, it’s extremely flexible. You can use undefined almost anywhere, to fill in for almost anything, even things that wouldn’t ever make sense with real code. That’s one of the drawbacks of this technique. When you allow the compiler to infer the type of undefined, you may find that you’re getting a false sense of security when your program compiles. It’s useful frequently enough that you shouldn’t necessarily avoid it altogether, but beware of the drawbacks.

The swap function has a straightforward implementation that closely resembles it’s type. Let’s start by taking a look at the simplest implementation:

swap :: (a,b) -> (b,a)
swap (a,b) = (b,a)

In the exercise, you were asked to consider whether or not there were other ways you could have implemented swap. It’s trivially true to write this function using different code. For example, we can use fst and snd instead of pattern matching, or use let bindings:

swap :: (a,b) -> (b,a)
swap input =
  let
    newFirstElem = snd input
    newSecondElem = fst input
  in (newFirstElem, newSecondElem)

The question then is: are these two implementations really different? They are obviously implemented in different ways, but in Haskell we prefer to reason about functions based on their inputs and outputs. This newer version of swap doesn’t change the behavior compared to our original implementation, so for the sake of this exercise, and for the sake of discussion in most cases, we’d say these are the same function.

The next question then is, can we write a version of swap that behaves differently? The answer is no, not really. We could make a version of the function that crashes, or enters some infinite recursion and never returns a value, but those errors wouldn’t arise naturally from any of the obvious implementations, so we’ll ignore them for now.

If you stop to think about it, you can start to understand why. The input to swap is a tuple that contains two values with types a and b. We have to return a tuple with two values, whose types are b and a. We can’t return the tuple elements in their original order, or ignore one element and duplicate the other, since a and b are different types. We have to return one of each, and in the correct order. Since a and b could be anything, we can’t create a new value for them (what value would we create?). The only way to return a value of type a is to use the one that was given to us. Same for values of type b.

Like swap, there’s an obvious definition of concat that we can start with. Since concat is part of Prelude if you are following along you’ll need to either name your function something else, like myConcat, or you’ll need to add this to the top of your source file, after the module line:

import Prelude hiding (concat)

The first place your mind might go when writing concat is a manually recursive version of the function:

concat :: [[a]] -> [a]
concat [] = []
concat (x:xs) = x <> concat xs

Alternatively, you might choose to use foldr to write your version:

concat :: [[a]] -> [a]
concat = foldr (<>) []

Just like with swap, these two versions of concat will behave the same way, so we’ll say that for our purposes, they are the same function. Unlike with swap, there are also several other definitions of concat that would typecheck, but could return very different results. Let’s look at a couple of examples.

One easy alternative would be to ignore our input and always return an empty list:

concat :: [[a]] -> [a]
concat _ = []

Since lists can be empty, we can construct a value of type [a] without needing to be able to create an arbitrary value of type a. Similarly, there are some operations we can do on lists that we can’t do on arbitrary values of type a. For example, we can write a version of concat that returns the first list:

concatReturnFirst :: [[a]] -> [a]
concatReturnFirst [] = []
concatReturnFirst (x:_) = x

There are some other choices available to us as well, like returning the concatenated list backwards, or returning the longest sublist:

concatReverse :: [[a]] -> [a]
concatReverse = reverse . foldr (<>) []

concatLongest :: [[a]] -> [a]
concatLongest = foldr getLongest []
  where
    getLongest subList currentLongest
      | length subList > length currentLongest = subList
      | otherwise = currentLongest

All of these examples return substantially different values than the original concat, even though they have the same type. There’s a more subtle type of difference that we should also consider. In the last part of this exercise we looked at swap and noted that we could have written a version of swap that simply crashed or never returned a value. At the time, we didn’t bother to think about that much, since it was unlikely that we’d run into the problem. With concat it’s much more likely. For example, imagine that we implemented concat using foldl:

concatFoldl :: [[a]] -> [a]
concatFoldl = foldl (<>) []

For finite lists, this will work exactly the same as our foldr version:

λ concat [[1,2],[3,4],[5,6]]
[1,2,3,4,5,6]

λ concatFoldl [[1,2],[3,4],[5,6]]
[1,2,3,4,5,6]

If we’re working with infinite lists though, only the foldr based concat will return a value:

λ take 10 . concat $ repeat [1,2,3]
[1,2,3,1,2,3,1,2,3,1]

λ take 10 . concatFoldl $ repeat [1,2,3]
Interrupted.

This is one of the more subtle examples of how functions with the same type can differ in their behavior.

These examples show two different ways that functions with the same type can behave differently. When we’re working a type that is concrete enough to allow us to construct new values, we have the option of constructing arbitrary values instead of using the inputs that were provided to us. When we’re working with types that have structure or support operations that might lead to us doing recursion or pattern matching, then we introduce the possibility of infinite recursion, partial pattern matches, and generally having functions that behave differently in various edge cases.

The final example we need to evaluate is the id function. Like concat this is defined in Prelude so you’ll need to either name your function something differently, or add import Prelude hiding (id) after your module declaration if you want to follow along.

As with our earlier solutions, let’s start out with the obvious implementation:

id :: a -> a
id a = a

Like swap, we don’t have enough information to do any meaningful computation on the value that’s passed in, and there’s no obvious implementation that puts us at risk of accidentally raising an error or infinitely recursing.

Where id differs from swap is that we have even fewer options for how we might implement this function. The tuple that was passed into swap gave us some structure, and some choices between pattern matching for calling functions like fst and snd. By comparison, id gives us zero information about the input, and so it leaves us with nothing productive we can do other than returning that value.

We could, of course, create some useless intermediate values, but we couldn’t return them since the type of id resticts what we can return. Thanks to lazy evaluation, any intermediate values that aren’t used won’t be computed, so they aren’t likely to even change the unobservable behavior of the function.

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'