1.3 Working with data

Hackett is a pure programming language, which means functions cannot have side-effects. This makes Hackett functions truly functions in the mathematical sense—the output is always the same for a given input, and a function’s evaluation cannot do anything but produce a value as output. This encourages a very data-oriented style of programming, assembling pipelines of pure functions that operate on data structures.

For that reason, the basic building blocks of Hackett are built around producing and consuming data, and Hackett makes it easy to define new data structures. You’ve already seen integers, but Hackett provides a myriad of built-in datatypes. This section will cover some of those datatypes, how to produce and consume them, and how to build your own.

1.3.1 Enumerations

One of the most fundamental sorts of data that can be represented in Hackett are enumerations, often called “enums” in other languages. An enumeration is a type that can be one of a set of predefined values. For example, the days of the week form an obvious enumeration. We can define that enumeration in Hackett using the data form:

(data Weekday   sunday monday tuesday wednesday   thursday friday saturday)

This declaration defines two things: a type and a set of values. Specifically, it defines a new type named Weekday, and it defines 7 values, monday through sunday. You can see that each of these names are bound to values of the Weekday type by evaluating them in the REPL:

> monday

: Weekday monday

> thursday

: Weekday thursday

Of course, these values are not very interesting on their own. Presumably, once we have an enumeration, we would like to be able to do something with its values. For example, we might wish to write a function that determines if a weekday is a weekend—that is, if it is sunday or saturday. To do this, we need some way to check if a weekday is a particular value.

We can do this by using pattern matching, which makes it possible to make a decision based on the different values of an enumeration. Here’s one way to write our is-weekend? function:

> (defn is-weekend? : {Weekday -> Bool}     [[sunday] True]     [[monday] False]     [[tuesday] False]     [[wednesday] False]     [[thursday] False]     [[friday] False]     [[saturday] True])

> (is-weekend? saturday)

: Bool True

> (is-weekend? wednesday)

: Bool False

This works! Each clause in defn provides a pattern to match against. If a pattern is the name of an enumeration value, it only matches if the supplied argument is that specific value.

Sadly, while the above definition works, it’s a little wordy. To simplify it a little, it’s possible to use the special _ pattern, which matches any value. This can be used to create a sort of “fallthrough” case:

> (defn is-weekend? : {Weekday -> Bool}     [[sunday] True]     [[saturday] True]     [[_] False])

> (is-weekend? saturday)

: Bool True

> (is-weekend? wednesday)

: Bool False

This works because patterns in defn are matched from top to bottom, picking the first one that successfully matches.

1.3.2 An introduction to lists

While it’s great to be able to represent weekdays with our Weekday type, we don’t have any way to talk about multiple weekdays at a time. To do this, we need a data structure that can hold multiple values of the same type. One such data structure is a list, which represents a singly-linked list. Lists are homogenous, which means they hold a set of values that all have the same type.

A list is built out of two fundamental pieces: the empty list, named Nil, and the “cons” constructor, named ::. These have the following types:

The use of forall in the types of Nil and :: indicates that lists are polymorphic—that is, they can hold values of any type. This will be covered in more detail in a future section.

value Nil : (forall [a] (List a))

value :: : (forall [a] {a -> (List a) -> (List a)})

Essentially, :: prepends a single element to an existing list (known as the “tail” of the list), and Nil is the end of every list. To create a single-element list, use :: to prepend an element to the empty list:

> {1 :: Nil}

: (List Integer) {1 :: Nil}

A list of more elements can be created with nested uses of :::

> {1 :: {2 :: {3 :: Nil}}}

: (List Integer) {1 :: 2 :: 3 :: Nil}

Additionally, :: is an infix operator that associates right, so nested braces can be elided when constructing lists:

> {1 :: 2 :: 3 :: Nil}

: (List Integer) {1 :: 2 :: 3 :: Nil}

Once we have a list, we can do various things with it. For example, we can concatenate two lists together using the ++ operator:

> {{1 :: 2 :: Nil} ++ {3 :: 4 :: Nil}}

: (List Integer) {1 :: 2 :: 3 :: 4 :: Nil}

We can sum a list of numbers using the sum function:

> (sum {1 :: 2 :: 3 :: Nil})

