Lecture: Types Revisited

Dear students:

My love for Haskell began with higher-order functions. I saw a language that respected my time and my brain. Instead of forcing me to write the same iteration code again and again, someone identified the common algorithmic patterns and wrote them up as map, filter, and fold. These higher-order functions seemed like the big lesson that Haskell had to offer the world, and I was happy to ignore the rest of the language, which seemed too exotic to be practical.

However, I was naive. I had been using languages like Java and C++ that told me their type system would make my code safer. In truth, those type systems didn't catch a lot of errors, and they also generated a lot of work for me. As I kept learning Haskell, I saw that type systems were capable of more than the languages I was using offered me. Today we'll have a look at that type system.

Aside

Some of you question the value of Haskell. Certainly we have academic reasons for including it in this course: your mind is fixated on objects after Java and you lack fluency in functions, and you think mutability is the only sensible way to program and cut yourself off from ideas that might build safer and faster software. I'd like to offer another justification of its inclusion: the top-paying technologies as reported in the most recent Stack Overflow Developer Survey.

Functional programming languages dominate the top of this list. Haskell developers who responded earn approximately $15K more than JavaScript and Java programmers. Zig, Erlang, F#, Clojure, Elixir, LISP, Scala, and OCaml are functional languages that rank even higher. Ruby and Rust are also near the top of this list. At most we can say salary and functional languages are correlated. It could be that functional programming skills lead to higher salaries, or it could be that quality programmers like to use funcional languages, or there could be some other explanation, like a quality education, that leads to both effects.

Maybe

Let's get talking about Haskell's type system. One of its nice features is that it can be used to communicate failed computations. But first, let's consider C. What does the function atoi do when we feed it a bad string? It returns 0. What if we feed it the string "0". It returns 0. Hmm...

Suppose we are asked a yes-or-no question about something, and we don't know the answer. We don't want to answer yes, nor do we want to answer no. We need a third choice. A similar situation happens in code. Sometimes we don't have a value to return. Perhaps because the file we were expecting to get the answer from is missing. Or perhaps the user entered malformed data.

We need a way to signal that something has gone wrong that won't get confused with a regular return value. Exceptions are one such signal. They're an extreme response that drastically alters the flow of the program. Exceptions are like yelling fire to get out of a theater. Exceptions are like donning the Ring of Power to exit your 111st birthday party. Exceptions are like using the window instead of the stairs.

A less extreme response is to use the normal return mechanism, but instead of returning a plain value, we make the return optional using the Maybe type. Maybe is defined using the data command:

data Maybe a = Just a
             | Nothing

A function that returns a Maybe Bool has three possible return values: Just True, Just False, and Nothing. A caller that wants to act on the result will have to pattern match on these possible values.

Sometimes programmers try to return null to mark an invalid response. One problem with null is that it only works when we're returning a reference. Another problem is that most languages don't force callers to check for it. The Maybe type uses the type system to force callers to recognize both valid and invalid returns. We'll see this idea of optional types again in Rust.

Polygon

Let's continue exploring Haskell's type system by building an application for drawing and transforming polygons. We want to draw these polygons, but let's not use Haskell for that. Instead, we'll target the web-based graphing calculator Desmos!

Viewer

This HTML page, which I've named index.html, embeds an interactive Desmos graph into a page:

<!DOCTYPE html>
<html>
<head>
  <title>...</title>
  <script src="https://www.desmos.com/api/v1.7/calculator.js?apiKey=USE-YOUR-OWN-APIKEY"></script>
  <style>
#calculator {
  position: fixed;
  left: 0;
  right: 0;
  top: 0;
  bottom: 0;
}
  </style>
</head>
<body>
  <div id="calculator"></div> 
  <script src="main.js"></script>
</body>
</html>

The HTML page loads this JavaScript file, which I've named main.js:

let parameters = new URLSearchParams(window.location.search);
let div = document.getElementById('calculator');
let calculator = Desmos.GraphingCalculator(div);

function plot(key) {
  let points = parameters.get(key);
  let rightIndex = points.indexOf(')');
  let first = points.substring(0, rightIndex + 1);
  points = `${points},${first}`;

  calculator.setExpression({
    id: key,
    latex: points,
    lines: true,
  });
}

plot('points');

If we open index.html in a browser, we'll see an empty graph. To plot something, we need append a list of 2D points as a query parameter. .../index.html?points=(0,0),(2,1),(1,4). The function plot extracts out this list, repeats the first point at the end to make a closed polygon, and then feeds the list to a helper function from the Desmos library.

We can test this with a quick little main function. The Web.Browser module has a function that can even open the web page for us:

import Web.Browser
path = "http://localhost:8000/index.html"

main = do
  let p = (2, 0)
  let p' = (4, 3)
  let url = path ++ "?points=" ++ show p ++ "," ++ show p'
  openBrowser url

Point

We'll write the backend of our polygon transformer in Haskell. Let's start with our simplest type. A good rule of thumb is to create a custom type for any compound data or data that has special operations. Desmos expects a list of points, so let's start with modeling a point.

A Point is just two doubles. We could use a tuple instead of making our own type. If we did, we should also define a type synonym so that we can use a meaningful word instead of the tuple type syntax:

