CSC302 2006S, Class 36: Haskell (3): Infinite Lists
Admin:
* Sick child = No reading responses today. Perhaps later.
* Confirmation of topics.
Monday: Peter, Mark, Dimitar: Ruby Basics
Wednesday: Michael, Bradley, David: Ruby Advanced
Friday: Angeline, Alex, and Davis: FP
Overview:
* Lazy lists.
* Listing primes.
Haskell:
* Lazy language - Don't evaluate things unless needed
* Purely functional - No side effects, I/O is hard, randomness is PITA
* Typeful - Type checking that infers types cleverly; Permits programmers to define their own types, including polymorphic types
* Pattern-based function definitions
Goal: Sequence of operations for infinite lists
* Make a list of 1's
* Select the first n elements of a list
* Built-in operation 'take'
* Define our own firstn
* Make a list of x, for all x
* Make a list of whole numbers
* Filter out selected elements
* Primes
/Goal: Create the infinite list of 1's/
(define list-of-ones
(lambda ()
(cons 1 (list-of-ones))))
vs.
(define ones (cons 1 ones))
Not a good idea in Scheme
ones = (1:ones)
Repeating an arbirary value
lotsa x = x : (lotsa x)
What is the type of lotsa?
? Char -> [Char] NO
? Polymorphic: for all T , T -> [T]
silly i = (i+1) : (silly i)
Result of (silly 1)?
(silly 1) => (1+1) : (silly 1)
=> 2 : (silly 1)
=> 2 : ((1+1) : (silly 1))
=> 2 : (2 : (silly 1))
* Infinite list of 2's
Result of (silly 0.5)?
* Infinite list of 1.5's
Type of silly?
* "Either integer or real" -> List of same type
* How do we represent that in Haskell? Let's see
How do we define the natural numbers? 0, 1, 2, ...
* In general?
* 0 is a natural numver
* If n is a natural number, so is n+1
* In Haskell, building a list of natural numbers
0, 0+1, 0+1+1, 0+1+1+1
; Generate natural numbers starting with n
kernel n = n : (kernel (n+1))
kernel 5 => 5 : (kernel (5+1))
=> 5 : ((5+1) : (kernel (5+1+1)))
=> 5 : (6 : (kernel (6+1))))
How would we write a function, select pred lst
that selects all values that match pred from lst?
select pred [] = []
select pred (x:xs) = if (pred x) (x : (select pred xs)) (select pred xs)
Problem: Start with the list of whole numbers starting with 2
Repeatedly: Keep the first remaining value in the list and remove all multiple
primes = primeskernel (kernel 2)
; Given a list of candidate primes, determien all primes
primeskernel (p:xs) = p : (remove (multiple p) xs)
; is q a multiple of p?
multiple p q = (mod q p) == 0