Held: Wednesday, April 26, 2006
Summary:
Today we continue our exploration of Haskell by considering data types
and an example of using infinite lists.
Related Pages:
Due
Assignments
- Read Sections 1 (Evolution) and 2 (Distinguishing Features) of Hudak's Conception, Evolution, and Application of Functional Programming Languages.
Notes:
- I will do my best to honor "Day of Silence" requests.
- EC for attending Cunningham's talk today.
- EC for attending convo tomorrow.
Overview:
- Types in Haskell.
- Patterns and Data Structures.
- Lazy Evaluation and the Sieve of Eratothenes.
- Haskell is a typeful language. Types play a large role
in the language.
- Programmers are encouraged to define their own types.
- Haskell has a rich type inference and checking system.
- A type declaration gives a type name and a set of
type constructors which tell how to build objects of that type.
- Constructors may take arguments (e.g., Cons would take two arguments).
- Constructors may take no arguments (in which case they act like
basic values).
- Often, there are multiple constructors for a type. These can be separated
with vertical bars.
- For example, an enumerated type would be written something like
data Days = Mon | Tue | Wed | Thu | Fri | Sat | Sun
data Gender = Male | Female | Unspecified
- In a record type, we would also give arguments, as in
data Person = Per String Int Gender
- In this instance,
Per is the constructor, which takes
three arguments:
- A string, perhaps representing the person's name
- An integer, perhaps representing the person's age
- A gender
- Haskell also allows recursive types, such as
data IntList = ILnil | ILcons Int IntList
- More importantly, Haskell allows you to define polymorphic types (what
I've sometimes called metatypes) that take type variables as arguments.
For example,
data List a = Nil | Cons a (List a)
- Patterns are very useful for describing the key actions related to
data structures.
- For example, in the original defintion of LISP,
variations of the following two equations appear in the report to define
Cons, car, and cdr.
car (Cons x xs) = x
cdr (Cons x xs) = xs
- As you read the data-structures literature, you'll soon realize that
many data structures are
defined
by a series of equations like this.
- For example, many people define stacks by five operations:
Push, NewStack, top,
pop and empty.
- We can do the same in Haskell
data Stack a = NewStack | Push a (Stack a)
pop :: Stack a -> Stack a
pop (Push item stack) = stack
pop NewStack = error
top :: Stack a -> a
top (Push item stack) = item
top NewStack = error
empty :: Stack a -> Bool
empty NewStack = True
empty (Push item stack) = False
- Of course, this does seem to require that we have an error value.
- You can also leave out the error equations, and Haskell will report
an error when it encounters these patterns.
- Note that, in both cases, the specification of the meaning of an
operation becomes the definition of the operation.
- Laziness provides a fun way to explore the legendary sieve of Eratothenes.
- E suggested that we can identify the primes as follows:
- Build a list of integers, starting at 2.
- Repeatedly grab the first element of the list (which is prime)
- Remove all multiples of that element from the remainder of the list
- Let's see how we'd code that in Haskell.
;
Check with Bobby