type Point = (Double, Double)

A type synonym is not a new type. It's just a handy name. We've used type synonyms in C with typedef.

However, later on we're going to add our type to a typeclass. It's not impossible to make tuples members of a typeclass, but we have to enable some language extensions to go that route. Let's just make our own tuple-ish Point type use the data command:

data Point = Point Double Double

We only have one variant. From your reading you know that the type of the constructor function Point is Double -> Double -> Point.

Debugging will be a lot easier if we have a way to turn a Point into a printable string. We make Point a member of the Show typeclass:

instance Show Point where
  show (Point x y) = "(" ++ show x ++ "," ++ show y ++ ")"

Now the type's clients can write show p. However, if numbers get small, they are shown in scientific notation. For example, show 0.01 yields "1.0e-2". Desmos won't accept this representation. Instead, we'll call upon the printf function from the Text.Printf module:

import Text.Printf

instance Show Point where
  show (Point x y) = printf "(%.2f, %.2f)" x y

Transform

Next we want to be able to transform points. This class isn't really about graphics, so we're going to breeze over this. Points are generally changed in these three ways:

• Translate by some x- and y-offsets
• Scale about the origin by some x- and y-scale factors
• Rotate about the origin by some angle

These transformations are often sequenced together as a scene animates or as the user interacts with the display. Let's make it so we can build up a list of transformations. This calls for a new type. This time we'll make a new custom type with three variants:

data Transform = Scale Double Double
               | Translate Double Double
               | Rotate Double

In your reading, you learned that this was called a tagged union. Haskell's data command subsumes all the various ways of defining types you've encountered in C and Java.

We have points, and we have transforms. Now we add a function that applies a single transform to a single point:

transform :: Transform -> Point -> Point
transform (Scale sx sy) (Point x y) = Point (sx * x) (sy * y)
transform (Translate dx dy) (Point x y) = Point (x + dx) (y + dy)
transform (Rotate angle) (Point x y) = Point x' y'
  where x' = cos angle * x - sin angle * y
        y' = sin angle * x + cos angle * y

Because we have a type definition, we can break the function into subdefinitions using pattern matching. Scaling and translation employ fairly innocent arithmetic. The math behind rotation comes from a trigonometric identity.

We adjust our main function to show the transformed point:

main = do
  let p = (2, 0)
  let p' = transform (Rotate 0.1) p
  let url = path ++ "?points=" ++ show p ++ "," ++ show p'
  openBrowser url

Polygon

Great, but we want to transform entire polygons, not just individual points. While we could just use a type synonym, a custom type will give us more control. It only has one variant that wraps around a list of Point:

data Polygon = Polygon [Point]

We make Polygon a member of the Show typeclass also:

import Data.List

instance Show Polygon where
  show (Polygon points) = intercalate "," $ map show points

Intercalate is a fancy term for the join operation.

We also want to be able to transform polygons. But there's a problem. We've already defined the transform function, and it only works on points. Two choices lie before us:

• Name the function that transforms polygons something different.
• Define a typeclass that unlocks overloading.

The second option gets us using another facet of Haskell's type system, so we choose it.

Typeclass

A typeclass is an interface. At its simplest, it's just a set of function signatures. In our case, we want to overload the function transform, so declare it and name the typeclass Transformable:

class Transformable a where
  transform :: Transform -> a -> a

Now we bring the definitions for Point under the umbrella of the typeclass using the instance command:

instance Transformable Point where
  transform (Scale sx sy) (Point x y) = Point (sx * x) (sy * y)
  transform (Translate dx dy) (Point x y) = Point (x + dx) (y + dy)
  transform (Rotate angle) (Point x y) = Point x' y'
    where x' = cos angle * x - sin angle * y
          y' = sin angle * x + cos angle * y

Since we have a typeclass, the Polygon type also gets this function. Its definition of transform defers most of the work to the definitions from Point by mapping over its list:

instance Transformable Polygon where
  transform op (Polygon points) = Polygon $ map (transform op) points

Our main function may now create a square and transform it:

main = do
  let shape = Polygon [Point 1 1, Point 2 1, Point 2 2, Point 1 2]
  let xform = Scale 1.2 1.4
  let polygon' = transform xform shape
  let url = "http://localhost:8000/index.html?points1=" ++ show polygon ++ "&points2=" ++ show polygon'
  openBrowser url

Gauntlet

Suppose we wish to run a point or shape through a gauntlet of transformations. This task is easier if we recognize that a gauntlet of transformations is itself a transformation, which means we need a new variant for a list of Transform:

data Transform = Scale Double Double
               | Translate Double Double
               | Rotate Double
               | Gauntlet [Transform]

The only other task is to add a case to the transform function for Gauntlet. The last transform in the list is applied to the point first, producing a new point that is fed into the next transform. What is this pattern? A fold. In particular, a right fold. This single foldr call runs the point through the gauntlet:

instance Transformable Point where
  -- ...
  transform (Gauntlet ops) point = foldr transform point ops

We just added a whole lot of expressive power with two lines of code thanks to the type system and higher-order functions.

TODO

Here's your list of things to do before we meet next:

See you next time.

P.S. It's time for a haiku!