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