5. Tokenizer: Data Types

26 Jun 2013 Bartosz Milewski View Markdown source

As of March 2020, School of Haskell has been switched to read-only mode.

Sections

In the previous tutorial I sketched the desing of a calculator and implemented the top-level input/output loop. This is a typical pattern in Haskell: the top level is implemented in the IO monad (after all, the signature of main is IO ()) but, as you descend to the lower levels, you enter the realm of side-effect-free pure functions. The first such function is tokenize with the following signature:

tokenize :: String -> [Token]

Before we can start implementing it, we have to define the Token data type and learn more about Strings.

Haskell Data Types

There is one major difference between data in imperative languages and data in Haskell. Haskell data is immutable. Once you construct a data item, it will forever stay the same.

Well, it's not entirely true because of another property of Haskell: laziness. Calling a constructor of a data type is not the same as evaluating it. It's only when you actually peek inside a data item that the constructor is evaluated, and only the part that you're looking at.

But for all intents and purposes, the state of a data item remains frozen after its construction. Moreover, every data item remembers the way it's been constructed. It remembers which constructor was used and what values were passed to it.

But how can you write programs without mutable data? Actually, those of us who had to deal with concurrent programming in imperative languages had to learn (often the hard way) to eschew mutability whenever possible. The fewer opportunities for those hard to reproduce and debug low-level data races, the more reliable your code. This is one more reason to learn programming in Haskell even if your job requries the use of imperative languages: You'll learn how to solve problems without mutable variables.

In Haskell you'll often see mutation replaced by construction. Instead of modifying one element of a data structure, you construct a copy of it with the appropriate change in place. This trick could be prohibitively expensive if you use the wrong data structures. We'll be steering away from such data structures in favor of the so called persistent data structures, which don't require a lot of copying when they are modified. For instance, the workhorse of Haskell data structures is the list, not the array of the vector. We'll talk more about this later.

Enumerated Data Types

