Courses/CS 332F/Fall 2009

From CSWiki

Contents 1 Week 1 (September 29) 2 Week 2 (October 6) 3 Week 3 (October 13) 4 Week 4 (October 20) 5 Week 5 (October 27) First midterm 5.1 1. Problem 6 (longest words) from Basic Haskell Exercises. 5.2 2. Problem 13 (adjPairs) from Haskell -- Exercises. 5.3 3. Multiway trees are defined in 99 Haskell problems: Multiway trees. 5.4 Scores 6 Week 6 (November 3) 6.1 Anonymous (lambda) functions 6.2 Partial function application and currying 6.3 Sections 6.4 As-patterns. (You can skip this section.) 6.5 Code reuse through composition: composition 6.6 Tips for writing readable code 6.7 Exercises 6.8 List comprehensions 6.9 List comprehension exercises 7 Week 7 (November 10) 7.1 MapReduce in Haskell 8 Week 8 (November 17) Second midterm 9 Week 9 (November 24) Second midterm 9.1 Infinite Lists 10 Week 10 (December 1) 10.1 Infinite lists

Meeting times and place

Tuesdays: ET 210. 9:50AM - 1:10PM.

Grades

Two midterms and a final, all equal value.

Resources

Textbook: Real world Haskell

Code from the book: Examples.zip

Haskell Platform. Download and install.

Prelude (the standard library).

Basic libraries index

Haskell wiki

GHC User's Guide

Haskell search engines: Hoogle and Hayoo

Haskell mailing lists

haskell@haskell.org (Home page)

Announcements, discussion openers, technical questions.

haskell@haskell.org is intended to be a low-bandwidth list, to which it is safe to subscribe without risking being buried in email. If a thread becomes longer than a handful of messages, please transfer to haskell-cafe@haskell.org.

haskell-cafe@haskell.org (Home page)

General Haskell questions; extended discussions.

In Simon Peyton Jones' words: "forum in which it's acceptable to ask anything, no matter how naive, and get polite replies."

beginners@haskell.org (Home page)

Beginner-level, i.e., elementary, Haskell questions and discussions.

In the words of Benjamin L. Russell (the one who first suggested creating the mailing list and the current administrator): "Here, there is no such thing as a 'stupid question.'"

[edit] Week 1 (September 29)

video

Read from the start of the book through Chapter 2 and do all the exercises.

  9:50 - 10:30: Why functional programming? Why Haskell?

10:40 - 11:40: 1. Getting started. Note that before Rational numbers work you have to load Data.Ratio.

Prelude> :module Data.Ratio

On the lab computers, the Path for runghc is not set up. To run the last example, instead of

$ runghc WC < quux.txt

enter

$ D:\CSProg\ghc-6.10.3\bin\runghc WC < quux.txt

11:50 -   1:10: 2. Types and functions. The concepts and notation in this chapter are very important. They serve as the foundation for the rest of course and the rest of the book.

This was one attempt to find the next-to-last element of a list.

nextToLast xs = if (length xs) >= 2 then ... else length xs

Assume ... is something like

head (tail (reverse xs))

or

head (drop (length xs -2) xs)

what's wrong with this solution? It has nothing to do with the if-part, either of which is fine.

[edit] Week 2 (October 6)

video

Chapter 3. User-defined types. Like a class without methods in Java or a struct in C/C++—or a record in Pascal. This chapter has a lot of somewhat tedious details. The actual content/meaning of these ways of dealing with types is not that different from what you are already used to. But it may look different. For now, read the chapter, try the examples, and ask questions if you are confused. Don't expect to remember it all. You can always come back and look at it later when you want to use it.

Make sure you understand the Pattern Matching section. It's a very nice way of writing code. Essentially it lets you write code for different conditions without having to write a switch or if statement to distinguish among the conditions. it also allows you to bind local variables to the parts of a structure that you want to access. It's a convenient and powerful programming feature.

Back to data declarations. The two forms declare the same data type. The "record" form simply allow you to declare accessor functions as well.

The first paragraph of Parametrized Types introduces the built-in types Maybe and Just. As it says, they are used when a value may not exist but one still must return something. Don't worry too much about them now.

What is important about Parameterized Types is that it is possible to use "type variables." The definition of List will be more familiar.

data List a = Cons a (List a)
             | Nil
              deriving (Show)

This says that a list is either an element stuck in front of a list of elements of the same type or Nil, which represents the empty list. This is like Java generics in which Lists are also parametrized. As long as all elements of the list have the same type, the actual types of the list elements don't matter when all you are thinking about is the list structure. In this case, the type variable "a" is used to refer to the type of the list elements whatever they are.

