4/10/20081CSE 3302 Programming LanguagesFunctional Programming Language: Chengkai LiSpring 2008Haskell (cont’d)Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20081Grading• Homework (HW): 25%. (HW1, HW2, HW3, HW4, HW5)• Machine Problems (MP): 20%. (MP1, MP2)• Essays (ES): 10%.• Midterm exam: 20%. • Final exam: 25%.•Bonus points:5%Based on class participation•Bonus points:5%.Based on class participation. some additional bonus points (in MP2, HW5)Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20082Letter Grades• curve‐based• The cutoffs for letter grades are based on your performance.• Bonus point: can only increase your gradeExample: cutoff for A: 88.5your raw score: 86bonus points: 3your grade: B ‐> A (86+3>88.5)Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20083What’s ahead• HW4: due by April 21st• HW5: due by May 2nd• Essay: have you started yet? (due at May 1st)Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20084Grades on WebCTLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20085Foldl and Foldrfoldl :: (a -> b -> a) -> a -> [b] -> afoldl f z [] = zfoldl f z (x:xs) = foldl f (f z x) xsfoldr :: (a -> b -> b) -> b -> [a] -> bfoldr f z [] = zfoldr f z (x:xs) = f x (foldr f z xs)Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200864/10/20082Foldr: ⊕ is right-associativeFoldl: ⊕ is left-associativeLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20087foldr (-) 1 [2,3,4]foldl (-) 1 [2,3,4](section 3.3.2 in the tutorial)foldr ⊕ v [x0,x1, …, xn] = x0 ⊕ (x1 ⊕ (…(xn ⊕ v)…))Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20088foldl ⊕ v [x0,x1, …, xn] = (…((v ⊕ x0) ⊕ x1)…) ⊕ xnLambda ExpressionsA function can be constructed without giving it a name by using a lambda expression.\x -> x+1The nameless function that takes a number x and returns the result x+1.Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 20089Why Are Lambda's Useful?Lambda expressions can be used to give a formal meaning to functions defined using currying.For example:add x y = x+yadd = \x -> (\y -> x+y)meansLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200810Another examplecompose f g x = f (g x)meansLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200811compose f g x = f (g x)compose f g = \x -> f (g x) Exercises1. Write a recursive function sum n that returns 1 + 2 + …. + nLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008124/10/20083Exercises2. Write a recursive function genlist n that returns [ 1, 2, …, n ].Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200813Exercises2. (cont.) Check to make sure n>0, otherwise return empty list.Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200814Exercises3.Check if an element is a member of a list.Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200815Exercises4.Implement ++Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200816Exercises4. (cont.) Merge two lists and return a list with elements sortedLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200817Exercises5. A triple (x,y,z) of positive integers is pythagorean ifx^2+y^2=z^2. Using list comprehension to define a function pyths::Int‐>[(Int, Int, Int)] that returns the list of all pythagorean triples whose components are at most a given limit. For example:p>pyths 10[(3,4,5), (4,3,5), (6,8,10), (8,6,10)]Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 2008184/10/20084Exercises5. (cont.) Make sure x <= y <= zLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200819Exercises6. Define list comprehension [ f x | x <- xs, p x] using map and filter.Lecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li, 200820Exercises7. Define map f and filter p using foldrLecture 20 – Functional Programming, Spring 2008CSE3302 Programming Languages, UT‐Arlington ©Chengkai Li,
View Full Document