The simplest data types just enumerate all possible values. For instance, Bool is an enumeration of True and False (as defined in the Prelude, the Haskell's standard library):

data Bool = True | False

A data structure definition is introduced by the keyword data. Bool is the name of the type we are defining. The right hand side of the equal sign lists the constructors separated by vertical bars. When you create a new Bool value, you use one of these two constructors. Constructor names must start with a capital letter and must be unique per file (two data structures can't share the same constructor name).

When you want to inspect a Bool value, you match it with one of the constructors (remember, a value remembers how it was constructed). There are several ways of matching values to constructors in Haskell. Let's start with the simplest one: Defining a function using multiple equations. Instead of defining a function with one equation, like this:

boolToInt :: Bool -> Int
boolToInt b = if b then 1 else 0

main = print $ boolToInt False

you may split it into two equations corresponding to two constructor patterns, True and False:

boolToInt :: Bool -> Int
boolToInt True  = 1
boolToInt False = 0

main = print $ boolToInt False

Patterns are matched in order, so when boolToInt is called with False, the runtime first tries to match it to True and fails, so it moves to the second pattern False and succeeds. (All equations for the same function must be consecutive.)

(Note: In order to save on parentheses I will start using the function application operator $ that I introduced in the first tutorial. It's been a long time, so here's a quick recap: $ separates a function call from its argument. It's very useful when the argument is another function call, because function calls bind to the left. In our example, without the $ or parenteheses, the function calls would bind: (print boolToInt) False, and would fail to compile. Operator $ has very low precedence so the thing to its right will be evaluated before the function to the left is called, and it binds to the right.)

Here's a useful enumeration that we will use in our project:

data Operator = Plus | Minus | Times | Div

Ex 1. Write a function that takes an Operator and returns one of the characters, '+', '-', '*', or '/'.

data Operator = Plus | Minus | Times | Div

opToChar :: Operator -> Char
opToChar = undefined

main = print $ opToChar Plus

Token

Our tokenizer should recognize operators, identifiers, and numbers. We can enumerate the four operators, but we can't enumerate all possible indentifiers or numbers. For those tokens we need to store additional information: a String and an Int respectively. Here's the definition of Token:

data Token = TokOp Operator
           | TokIdent String
           | TokNum Int
    deriving (Show, Eq)

All three constructors now take arguments. The TokOp constructor takes a value of the type Operator, TokIdent takes a String, and TokNum takes an Int. For instance, you can create a Token using (TokIdent "x"), etc.

I'll explain the deriving clause in more detail when we talk about type classes. For now it will suffice to know that deriving Show means that there is a way to convert any Token to string (either by calling show or by print'ing it), and deriving Eq means that we can compare Tokens for (in-)equality. The compiler is clever enough to implement this functionality all by itself (if it can't, it will issue an error).

Pattern matching on these constructors is more interesting: We not only match the constructor name but also the value with which it was originally called. Here's a definition of a function showContent that uses this kind of pattern matching:

-- show
data Token = TokOp Operator
           | TokIdent String
           | TokNum Int
    deriving (Show, Eq)

showContent :: Token -> String
showContent (TokOp op) = opToStr op
showContent (TokIdent str) = str
showContent (TokNum i) = show i

token :: Token
token = TokIdent "x"

main = do
    putStrLn $ showContent token
    print token
-- /show
data Operator = Plus | Minus | Times | Div
    deriving (Show, Eq)

opToStr :: Operator -> String
opToStr Plus  = "+"
opToStr Minus = "-"
opToStr Times = "*"
opToStr Div   = "/"

Notice that non-trivial constructor patterns require parentheses. In these patterns the argument to the constructor is replaced by a (lower-case) variable that is to be bound to the value stored inside the Token. For instance, in the (TokIdent str) pattern, str will be bound to the string that was used in the construction of the matched token. If the token was constructed using TokIdent "x", str will be bound to "x". (For immutable variables we prefer to use the word "bind" rather than "assign.")

In general, constructors may take many arguments of various types, and they can all be matched by patterns.

Ex 2. Define a data type Point with one constructor Pt that takes two Doubles, corresponding to the x and y coordinates of a point. Write a function inc that takes a Point and returns a new Point whose coordinates are one more than the original coordinates. Use pattern matching.

data Point = Pt ... 
    deriving Show

inc :: Point -> Point
inc ... = ...

p :: Point
p = Pt (-1) 3

main = print $ inc p

By the way, we've seen pattern matching previously applied to pairs. The constructor of a pair is (,).

Ex 3. Solve the previous exercise using pairs rather than Points.

inc :: (Int, Int) -> (Int, Int)
inc ... = ...

p :: (Int, Int)
p = ...

main = print $ inc p

Lists and Recursion

In Haskell a String is a list of characters. Admittedly, list storage and processing is less space/time efficient than the processing of arrays of characters in imperative languages. However, unless your application is string-intensive, the convenience of list manipulation overcomes these shortcomings. And it's easy enough to replace String with the more efficient array-based ByteString in string-intensive applications.

Since we'll be manipulating strings -- and strings are list of characters -- we need to learn about lists first.

First we have to ask ourselvest: What is a list? If you're thinking, "Singly-linked or doubly-linked?", you are talking about implementation, not the essence of a list. So what's the essence of a list? Like any abstract data type, list is defined by operations you can perform on it. The most essential operation is the creation of a list.

One should be able to create a new list by prepending an element to an existing list. This operation is often called "cons," a word taken from Lisp jargon. Notice that this definition is self-referential -- you create a list from a list. To start somewhere, you should also be able to create a list from nothing -- an empty list. Here's a definition of a list of integers that is based just on this description:

data List = Cons Int List | Empty

The fact that this definition is recursive shouldn't bother us in the least. The important thing is that it lets us create arbitrary lists:

lst0, lst1, lst2 :: List
lst0 = Empty        -- empty list
lst1 = Cons 1 lst0  -- one-element list
lst2 = Cons 2 lst1  -- two-element list

This definition can also be used in pattern matching. For instance, here's a function that checks if a list is a singleton:

data List = Cons Int List | Empty

singleton :: List -> Bool
singleton (Cons _ Empty) = True
singleton _ = False

main = do
   print $ singleton Empty
   print $ singleton $ Cons 2 Empty
   print $ singleton $ Cons 3 $ Cons 4 Empty

In this example, I made use of a wildcard pattern _. Let me remind you that his pattern matches anything (without evaluating it). For instance, in the first clause of singleton I'm discarding the integer stored in the list. In the second clause I'm ignoring the whole list, because I know that the first clause, which catches one-element lists, is tried first.

Most importantly, because list is defined recursively, it's easy to implement recursive algorithms for it. For instance, to calculate the sum of all list elements it's enough to say that the sum is equal to the first element plus the sum of the rest. And, of course, the sum of an empty list is zero. So here we go:

data List = Cons Int List | Empty

sumLst :: List -> Int
sumLst (Cons i rest) = i + sumLst rest
sumLst Empty = 0

lst = Cons 2 (Cons 4 (Cons 6 Empty))

main = do
   print (sumLst lst)
   print (sumLst Empty)

But you don't want to be defining a new list type for each possible element type. Fortunately, static polymorphism in Haskell is embarassingly easy. No need for the verbose template<typename T> ugliness. You just parameterize types by specifying a type argument. You may define a generic list by replacing Int by a type parameter a (type parameters must start with lower case and are typically taken from the beginning of the alphabet):

data List a = Cons a (List a) | Empty

List a in this definition is a generic type; List itself is called a type constructor, because you can use it to construct a new type by providing a type argument, as in List Int, or List (List Char) (a list of lists of characters). To avoid confusion, the constructors on the right hand side of a data definition are often called data constructors, as opposed to the type constructor on the left.

In reality, you don't need to define a list type -- its definition is built into the language, and it's syntax is very convenient. The type name for a list consists of a pair of square brackets with the type varaible between them; Cons is replaced by an infix colon, :; and the Empty list is an empty pair of square brackets, []. You may think of the built-in list type as defined by this equation:

data [a] = a : [a] | []

Let me rewrite the previous example with this new notation:

sumLst :: [Int] -> Int
sumLst (i : rest) = i + sumLst rest
sumLst [] = 0

lst = [2, 4, 6]

main = do
   print (sumLst lst)
   print (sumLst [])

There is another convenient feature: special syntax for list literals. Instead of writing a series of constructors, 2:8:64:[], you can write [2, 8, 64].

Pattern matching may be nested. For instance, you may match the first three elements of a list with the pattern (a : (b : (c : rest))) or, taking advantage of the right associativity of :, simply (a : b : c : rest).

Finally, this is the definition of String:

type String = [Char]

String comes with some syntactic sugar of its own: When defining string literals, you can write "Hello" instead of the more verbose ['H', 'e', 'l', 'l', 'o'] .

Here, the type keyword introduces a type synonym (like the typedef in C). You can always go back and treat a String as a list of Char -- in particular, you may pattern match it like a list. We'll be doing a lot of this in the implementation of tokenize. Type synonyms increase the readability of code and lead to better error messages, but they don't create new types.

In the next tutorial we'll continue to work on the tokenizer and learn about guards and touch upon currying.

Exercises

Ex 4. Implement norm that takes a list of Doubles and returns the square root (sqrt) of the sum of squares of its elements.

norm :: [Double] -> Double
norm lst = undefined

main = print (norm [1.1, 2.2, 3.3])

Ex 5. Implement the function decimate that skips every other element of a list.

decimate :: [a] -> [a]
decimate = undefined

-- should print [1, 3, 5]
main = print (decimate [1, 2, 3, 4, 5])

Ex 6. Implement a function that takes a pair of lists and returns a list of pairs. For instance ([1, 2, 3, 4], [1, 4, 9]) should produce [(1, 1), (2, 4), (3, 9)]. Notice that the longer of the two lists is truncated if necessary. Use nested patterns.

zipLst :: ([a], [b]) -> [(a, b)]
zipLst = undefined

main = print $ zipLst ([1, 2, 3, 4], "Hello")
comments powered by Disqus