Be sure to do the two exercises at the end of this section.

Look at the Reporting errors section to see a better way to handle the problem we ran into last week when taking the next-to-last element of a list that doesn't have 2 elements.

Do a representative selection of the exercises at the end of the chapter. There are 12 exercises, pick 6 that are not too similar. E.g., do all the even problems or all the odd problems.

[edit] Week 3 (October 13)

video

Chapter 4.

• You can skip the beginning of the chapter and start with the Infix functions section. Most of that and the sections on the list functions should be review.

• The new and important part of this chapter (for this week) is the section on the map, filter, and fold functions. It starts with the section How to think about loops and goes up to (but not including) the section on Anonymous (lambda) functions.

• It's not important to memorize the various list functions. The Data.List library is documented here.
• The first comment on exercise (1) suggests the following.

safeListFunc func [] = Nothing
safeListFunc func xs = Just (func xs)

safeHead = safeListFunc head
safeTail = safeListFunc tail
safeLast = safeListFunc last
safeInit = safeListFunc init

Does it work? Do you understand it?

Here's a definition of safe-minimum. It uses recursion and makes the less-than test on the way out of the recursion to illustrate how Maybe a must be unwrapped.

-- If the list is empty, there is no minimum.
safeMin [] = Nothing 
-- If the list is not empty, the answer is Just x, where x is the smallest number in the list.
safeMin [x] = Just x
safeMin (x:xs) = smallerOf x (safeMin xs)

We have to define

smallerOf :: (Ord a) => a -> (Maybe a) -> (Maybe a)

smallerOf x Nothing = Just x
smallerOf x (Just y) 
 | x < y     = Just x
 | otherwise = Just y

This is where the Maybe data type is useful. It is used when one isn't sure that a function will be able to handle its input. Assume the function f is

f :: a -> b

Instead of that define

safe_f :: a -> Maybe b

• When f would return a result x, safe_f will return Just x
• When f would generate an error, safe_f will return Nothing.

A problem with Maybe is that you have to unwrap the results.

head' xs = unwrap (safeHead xs)

unwrap (Just x) = x

But then you will get an error with head' []. What Maybe offers is the chance to take your own recovery action.

• You can skip exercises 2, 3, and 4 in the first set of exercises. They use the material before Infix Functions.
• You can skip over the Adler32 example.

All the preceding should be review—more or less. You should know how to write recursive list functions from CS 203. The next part of the chapter is the new part.

Make sure you understand the fold, map, and filter functions — and their types. Be sure you can explain why the types are as they are. In particular, the first argument is a function, which itself has a type. For example, the type of filter is

filter :: (a -> Bool) -> [a] -> [a]

The first argument to filter is a function that maps elements of type a to a Boolean. The second argument is a list of elements of type a. The filter function also returns a list of elements of type a. In particular it returns the elements from the original list that the function mapped to true

You can stop when you get to the Anonymous (lambda) functions section. But do the group of exercises just before that.

[edit] Week 4 (October 20)

Video

Exercises for review. (There may be a number of duplicates.)

• From Basic Haskell Exercises 1, 2, 4, 6
• From Haskell exercises 1, 2, 5, 6, 7, 10, 11, 12, 13, 14.
• 99 Haskell Exercises. The answers are given, but try to write them yourself first. These problem were initially created for Prolog. Then they were converted to Lisp problems. Now they are Haskell problems. You will see references to Prolog and Lisp. You can ignore them.
  • 1 - 10. Lists These are mostly problems you have already seen. Problems 8 and 9 may be new.
  • 11 - 20, Lists, continued. All.
  • Lists again. 21, 22, and 28.
  • Binary Trees. 56.
  • Binary Trees, continued. 61, 61A, 62, 62B.

[edit] Week 5 (October 27) First midterm

Video The problems will be similar to the ones reviewed the previous week.

CS 332F Midterm

Each problem is worth 33 points. One point is free.

Open book; open notes; open internet. No helping each other.

Please submit three files: one file for each question. There is a 5 point penalty per minute for files turned in after 1:10

[edit] 1. Problem 6 (longest words) from Basic Haskell Exercises.

Here are a number of answers. All use the words function to turn a string into a list of words.

This first version is the most elegant. It filters for the words that are as long as the longest word.

longestWords1 string = lw1 (words string)
lw1 xs = 
  filter isLongest xs 
  where isLongest x = length x == maximum (map length xs)
    

