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