CSC302 2006S, Class 35: Haskell (2): Types, Infinite Lists

Admin:
* Topics?  Dates?
* Read Sections 1 and 2 of Conception, Evolution, and Application of Functional Programming Languages
* 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 Typeful/

* Haskell pays attention to types
* Static type checking
* Rich type system, including polymorphic types
* Permits user-defined types

data NameOfType = StructureOfInstanceOfType0 | StructureOfInstanceOfType1 | ...
Structure has the form  NameOfOfConstructor type-of-param type-of-param

data ListOfIntegers = EmptyLOI | ICons Integer ListOfIntegers

No parameters: Can use for enumerated types

data Days = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday

* Order of the parameters is significant
* When you apply a "Constructor" to the appropriate parameters, you get a value in the appropriate type
* We work with that value using patterns

length :: ListOfIntegers -> Integer
length EmptyLOI = 0
length (ICons i loi) = 1 + (length loi)

icar :: ListOfIntegers -> Integer
icar (ICons i is) = i
icdr :: ListOfIntegers -> ListOfIntegers
icdr (ICons i is) = is

nth :: Integer -> ListOfIntegers -> Integer
nth 0 loi = car loi
nth n loi = nth (n-1) (cdr loi)

Useful for data structure definitions

Stack
* Push, Pop, IsEmpty, Top, New
* Constructors: New, Push
* "Functions": pop, isEmpty, top

data Stack = EmptyStack | Push Integer Stack
pop (Push i s) = s
top (Push i s) = i
isEmpty EmptyStack = True
isEmpty (Push i s) = False

Haskell's combination of patterns and data-definition mechanisms permit specs to act as code