This second version is more brute force. But it takes only one pass through the list. It accumulates the answer as it goes. It does that by calling a helping function lw2 and passing the empty list as the start of the answer.

longestWords2 string = lw2 (words string) []

-- If the list of words is empty, ans is the answer.
lw2 [] ans = ans
-- If there is nothing in ans yet, put the first word of the list into it.
lw2 (word:words) [] = lw2 words [word]

lw2 (word:words) (a:as) 
  -- if the current word is longer than the words in ans, start ans again with the current word
  | (length word) > (length a)  = lw2 words [word]
  -- if the current word is as long as the words in ans, add it to ans
  | (length word) == (length a) = lw2 words (word:a:as)
  -- if the current word is shorter than the words in ans, skip it
  | otherwise = lw2 words (a:as)

This version uses the same approach, but it uses foldr to run through the list.

longestWords3 xs = foldr nextWord [] (words xs)

-- nextWord takes the current word and the list of longest words found so far
-- and returns the updated list of longest words.
nextWord word [] = [word]
nextWord word (w:words)
  | (length word) > (length w) = [word]
  | (length word) == (length w) = word:w:words
  | otherwise = w:words

On the other hand, this is a standard answer.

longest string = wordsOfLength (maxLength (words string)) (words string)
  
maxLength [] = 0
maxLength xs = maximum (map length xs)
         
wordsOfLength len [] = []
wordsOfLength len (x:xs) 
  | length x == len = x:(wordsOfLength len xs)
  | otherwise     = wordsOfLength len xs

Here's the foldr version.

longest string = wordsOfLength (maxLength (words string)) (words string)
 
maxLength [] = 0
maxLength xs = maximum (map length xs)

wordsOfLength maxLength words = 
  foldr nextWord [] words 
  where nextWord word ans
         | length word == maxLength = word:ans
         | otherwise = ans

Here's a clunky version. It uses an accumulator when there is no need for an accumulator.

longest string = wordsOfLength (maxLength (words string)) (words string) []
  
maxLength [] = 0
maxLength xs = maximum (map length xs)
         
wordsOfLength len [] ans = ans
wordsOfLength len (x:xs) ans
  | length x == len = wordsOfLength len xs (x:ans)
  | otherwise       = wordsOfLength len xs ans

Here's an even clunkier version. It use if/then/else instead of multiple clauses and guards.

wordsOfLength len xs ans = 
  if (xs == []) then ans
  else if (length (head xs) == len) then wordsOfLength len (tail xs) ((head xs):ans)
  else wordsOfLength len (tail xs) ans

The last version could be prettied up a bit by using if/then/else as a function that returns a value (like  ? : in Java) rather than as a control structure.

wordsOfLength len [] ans = ans
wordsOfLength len (x:xs) ans = 
  wordsOfLength len xs (if (length x == len) then (x:ans) else ans)

[edit] 2. Problem 13 (adjPairs) from Haskell -- Exercises.

Note that every element in the input list (except for the first and last elements) appears twice in the output: first as the second element of a pair and then as a first element.

Here's a simple answer.

adjPairs xs = zip xs (tail xs)

[edit] 3. Multiway trees are defined in 99 Haskell problems: Multiway trees.

Write a function that returns the height of a multiway tree. (The height of a leaf, i.e., a tree with no children, is 1.)

Ten points extra credit if you do this problem without using recursion. You may use the built-in function maximum, which finds the maximum element in a list. Be careful, though, maximum will throw an exception if given the empty list.

     > maximum [3, 2, 8, 6, 3, 9, 6, 0, 4]
     9

but

     > maximum []
     ** Exception: Prelude.maximum: empty list

Even though one might argue that it is recursive, this answer got the extra 10 point credit.

-- The height of a leaf is 1
height1 (Node _ []) = 1
-- The height of a tree is 1 more than the height of the tallest child.
height1 (Node _ ts) = (maximum (map height1 ts)) + 1

For a fully non-recursive answer, you need a function that operates on Trees the way foldr operates on lists.

reduceTree upFunction (Node n trees) = 
              upFunction n (map (reduceTree upFunction) trees)

The upfunction takes the values computed on the children along with n, the value at the node, and computes the value of the subtree consisting of that node value and the children.

Note that it's not necessary to terminate the recursion of reduceTree since map applied to an empty list (of children) will just return an empty list.

Given this definition, height can be defined as follows.

height2 tree = reduceTree upOneLevel tree

upOneLevel _ []              = 1
upOneLevel _ childrenHeights = (maximum childrenHeights) + 1