: Integer 6

We can even apply a function to each element of a list to produce a new list by using the map function:

> (map (+ 1) {1 :: 2 :: 3 :: Nil})

: (List Integer) {2 :: 3 :: 4 :: Nil}

Combining this with our Weekday type from earlier, we can create a list of all the days in the week:

> (def weekdays : (List Weekday)     {sunday :: monday :: tuesday :: wednesday      :: thursday :: friday :: saturday :: Nil})

The filter allows selecting elements from a list that match a given predicate. Using filter combined with the is-weekend? function we wrote earlier, it’s possible to produce a list that contains only weekends:

> (filter is-weekend? weekdays)

: (List Weekday) {sunday :: saturday :: Nil}

1.3.3 Representing operations that can fail

While it’s interesting that we can construct lists and iterate over them, it’s important to be able to consume lists as well. In many languages, there are functions to access the first element of a list, and Hackett has such a function, too, called head. However, head is an interesting operation, since it can fail. What happens if we try to get the first element of an empty list?

> (head (: Nil (List Integer)))

: (Maybe Integer) Nothing

Rather than produce an error, Hackett returns Nothing. At first, this might seem like null or nil in other languages, but it isn’t—in those languages, almost anything has the potential to be null, so it’s easy to accidentally forget to properly handle null cases. In Hackett, Nothing is just an ordinary value of type (Maybe a).

To see why this is different, let’s apply head to a list that actually does contain some elements:

> (head {1 :: 2 :: 3 :: Nil})

: (Maybe Integer) (Just 1)

Note that it is wrapped in Just. This is because the Maybe type is a wrapper that encodes the notion that the value might not be there. If it is, it is wrapped in Just. If it isn’t, it’s the plain value Nothing.

Many Hackett functions produce Maybe-wrapped values, since there are many operations that have the potential to fail. Importantly, this is always expressed in the function’s type:

> (#:type head)

: (forall (a) {(List a) -> (Maybe a)})

> (#:type tail)

: (forall (a) {(List a) -> (Maybe (List a))})

While this is generally true—the majority of Hackett functions express failure potential at the type level—this is not guaranteed by the typechecker. For more information on the ways functions can fail at runtime, see Partial Functions and Nontermination.

Since Maybe is explicitly annotated in the return type (rather than always implicitly possible, like null in many other languages), you can know exactly which functions can fail, and the typechecker will ensure you properly handle the failure case.

Of course, while this is very nice, it’s not completely useful to get back a value of type (Maybe Integer) if we really need an Integer, since the two are entirely different types. We cannot, for example, add an Integer to a (Maybe Integer):

> {1 + (Just 2)}

eval:560:19: typechecker: type mismatch

between: (Maybe Integer)

and: Integer

in: (Just 2)

So, at some point, we need to have some way to unwrap the Maybe wrapper. One way to do this is using the from-maybe function:

> (#:type from-maybe)

: (forall (a b) {a -> (Maybe a) -> a})

Note that this function is not (forall [a] {(Maybe a) -> a})! Such a function would entirely defeat the purpose of using Maybe to indicate failure, since it would not have any way to properly handle the Nothing case. Instead, from-maybe requires that you specify a default value to produce in the event that the second argument is Nothing:

> (from-maybe 0 (Just 42))

: Integer 42

> (from-maybe 0 (: Nothing (Maybe Integer)))

: Integer 0

However, this is not always the right thing to do. Sometimes, a default value might not make any sense. Sometimes, a failure is something that needs to be handled at a different level, not immediately, but you might still want to modify the value inside a Just wrapper. To do this, it’s actually possible to use the map function to modify the value inside Just, in the same way that it’s possible to modify the values inside a list:

> (map (+ 1) (Just 11))

: (Maybe Integer) (Just 12)

> (map (+ 1) (: Nothing (Maybe Integer)))

: (Maybe Integer) Nothing

If this is confusing to you, you can think of Maybe as a special case of List: while a value of type (List a) can hold any number of as, a value of type (Maybe a) can hold exactly zero or one a. Using the map function on a value wrapped in Just is therefore sort of like mapping over a single-element list, and using it on Nothing is like mapping over the empty list.