You’ve already finished two of the main tasks in this book: implementing some data mining algorithms for analyzing clients and their purchases and looking at several ways to save the information about purchases in a durable container. This chapter is the starting point of the last task: creating a domain-specific language (DSL) for expressing offers to be applied in the Time Machine Store. You will provide a set of combinators to create the offers, which are initially basic offers.
Not all offers expressible in this language will be valid. The interesting part is that you can use the type system to help avoid many of the wrong offers, and this chapter will teach you the features needed to do that.
I will introduce you first to generalized algebraic data types (GADTs), which are a way to create more concrete constructors for your data types. Then, you will see how to encode other invariants using different techniques. In particular, this chapter discusses both functional dependencies (FDs) and type families (TFs), along with singletons .
Once you’ve read this chapter, you’ll have a thorough grasp of the complete Haskell type system. You will be able to understand code that uses the advanced features described here, and you also will be able to use them in your own code.
Domain-Specific Languages
A domain-specific language (DSL) refers usually to a language not intended for expressing any computer program but rather data or computations about a specific problem space. For example, SQL can be seen as a DSL for expressing database queries. Haskell is not a DSL, but rather a general-purpose language, because it’s not tied to any particular application domain.
The existence of DSLs is not new in computer science. Many of the programs you use contain one or several DSLs at their core. For example, CSS is a DSL for expressing presentation attributes of markup elements, regular expressions are a DSL for expressing patterns over a string, hardware designers use specific languages for designing circuits, and so on.
You no longer need developers to write the business rules in your program. If your DSL really expresses the rules using the usual abstractions for the intended domain, the experts on that specific domain can be the ones writing the rules. This decreases the mismatch between domain experts and programmers.
You need to implement only a core DSL, which is usually quite small, and then use the new abstractions to build the rest of the system. This makes the programs easier to write, easier to understand, and easier to maintain because the abstraction of the domain is not scattered between different moving parts.
These advantages are important in the software engineering process. As a result, the concept of DSLs has risen in importance, and many problems are now tackled by means of a custom language for a domain. In fact, many tools are geared toward designing DSLs, and this chapter will make the case that Haskell is one of best in this field.
Embedding Your Language in Haskell
Any DSL you design will ultimately be integrated inside a larger application . That larger application will be written in a general-purpose language, like Haskell. Thus, it’s important to consider the ways in which the DSL can hook into that other language, usually called the host.
One possibility is to make the DSL completely independent of the host language. In that case, you need to develop a full set of tools for this language. At the very least, you need to write a parser for the language. Thus, you get a lot of freedom in the design, but you need to put a lot of effort into its implementation. This way of integrating your language, called external or stand-alone, is useful when the DSL forms the core of your application and you want to provide extra tools (such as debuggers and IDE integration). Think of HTML as a perfect example of this kind of DSL.
Its powerful type system allows you to express invariants that valid values in your DSL must satisfy. This means the extra safety Haskell provides is also in your language.
Haskell syntax is terse, so it doesn’t introduce many strange symbols in your DSL. Using operators and the mixfix application, you can make the values in your new language resemble a natural language description.
Type classes, especially applicatives, monads, and do notation, provide a convenient framework for expressing the abstractions that are part of a DSL. This means Haskell developers can use a well-known notation for many concepts.
Many of the libraries I’ve talked about in this book are actually embedded DSLs: parser combinators like attoparsec for describing grammars only need to use special functions, a query language such as Esqueleto uses a combination of type classes and custom data types, and digestive-functors expresses forms using applicative style and a set of basic ways to treat a form value. As you can see, the features of Haskell are used differently by each DSL, depending on how convenient the features are.
You’ve seen the two advantages of using deep instead of shallow embedding. First, you can give more than one interpretation; that is, you can treat the values of your embedded DSL in different ways depending on the situation. Additionally, you can inspect the syntax tree before creating the meaning and implementing optimizations or statistics about your value.
In this chapter, I will show how to design a deep embedding of the offers language inside Haskell. The next chapter will explain a conceptual tool , attribute grammars, and a concrete implementation of those ideas, UUAGC , which help you express the behavior of one of the offers applied to a basket of products.
The Offers Language
Let’s create a DSL for expressing the offers in the Time Machine Store. In addition to empowering managers to directly encode the offers for your application (so you don’t need to manually implement them each time), implementing the language will be a good way to learn more Haskell. You don’t need a big language for the second objective, so I will keep the core DSL small. As a general guide, you should always try to make your DSL as small as possible because it is easier to work with a small core. For complex needs, you can write functions that generate compound expressions out of the simple language you have created.
- 1.
The language may restrict the offer to be valid only on a set of products.
- 2.
By default, all the offers are valid for an indefinite period of time. The language will provide ways to constrain the starting and ending dates of the offer to extend the offer for a longer time.
- 3.
The language will allow you to make an offer be the union of two offers (e.g., give a free balloon and a 10 percent discount), be just the best out of two (e.g., either give a 10 percent or give a $5 discount), or be conditional upon satisfying some property in the purchase (such as applying an offer only when the client purchases more than $100 worth of products).
These data types are the core of our DSL. But as Exercise 13-1 shows, you can add some helper functions to make it easier to describe offers that follow the same pattern often.
period f d o will constrain the offer o for the following d days starting from day f. Remember that From and Until have as arguments specific points in time, not lengths.
allOf os should be the conjunction with all the offers in the list os.
Then, express the following offer: “From the third day and for five days hence, you will get a free balloon, a free chocolate muffin, and a 10 percent discount in the Time Machine Store.” Check whether your expression corresponds to the correct offer expressed using the core DSL.
In addition to constraining the kind of basic offers that you can express, there are two further requirements that all values in your DSL must satisfy. The first one is the Presents Rule: at some time during the year, the number of presents that will be given for free with a purchase is limited. Thus, the system should check that constraint. The second one is the Duration Rule: you don’t want to allow offers if they violate a time restriction. You’ll learn how to enforce these two rules in the language later in this chapter.
Adding Safety to the Expression Language
Amounts, prices of items, and constant values (those created through the FVal or IVal constructors) should be tagged as numbers.
Comparisons will take as arguments only values tagged as numbers and will produce a value tagged as a Boolean.
Boolean operators will combine only those expressions tagged as Booleans.
The final expression in an offer must be tagged as a Boolean.
The problem is that plain data declarations do not allow you to return different types depending on the constructor of a value. All constructors uniformly construct values of the type expressed after the data keyword. Generalized algebraic data types (GADTs) lift that restriction ; now each of the constructors of the data type can return a different set of type parameters to the type being defined. That is, in the definition of Expr a t, you can return Expr a Bool, Expr Int Int, and so on, but not Offer Char.
Since the arithmetic and comparison operators need to work on both Integer and Float values , we cannot use a type there directly. Instead, we use a Num constraint, since both types are instances of that type class.
Now if you try to build some code with the incorrect expression that started this section, you will get a compile error because the expression will not type check. This is the first example of using the strong type system to constrain the kind of values that the DSL can express.
This interpretation function still needs some love. Exercise 13-2 asks you to complete the work.
Write the missing code of the interpretExpr function for the cases of Expr being defined by a regular ADT and by a GADT. In the case of PriceOf, you should take into account that the same product may appear more than once in the purchase list.
Even though here you’re tagging types using built-in types from the Prelude module , nothing stops you from using any other type here. Actually, it may be the case that you create new data types only for tagging other types. In that case, you don’t even need any constructors in the declaration since you will never use them. You can create empty data declarations if you enable the EmptyDataDecls extension .
Time traveling is a tiresome task, so users of your time machines need to eat snacks from time to time. However, people have constraints on the food they can take, such as vegetarian, no pork, low salt, and so on. Exercise 13-3 asks you to build a GADT that represents those snacks tagged with constraints.
Create a GADT representing a set of possible snacks for the Time Machine Store. The snacks must be tagged with a type defining whether it’s OK for vegetarians and whether it contains pork. Use empty data types as shown in this section.
Type-Level Programming
It seems that this idea of tagging types with extra information is quite successful, at least for expressions. However, the way in which you can do it is quite limited because you can use only other types and only as constants or variables that you don’t inspect.
One way to have a more powerful type system is by allowing values, in addition to types, to take part in other types. For example, you might be interested in tagging lists with their length and expressing things such as “the length of append l1 l2 is the sum of the lengths of l1 and l2.” As you can see, in this case, the tag is not another type, but rather a number (or a value in the world of Haskell). Dependent type systems open the last barrier that Haskell imposes between values and types and allow you to create types depending on values, as the list tagged with its length that was being discussed.
Haskell is not a dependently typed language, though; it imposes a clear separation between the world of terms or expressions and the world of types. In Haskell , values are only allowed to depend on other values (via regular function parameters) or on types (via parametric or ad hoc polymorphism), whereas types are allowed to depend only on other types (via type variables). On the other hand, it’s forbidden to use terms as parameters to types. When working with GADTs , you used some empty data types as tags. This approach mimics partly dependent typing but allows tagging only with constant values, not performing any operation on the types. The rest of the chapter is devoted to showing different ways in which you could describe operations that work on types. All these methods are known collectively as type-level programming techniques.
Dependent typing is an extensive area of knowledge. It is expected that Haskell gets more and more of these features as time progresses. If you want to learn more about dependent types, you can read Type-Drive Development with Idris and Programming in Idris: A Tutorial both by Edwin Brady,1 “Dependently Typed Programming in Agda” by Ulf Norell and James Chapman,2 Certified Programming with Dependent Types by Adam Chlipala,3 or Software Foundations by Benjamin C. Pierce et al.4 (the latter two using Coq).
The programming techniques that will be presented in the rest of the chapter are usually categorized as advanced Haskell features . You don’t need to understand every detail of functional dependencies and type families to be a proficient Haskell programmer. Indeed, these features are recent additions to the Haskell language, so their use is not widespread yet.
However, type-level programming is becoming an increasingly important technique. More recent libraries, such as Persistent and Yesod, make heavy use of them. Even though you may skip some of this material in a first reading, you should come back to it in the future. It will help you understand many of the error messages and design decisions of those libraries, and it will also help you build better applications.
Two Styles of Programming
Functional dependencies (FDs) allow you to constrain the parameters of type classes. Given the correct constraints, the Haskell compiler can infer a unique type, which can be seen as the result of a type-level function.
Type families (TFs) let you create functions that assign a type given a set of other types. Recent versions of GHC include two kinds of type families. Closed type families are the closest to the intuitive notion of type function, and open type families are like type classes in the sense that you may add a new rule to an open type family at any point, like you may add an instance to a type class.
Both ways are equally powerful, so in principle it doesn’t matter which one you choose to encode your invariants. However, in some cases, it’s easier to use FDs, and in other cases, it’s better to use TFs. As a rule of thumb, start using TFs (because the type-level concepts they expose are closer to the simple Haskell level) and use FDs if you need more expressiveness in the relations between types.
Although they have the same power, mixing FDs and TFs in the same code can become challenging. Thus, if you depend on a library that exposes FDs or TFs, you should use the same technique to avoid further problems. The situation, however, may improve in newer versions of the GHC compiler.
Representing Natural Numbers
Since the tags that will be used to check the Presents Rule are natural numbers, you must know how they are encoded as values previous to using FDs or TFs to represent them at the type level. This section tries to give a fast-paced introduction to natural numbers . Feel free to skip it if you already know the standard data type for natural numbers and how addition, maximum, and minimum are coded using them.
Zero is a natural number.
For every natural number n, there exists a successor of n, which is also a natural number.
You can think of this encoding of natural numbers as lists in which you don’t care about elements. Then, addition would be concatenation of lists, taking the minimum would be returning the list with the smallest number of elements, and so on.
If you add 0 to any natural number y, the result is y.
If you add the successor of x to y, this is equal to the successor of the addition of x and y. Since the successor is equivalent to (+1), you can see this as encoding the algebraic law that reads (x + 1) + y = (x + y) + 1.
The result is the number 3 represented in this way, as you can see in the output.
The minimum function has a similar skeleton. Exercise 13-4 asks you to write the full code.
Write a function min' of type Number -> Number -> Number that computes the minimum value of the two natural numbers given as arguments.
Functional Dependencies
As stated in the previous section, functional dependencies represent one of the ways in which you can encode type-level operations in Haskell. However, the original intention of FDs was to enhance the type class mechanism by constraining the set of types that can be related via a multiparameter type class. In this section, I’ll start looking at this original aim and then move on to encoding the Presents Rule via FDs.
Categories of Products with FDs
Let’s diverge for a moment from the offers language and focus on a completely different problem . Until now, all the products in the Time Machine Store were represented using the same data type, Product. However, the information for describing a time machine is not the same as that needed to describe a book or a costume. Thus, it may be interesting to make Product a type class and make data types represent different categories of products.
In addition to different fields to describe them, you use different products in different ways. For example, you travel with a time machine, but you read a book. It would be interesting to specify, for each category of products, which operations are available to perform upon them. Then, you could include specific instructions on how to perform each operation and a specification of which operation should be used to test the product.
Remember that you need to enable the MultiParamTypeClasses extension for GHC to accept this code.
The error message tells you that there’s not enough information to infer which operation type corresponds to each product category. But the intent of the code is clear. For TimeMachine, the corresponding operation type is TimeMachineOps, and only that one. Somehow, the compiler should infer that when you’re using a TimeMachine, the operations will always belong to TimeMachineOps .
The compiler won’t complain because the code is perfectly fine. But now you can see why the definitions of totalAmount or testOperation were ambiguous. Potentially, there is another instance where a declaration different from Product TimeMachine TimeMachineOps may be applicable.
The solution is to add a constraint to the type class declaration that exactly expresses that given a specific category of products, only one possibility is available for the set of operations. This is done via a functional dependency, a concept from database theory that describes exactly these scenarios. Functional dependencies are written in the head of the class declaration , separated from the name and type variables by the | sign, and with commas between each of them. Each functional dependency, in turn, follows the same schema, x 1 ... x n -> y 1 ... y m, expressing that for each unique substitution of the types x 1 to x n, there’s only one possible compound value of y 1 to y m. Note that you need to enable the FunctionalDependencies extension to use this syntax in your own type classes.
Now the compiler allows the definition of totalPrice and performTest because it knows that given a category for products, only one possible set of operations will be available, so it can select them.
Functional dependencies are helpful once you understand when they are needed in a type class declaration . The “Functional Dependencies in Monad Classes ” sidebar describes their use in monad classes. Then Exercise 13-5 proposes a task for helping you understand these ideas.
When the type classes supporting the lifting of the basic operation in each monad transformer (MonadState, MonadReader, MonadWriter, etc.) were discussed in Chapter 7, functional dependencies appeared in the class declarations but weren’t explained.
The crux of a type class such as MonadState is that it declares both the monad that performs the operations and the type of elements saved in the state because they are both needed in the signatures of some operations. The functional dependency states that given a specific monad, the type of the state values is automatically known. Think of the State Int monad, for example. From its signature, you already know that only Int can be the type of elements saved in the state.
In the store, two kinds of bags are available: big and small. Create new data types called BigBag and SmallBag for representing each kind of bag. Then, add a new parameter to the Product type class for stating which bag you should use for each category of products. In principle, time machines should go on big bags, whereas books need only small ones. Think carefully about extra functional dependencies .
Vectors Using FDs
At first sight, it seems that functional dependencies have nothing to do with type-level operations in Haskell. However, a second look will show how you can encode type-level functions in this way.
Notice that in almost every example in this section, the code will use more and more GHC extensions. These will be shown using the LANGUAGE pragma. Most of the extensions are needed only for enabling certain syntactic constructs, and the compiler will tell you to enable them if you forget, so you don’t need to worry too much about them.
In fact, if you try to pattern match with VNil, the compiler rejects such declaration, because an empty vector cannot have a length of the form (Succ n).
Since the Plus type class is used only for its results at type level, it’s not necessary to include any function in its body. In that case, Haskell allows you to omit the where keyword from the declaration.
This is expressing the same logic for Peano addition but in a backward style of reasoning. The first instance encodes the rule of adding 0 to a number, whose result is the same as the second argument. The second rule is a bit subtler; it’s expressing that if you know that x + y = z, you can infer the addition (x + 1) + y, which will be exactly z + 1. In some sense, the declaration is reversing the way in which you write the pattern matching on the arguments and handling the recursion via a call to a smaller instance.
To understand how this encoding works, Exercise 13-6 asks you to define binary tree tagged with height, in a similar fashion to vectors.
Create a BinaryTree data type with two constructors: Leafs, which contain only one element, and Nodes, which contain an element and two subtrees. The type must be tagged with the height of the tree. Hint: Implement the max' function for Peano numbers using a type class Max and functional dependencies.
Enforcing the Presents Rule with FDs
There are still some constructors left for the full offers language. Exercise 13-7 asks you to write the rest of them, encoding the type-level functions needed as functional dependencies.
Include the constructors for the remaining offers language: From, Until, Extend, and If. Write them following the same technique from this section. In the case of conditionals, the same considerations as BetterOf should be taken: you cannot always compute the exact value, but you can approximate it.
If you’ve ever used a logic programming language, such as Prolog or Datalog, you may find some resemblance between the way you encode type-level functions using instance declarations and the way you write predicates on these languages. This relation is indeed true: programming with functional dependencies exposes a logic programming style in a Haskell type system.
This extra paradigm brought into Haskell is the main criticism with functional dependencies. The programmer should not change programming styles when moving from term-level to type-level coding. Type families, as you will see later, have a more functional style in their declaration.
Type Families
You’ve already seen how functional dependencies can empower you to construct a stronger type system. This section will show you how to express the same kind of invariants but using the language of type families (TFs). In short, a type family is a function at the type level. It gives you a type given some other types as parameters, but in an ad hoc way and in contrast to parametric polymorphism. The type family may appear in the top level of your module or inside a type class. You will see the purpose of each of them in this section.
Vectors Using TFs
As you can see, the type instances completely mimic the definition of the (+) function on regular, term-level, natural numbers. This similarity makes it easier to port code from term level to type level if you use type families.
The previous code uses closed TFs, an extension available only since version 7.8.1 of the GHC compiler. You can always use open TFs for maximum backward compatibility, which are described in the next section.
Enforcing the Presents Rule with TFs
As in the previous case, it’s your task (in Exercise 13-8) to write the rest of the cases of the data type.
Include the constructors for the rest of the offers language: From, Until, Extend, BetterOf, and If. At this point, you’ll know that you’ll need a type-level function that encodes the maximum of two natural numbers in the last two cases. Define it using type families.
Categories of Products with TFs
The introduction to type-level programming in Haskell stated that functional dependencies and type families had the same power of expressiveness. You’ve already seen how both can encode type-level functions, but there’s still the question of how to use type families to solve the problem with categories of products.
This is not a satisfactory solution, though. When you used a type class along with an FD, you had the option of adding a new product along with its sets of operations at any moment, via a new instance declaration. However, if you follow the approach I’ve just shown, with the previous definition of a TF, you need to add both an instance to the Product type class and a new equation to the Operation type family. This makes the type class and the type family tightly coupled and thus less maintainable.
The problem in this case does not lie in the use of type families but rather in the fact that the type family is defined as a closed one. GHC supports two kinds of type families. The closed ones, which I’ve already introduced, cannot be enlarged with more rules after its definition. In contrast, open type families define a partial function that can be refined or enlarged in other parts of the code.
Notice that in this case the instance declarations appear at the same level of the signature, since they may be defined in completely different modules.
There’s an important difference between closed and open type families. Closed type families follow the usual evaluation model. The first rule is tried; if it doesn’t match, the second rule is tried, and so on, until a match is ultimately found. This can be done because rules from a closed type family have a defined order. However, rules from an open type family come from different, unrelated places and have no order. If the compiler found that two patterns match, it wouldn’t be able to know which choice to take. Thus, GHC forces type instance declarations to not overlap.
Now each application of the open TF Min has one and only one rule to apply.
In many of the cases where functional dependencies are used, you want to create a type-level function but also enforce each implementer of the type class to add a new rule to that type-level function. Or from another point of view, you want to add a type-level function inside the type class. When you enable the TypeFamilies extension, type class declarations are allowed to contain both term-level and type-level function signatures, as desired. The type-level signatures inside a type class are known as associated types.
Remember that types have a simple kind system (the only possible kinds are * and function-like kinds such as * -> *) that checks whether the application of type constructors is correct. If you don’t remember all the details, you can refer to Part 1 of the book, where I introduced the kind system.
Like in the previous section, the type of bag that each category of products needs should be encoded at the type level. Exercise 13-9 asks you to do so, now using associated types.
Using the previously defined data types BigBag and SmallBag, represent the kind of bag each category of product needs. To do this, add a new associated type to the Product type class. Finally, include the instances that express that time machines should go on big bags, whereas books need only small ones.
For the simple scenario of one of the types being completely dependent on the rest of the variables in the type class (like operations and bags in this section), associated types usually make more explicit that only one possibility can be chosen in each instance. However, functional dependencies shouldn’t be overlooked, because they allow richer expression of dependence.
Equality constraints are not often seen in handwritten code, but they are essential to understanding GHC error messages. In most of the instances where the type families do not coincide, the compiler will warn you about an equality constraint (one with ~) not being respected.
Being completely correct, the previous sections didn’t introduce type families but a subclass of them called type synonym families. When using this subclass, you need to use it in both parameters and return expression types that were already defined elsewhere.
Type synonym and data families are not interchangeable, though, because they have different properties (e.g., data families can be partially applied, while type synonym families can’t).
Many of the techniques in this chapter are applied in libraries in Hackage to make stronger guarantees about the code that is executed. You’ve already used associated types, although you didn’t know it back then, when writing the schema description in Persistent.6 Another interesting package that uses type-level programming is HList, which allows you to create lists whose elements have different types.
Data Type Promotion and Singletons
From version 7.4.1 on, GHC includes an extension called data type promotion. When enabled, for each data type at the term level, a new set of types is created at the type level (the type is promoted). Furthermore, a new kind is associated to each of these promoted data types, leading to safer type-level programming . In this section, you’ll see how to take advantage of this feature and how to promote functions in addition to data types using the singletons package.
A Further Refinement to the Presents Rule
Remember that kinds are used to categorize types, like types do for values. In Haskell, without data type promotion, all the fully applied data types have kind *. However, this extension opens the door to user-defined kinds, as the example shows.
In this case, the annotation is not needed because the compiler is able to infer that the kind of n must be Nat. But it’s still interesting to make it explicit, at least for documentation purposes and to ensure that a change in your code doesn’t make the compiler infer a different type.
As you can see, the DataKinds extension brings to type-level programming most of the safety that types give to the Haskell programs at the term level. Furthermore, the automatic promotion makes it easier to declare the types that will be used for programming at the type level. However, the kind system is not as powerful as the type system (e.g., you don’t have anything like kind classes), but for most of the type-level programming, this extension should be more than enough.
Cooking with Singletons
The DataKinds extension is really useful , but it doesn’t give you the full package. Your data types can be promoted to the type level seamlessly, but you still need to define your type-level functions using either FDs or TFs. If you are using some functionality that was already available at the term level, this means that you need to duplicate code and to do so in different styles of programming, hurting the readability and maintainability of the code.
The singletons package provides a pragmatic solution to this problem. Using the metaprogramming facilities of Template Haskell, it creates type-level versions of the term-level functions you ask for. Although the two worlds are still separated, this library creates the illusion that the same constructors and functions are used in both levels seamlessly.
To start using the package, you must add it as a dependency of your project and import the Data.Singletons.TH module in your source file. The expansion of Template Haskell blocks user type families and data type promotion, so in addition to the metaprogramming extensions, you need to enable them in your source file, or the code will refuse to compile.
The code inside the block starting from [d| to |] must be indented to work correctly. Double-check this fact when working with singletons.
In this section, we are defining our own version of promoted natural numbers and several operations over them. This is not needed, though, since the singletons package contains a quite complete copy of Haskell’s Prelude in the type level. You can find it in the Data.Singletons.Prelude module.
Enforcing the Duration Rule
I am adding ticks to the end of some names to disambiguate them from the ones in the singletons’ Prelude.
Almost any use of singletons leads to the UndecidableInstances extension . This is because the compiler cannot prove that the TFs you’ve created will always terminate their execution when you have nested TFs. This nesting appears in the promoted TFs because of the call to compare inside restrictFrom. However, if you know that the function you wrote will terminate, it’s safe to unveil that restriction and tell the compiler to accept that function without further termination checks.
The problem is that you cannot use promoted kinds in a constructor; only types of kind * are allowed. In particular, using Nat is forbidden.
There are some constructors left for the full Offer data type. Exercise 13-10 asks you to finish the job.
GHC provides extra features for tagging types with either natural numbers or strings. If you enable the TypeOperators extension and import the GHC.TypeLits module, you can use numbers and string literals at those places where you need a type of kind Nat (for natural numbers) or Symbol (for strings).
Note that this module provides only a small set of operations on natural numbers, namely, addition, product, and exponentiation, as well as a type class that encodes whether two type-level numbers are related as being less or equal.
data and function declarations express how to create values that Haskell can use to compute at runtime.
Promoted data types and kinds and type-level functions expressed as either FDs or TFs are evaluated at compile time and allow you to tag values with stronger types that introduce extra invariants.
Singleton types are the bridge between the worlds. When you need a type-level value that should also be reflected at runtime, you should use them.
Exercise 13-11 provides an exercise on a different domain to help you better understand these relations.
You must tag images with their bounding box, that is, the smallest rectangle that contains the whole of the image. For example, if you have the union of the rectangles from (1,0) to (5,4) and from (0,1) to (3,2), the bounding box is (0,0) to (5,4). You can draw them on paper to convince yourself about that.
The type-level calculations should be developed using the techniques from the singletons package. Think carefully about which places need singleton types.
Summary
This chapter introduced the concepts of external/stand-alone and internal/embedded domain-specific languages and the difference between deep and shallow embedding.
Generalized algebraic data types allow constructors of a data type to build values with different types; you used that extra functionality to create type-safe expressions.
You were introduced to the idea of tagging a type with some extra information, which allows you to check stronger invariants at compile time.
You explored several possibilities for doing type-level programming in Haskell, including functional dependencies, type families, and data type promotion. The main characteristic of Haskell in this aspect is the separation between the term and type worlds.
Functional dependencies and associated types refine the type class mechanism in Haskell and were covered in this chapter.
Data type promotion and the singletons library make it possible for you to move declarations from the term level to the type level. Furthermore, it extends the kind system to provide safer type-level programming in Haskell.