5 Words and graphs

 

This chapter covers

  • Modeling a graph structure in Haskell
  • Ensuring invariants on our data types by hiding their construction and modification
  • Reusing implementations with minimal overhead
  • Building simple transformations for strings

Our last project was a minimal clone of a popular UNIX tool. Serious business! But life is more than just writing industry-grade utilities for all of our terminal line numbering needs. Let’s have some fun. And how do people usually have fun? By playing games of course!

A fun little game to play is the word ladder game, which makes the players build chains of words that can be found by transforming single letters within them. The game has many variants, and we will focus on a pretty complex one. But why play games when we could have the computer play for us?

Writing an artificial intelligence, even for a children’s game, isn’t always a cakewalk. This project will make us think about clever usage of data structures to implement the solution for a search problem. While it might seem simple on the surface, we will see that there can be pitfalls, even in child’s play.

5.1 Building a graph

5.1.1 Polymorphic types

5.1.2 Introducing a new module

5.1.3 The Eq type class and type constraints

5.1.4 The flip function

5.2 Encapsulating implementations

5.2.1 Adding and removing entries

5.2.2 Using export lists to hide constructors

5.2.3 The Show type class

5.3 Using and reusing code

5.3.1 Qualified imports

5.3.2 Building maps for permutations

5.3.3 Creating a permutation map from a dictionary

5.4 Parameterizing transformations

5.4.1 List comprehensions

Summary