Can you see how reduceTree factors out all the recursion leaving you free to define upOneLevel as the function on the value at the node and the values generated on the children?

maxNode tree = reduceTree upOneLevel' tree

upOneLevel' n []           = n
upOneLevel' n childrenMaxs = max n (maximum childrenMaxs)

[edit] Scores

A  : 110, 110, 110, 110, 110, 107

A–: 92

C  : 77, 77, 77, 72, 67, 67, 64, 63, 62, 59, 59, 51

D  : 44, 41, 35, 34, 31

F  : 11, 1, 1

[edit] Week 6 (November 3)

Video

Chapter 3. Functional Programming

Read the following sections.

[edit] Anonymous (lambda) functions

*Main> let squares xs = map (\ x -> x*x) xs
*Main> squares [1 .. 9]
[1,4,9,16,25,36,49,64,81]

[edit] Partial function application and currying

Let's read this section.

*Main> :m Data.Char
Prelude Data.Char> map (dropWhile isSpace) [" a","f","   e"]
["a","f","e"]
Prelude Data.Char> :t isSpace
isSpace :: Char -> Bool
Prelude Data.Char> let dropLeadingSpaces = dropWhile isSpace
Prelude Data.Char> map dropLeadingSpaces [" a","f","   e"]
["a","f","e"]

[edit] Sections

[edit] As-patterns. (You can skip this section.)

[edit] Code reuse through composition: composition

Function composition

(.) :: (b -> c) -> (a -> b) -> (a -> c)

Define tails.

tails [] = []
tails (x:xs) = xs:(tails xs)

Lets assume we want a function

suffixes xs = init (tails xs)

This means we first apply tails and then init. We can use composition (.) to express that.

suffixes' = init . tails

From the texxt.

ghci> let capCount = length . filter (isUpper . head) . words
ghci> capCount "Hello there, Mom!"
2

[edit] Tips for writing readable code

Stop at "Space leaks and strict evaluation (seq)."

[edit] Exercises

Unfortunately, no exercises are given for any of these sections. Try doing the problems on last week's midterm using these features. A traditional place where lambda functions are used is in higher order functions like map, filter, foldr, foldl, reduce, etc. For example, can you use a lambda function and composition to complete this version of the solution to problem 1?

longestWordsIn string = 
                   -- where pa is a partial application
  let maxLength =  (maximum . pa . words) string
  in
                   -- sect is a section and f is a library function
  filter (\word -> (sect . f) word) (words string)

Having done that, what happens if you replace the lambda function with just the composition in its body?

longestWordsIn' string = 
                   -- where pa is a partial application
  let maxLength =  (maximum . pa . words) string
  in
          -- sect is a section and f is a library function
  filter (sect . f) (words string)

[edit] List comprehensions

pp 38-41 of Graham Hutton's Programming in Hankell.

(You can make it a bit more readable with the controls in the upper left corner.)

List comprehension can be used to define some of the higher order functions. Define filter' and map' as follows.

filter' p xs = [ x | x <- xs, p x] 

map' f xs = [ f x | x <- xs]
-- Note that it's possible to apply a function to x after 
-- it is selected and has passed all its conditions.

Load those definitions and execute the following.

Main> filter' (> 5) (map' (*2) [1 .. 5])
[6,8,10]

Or more directly:

Main> [ x | x <- [ y * 2 | y <- [1 .. 5]], x > 5] 
[6,8,10]

[edit] List comprehension exercises

(a) Exercises 1, 3, and 4 on page 46.

(b) Use list comprehension to write yet another solution to the longest words problem.

[edit] Week 7 (November 10)

video

[edit] MapReduce in Haskell

[edit] Week 8 (November 17) Second midterm

Video

Will cover everything up through MapReduce in Haskell.

[edit] Week 9 (November 24) Second midterm

Video

Will cover everything up through MapReduce in Haskell.

[edit] Infinite Lists

Get a head-start on next week. Infinite lists are a new way of thinking about certain forms of computing. Like many features of Haskell, it may take a while to get used to them. We will have only one week on infinite lists, but the topic will be on the final. To be sure you understand them, do the readings listed. Some of the readings have exercises, which you should do also. If you read the material in advance, we can talk about your questions next week.

[edit] Week 10 (December 1)

[ Video]

[edit] Infinite lists

Readings. (The order is not meaningful.)

• Infinite list tricks in Haskell
• "Infinite" Data Structures
• Sieve of Eratosthenes (Haskell)
• Infinite lists as another form of recursion