From CSULA CS Wiki
Jump to: navigation, search


June 23. Week 1: Introduction to functional programming and HUGS


See Grading for grading policy.


Question, comment, and discussion page.

If you have questions or comments, please enter them on the discussion page. Click the discussion tab above.

Thompson, Chapters 1 and 2.

Notes for Week 1.

Hugs irritation note. You can't make new declarations at the Hugs prompt. That is, you can't type

size :: Int
size = 12 + 13

into Hugs as in the book. (You can, but you get an error message.)

 Hugs only evaluates expressions and prints the result. 

The solution is to make all your definitions in a file and reload the file whenever necessary (using ":reload").

Homework 1

June 30. Week 2: Types and definitions

Thompson, Chapter 3.

Convenience and details

Note that if you do not declare a type for a function, the type will be the most general that can be determined from the function definition. For example,

 >    sq :: Int -> Int

 >    sq n = n * n

Will define sq as a function from Int to Int. If you try to execute: sq 5.4 you will get an error message. But if you define</P>

 >    sq0 n = n * n

sq0 will be defined as a function from any Num(erical) type to itself. If you try to execute: sq0 5.4 you will get the correct answer. To check this, look up these functions using the Browse > Name menu selection.</P>


Also note that to load Chapter3.hs or Chapter3.lhs you must split the single import statement and modify it to be:

>    import Prelude hiding (max)
>    import Char hiding (toUpper, isDigit)

Apparently the Char library was extracted from the Prelude.

Error bait

I can't get 4 'max' 5 to work. Can you?  The HUGS Error messages page points out that it should be 4 `max` 5, using the backquote, the key to the left of the '1' key.

Key idea

A reasonable way to think of what you are doing when associating values with identifiers (i.e., when writing an equation) is that you are both declaring the identifier and giving it a value.  So:

>    five :: Int
>    five = 5

declares the identifier "five" to be of type Integer and gives it a value of 5.  When you write

>    square :: Int -> Int
>    square n = n * n

you are declaring square to be of the type Int -> Int and giving it as a value the function that converts n into n * n. 

In other words, in functional programming, what one would normally think of as variables and what one would normally think of as functions are on the same level.  They are values of some type and may be named by some identifier.

Homework 2

  • Due at the end of the lab.
    • 3.4. You don't have to draw the picture.
    • 3.7
    • 3.8
  • Due Tuesday midnight.
    • 3.12 (Note that toUpper is almost but not quite the answer; try toUpper 'A' to see why it is not the correct answer. The problem is to find a way of determining when the argument is a "small letter" as the problems specifies. Do not use relational functions such as < or >. Look at the functions defined in Prelude.hs and Char.hs. These are available at C:\Program Files\Hugs98\libraries\Hugs.)
    • 3.13
  • Due Thursday midnight.
    • 3.17
    • 3.19
    • Define ~> (the tilde (~) symbol followed by the greater-than (>) symbol) to be an operator for logical implication. For example
 > False ~> False
 > False ~> True

 > True ~> False
 > True ~> True 

July 7. Week 3: Recursion, tuples, and lists


Thompson, Chapters 4 - 7 (selected parts).

Most of the material in these chapters is about how to do in Haskell what you (should) already know how to do in Java. So we won't spend too much time on the details. But there is a fair amount of notation to get used to. So don't take it too nonchalantly.

This week covers the greatest number of pages at one time. But don't forget, the book is written for someone with no programming background.

Think of it as a test to see if you are prepared to do upper division CS work! Did you learn what you should have learned in CS 201, 202, and 203?

What's important about this course are the concepts.

  • It doesn't matter if you don't remember the details of the notation. (I often don't.)
  • It does matter that you be able to look up those details and use them when you need them.

Chapter 4. Recursion.

Most of sections 4.1 - 4.3 should be review. Look at the examples on pp 62 - 64 to be sure. The examples should be conceptually easy. Do you understand the code?

Don't worry about the difference between recursion and primitive recursion (section 4.4). There is a formal distinction, but all that matters for us is that you know how to write recursive functions, which you should have learned in an earlier class. So this should be review. Section 4.5 should also be review.

Chapter 5. Tuples and lists.

A tuple is like a class without code or like a struct in C++. It is a collection of values, where each collection has the same structure. See page 72 - 76. Look especially at example 3 on page 75 for a clever way to define Fibonacci numbers by always passing pairs of numbers.

A list in Haskell consists of any number of elements but all of the same type, like a generic list in Java 1.5. Read pp 78 & 79. Do exercises 5.5 - 5.7 on your own. (But do them. Really try them out.)

Section 5.5 about list comprehension is new. Read pp 79 - 81. The notation

x <- list

means x is an element of list. Think of "<-" as "is an element of." It is not a left-pointing arrow. Look at all the examples on pp 80 & 81. Do you understand example 7?

Don't worry about 5.6 and 5.7. (We'll come back to 5.7 later.) Section 5.8 contains the built-in list functions. Section 5.9 describes the String type. A String is a list of Char elements as usual.

Chapter 6

More list examples. Most of it should be familiar. Read lightly.

Section 6.3 on Local Definitions describes where, which is quite useful. Look this over more carefully (pp 103 - 107).

Chapter 7. Patterns, guards, list notation, and writing list function.

Section 7.1. Patterns and guards provide a nice way to define functions conditionally.

Section 7.2. More list notation. x:xs is the list whose first element is x and whose remaining elements are the xs. Note that

4:3:2:1:[] = [4, 3, 2, 1]

A nice feature of Haskell and similar languages is that you can create structures by just writing them down. Just by writing down 3:[4, 5] I've created a list containing 3, 4, and 5.

Look at the definitions of head, tail, null at the bottom of p 117. Try

> head []

The case statement (as in other languages) (p. 118) offers another way to define functions conditionally.

Patterns and guards are written to the left of the = sign. A case construct is to the right.

Sections 7.3 - 7.5. Defining list functions recursively. Be sure that you understand the definition of (++) on page 121 and 122. This is example 2. The other examples are also worth spending some time with. For example, do you understand the definition of insertion sort (example 6)? Read through the examples on pp 126 & 127. Don't bother with the rest of the chapter.

Homework 3

Lab 3

  • 4.9. To test this function you may use the function f n = round(100*(sin n)^2).
    The sin function is built in. It is defined to expect a radian argument. Giving it an integer argument will produce somewhat arbitrary results between -1 and 1. Squaring the result makes them all non-negative. Multiplying by 100 stretches them out to the range 0 .. 100.

    To make this work you may have to take out the explicit declarations of maxFun and your test function f. Hugs will find the most general types that the definitions allow.

    Using list comprehension (from chapter 5) the first 12 values are as follows. (The new highs are in bold.)

> [round (100*(sin x)^2) | x <- [0 .. 11]]

Input: integers a and b
Output: greatest common divisor (gcd)
// Normally a > b.  But if b > a, a pass through the loop reverses them.
        while (b > 0)
             r = a mod b;
             a = b;
             b = r;
        end while
        return a;

  • 4.14. Use a recursive definition of isOdd and isEven; don't use `mod` or `rem`. You may use the definitions on pages 106 & 107 if you understand and can explain them.

Due Tuesday 7/11

  • 5.2.
  • 5.10. Try only possible divisors between 2 and (sqrt n). It's tricky to get the numeric types to come out right. The following works as a definition for divisors.
divisors :: Int -> [Int]
divisors n = [ x | x <- [2 .. floor (sqrt (fromInt n))], (n `mod` x ) == 0 ]
Note the use of fromInt to force the argument of sqrt to have been an Int. Since sqrt requires a Float or Double argument, without the fromInt the argument to divisors is apparently overloaded as both Int and Float/Double.

The following also works.

divisors :: Float -> [Float]
divisors n = [ x | x <- [2 .. sqrt n], ((floor n) `mod` (floor x)) == 0 ]
  • 5.11.
  • 7.6.

Due Thursday 7/13

  • 7.7.
  • 7.8.
  • 7.9.
  • 7.11.
  • 7.13.

July 14. Week 4: Polymorphism and higher order functions

(The following was posted on the Discussion page.)
  • Please re-read my page on values.
  • Ask yourself what you have contributed to the class so far. I have added a Class Contributions assignment to the CSNS system. I would like you to keep track of your contributions to the class—e.g., your entries on the discussion page, questions you ask in class, explanations you offer, homework problems you explain, etc.— and submit them to the system. You can submit the same assignment multiple times, so it is probably a good idea to submit a new version whenever you do something worth noting. The deadline is midnight July 27, the day before we have our midterm individual discussions.

Thompson, Sections 5.7 (p. 87 - 90) and 9.2 (p 155 - 161). You should be able to read 5.7 by yourself.

Do you understand the difference between polymorphism and overloading? It's explained in the last part of 5.7.

  • Polymorphism: If a type a has at least two subtypes a1, and a2, and if a function is defined on type a and is not re-defined on either of its two subtypes, that function is polymorphic. In this case we don't really care about the name of the function, just the function itself.
    • In an object-oriented context, think of a function like length(), which is defined on ArrayList<Object>. Since that same function applies to any ArrayList<AnyType>, it is polymorphic. The same code works on multiple types.
  • Overloading: If the same function name is used to define two distinct functions, that function name is overloaded. (Presumably we use the same name because we intend the two functions to mean the same thing.)
    • In an object-oriented context, if a function (named f) is defined on type a1 and is re-defined on type a2, (a1 and a2 need not be subtypes of a common parent type) then the function name f is overloaded. The function named area, which is computed differently depending on whether it is called on a circle or on a rectangle is overloaded. In reality there are two different functions. That is, the code is different since the formula for area is different in the two cases. In this case we may (but need not) have a superclass for both Circle and Rectangle called Figure. It might have an abstract function named area. But it is not required that there be a superclass to have an overloaded function name.

Homework 4

  • Lab
    • 5.18 (It's trivial to get the answer by using :type. Be sure you can explain it.)
    • 9.2.
  • Tuesday
    • 9.3, 9.6, 9.7.
  • Thursday
    • 9.8, 9.9, 9.10.

July 21. Week 5: Folding and primitive recursion

Thompson, Section 9.3. (We are skipping Section 9.4.)

Errata. The definition of foldr1 on p 162 is different from that on p161. Calling them foldr1_def161 and foldr1_def162 they behave thus:

foldr1_def161 (++) ["a", "b", "c"] = "abc"
foldr1_def162 (++) ["a", "b", "c"] = "bca"


You can think of foldr as something like a for loop.

foldr <loop-body> <initialization> <list>

The foldr construct passes the elements of the <list> to the <loop-body> one at a time, right to left.

The <loop-body> processes the elements of the list and stores its intermediate results in the data structure which is passed to it as its second argument.

The initial value of that second argument is specified by <initialization>. It can be as complex a data structure as you want.

The <loop-body> returns as its value a modified version of its second argument. That result is then passed as the second argument to <loop-body> again along with the next element of the <list>.

In other words,

foldr f vars0 xs

is comparable to

-- Assume vars are declared outside the loop.
-- They are initialize at the beginning with vars0.
-- Then run through the xs.
for (vars = vars0; x in xs) { from right to left.
  vars = f(x, vars)
 -- The vars are available after the loop.   
 -- Construct the result by picking values from the vars.

vars is some data structure, e.g., a list, a tuple, a list of tuples, etc., which can be used for storing values.

filterFirst and filterLast using foldr

Here's a recursive definition for filterFirst, which should return a list that excludes the first element that fails to satisfy a predicate p.

filterFirst :: ( a -> Bool ) -> [a] -> [a] 
filterFirst p [] = [];
filterFirst p ( x:xs ) 
       | p x = x:( filterFirst p xs ) -- x satisfies p, so continue looking
                                      -- for an x that doesn't satisfy p.
       | otherwise = xs;              -- x doesn't satisfy p. Include all the rest of the xs.

Here's how you would use foldr to do the same computation but starting from the end of the list.

filterLast :: ( a -> Bool ) -> [a] -> [a] 
filterLast p xs = snd (foldr loopBody (False, []) xs)
  where loopBody x (True, ys)  = (True, x:ys); -- Have already found an x that doesn't satisfy p.
        loopBody x (False, ys)       
         | not (p x) = (True, ys)        -- x doesn't satisfy p. Set flag to True.
         | otherwise = (False, x:ys)     -- Keep looking.

The data structure used to keep track of the result is a pair (<Bool>, <List>). The <Bool> value tells you whether you have already encountered a list element that doesn't satisfy p. Initially it is False since we haven't encountered an element that doesn't satisfy p. The <List> is the list of all elements except the right-most one that doesn't satisfy p.

Note that filterLast uses snd to extract the actual list from the data structure that is used inside foldr.

Note also how we are using p in the definition of p0. That is p0 could not be defined as a separate function unless we wanted to fix p in advance. But we don't want to fix p; it is supposed to be an input parameter to filterLast.

Here's a version of filterFirst using foldr.

filterFirst p xs = snd (foldr p0 ([], []) xs)
 where p0 x (all, some)
       | not (p x) = (x:all, all)    -- x doesn't satisfy p. Make <some>
                                     -- everything except x, i.e., <all>.
       | otherwise = (x:all, x:some) -- x satisfies p. Include it in <some>.

The second argument to p0 is a pair (<all>, <some>) where <all> is the entire tail of the list encountered so far, and <some> is the entire tail of the list except the most recent element, if any, that doesn't satisfy p.

allEqual using foldr

Consider the following definition for allEqual using foldr.

allEqual :: [a] -> Bool

allEqual should return True if all the elements of its argument (a list) are equal. It should return False otherwise.

allEqual [] = True
allEqual (x0:xs) = fst(foldr eq (True, x0) xs) -- Start in state True.

eq x (True, x0)                 -- All the xs (from the right) have been equal to x0 so far.
  | x == x0 = (True, x0)        -- The current element is equal to x0. Stay in state True.
  | otherwise = (False, x0)     -- The current element is not equal to x0. Go to state False.
eq _ (False, x0) = (False, x0)  -- We previously encountered an unequal element. Stay in state False.

In this case, the second argument to eq (the data structure in which the result is accumulated) is a pair (State, Value).

  • State is either True or False depending on whether all the elements encountered so far have been equal.
  • <Value>, the second element of the pair, is the value to which all elements seen so far are equal. This is meaningful only if the first element of the pair is True.

You can copy and paste the following exxamples.

> allEqual [1, 2, 3] 
        where allEqual (x0:xs) = fst(foldr eq (True, x0) xs); 
              eq x (True, y) = if x == y then (True, x) else (False, x); 
              eq _ (False, x) = (False, x)
> allEqual [2, 2, 2] 
        where allEqual (x0:xs) = fst(foldr eq (True, x0) xs); 
              eq x (True, y) = if x == y then (True, x) else (False, x); 
              eq _ (False, x) = (False, x)

Homework 5

Please do these problems for next week. We will be meeting individually, but I'd like you to be able to talk about these problems—as well as earlier work.

Due at end of Lab

  • 9.11
  • 9.12

Due Tuesday midnight

  • 9.13 (Note that     init = rev . tail . rev     works, but I want you to use foldr at the top level.)
  • 9.14 (be able to explain why). Note that sing puts its argument into a list with no other elements. For example:
> sing 3 where sing x = [x]
  • 9.16 (just define filterFirst; don't worry about returnLoan). But be able to explain what your function does if all elements of the list have the property p.
> filterFirst greaterThan4 [2, 6, 1, 7] 
[2, 1, 7]

Due Thursday midnight

  • 9.17 (Define filterLast twice, once using filterFirst and once directly using foldr.)
  • 9.18 (redefine the functions in 9.7 using foldr or foldr1)

July 28. Week 6: Midterm meetings

Please sign up to see me individually. We will talk about the homework assigned last week, your overall homework submission and class contribution record, and any problems you want to discuss.
I recommend that you review the basis of grading as expressed in Professional and academic values. I will be asking you to evaluate yourself according to those guidelines.

Below the sign-up table, I've left in some comments I made after the meetings from the previous time this class was held. You are welcome to look at them.

  • Contributory values
    • Homeworks presented
    • Comments on discussion page
    • Contributions in class
  • Technical values
    • Intellectural honesty
    • Insight/creativity
    • Competence: able to do the assigned work
  • Interpersonal values
    • Paying attention in class
  Time   Name
10:00 Smbat Bagdassarian
10:15 Herbert Lee
10:30 Daniel Germann
10:45 Eugene Flock
11:00 Celia Torres
11:15 Emmanuel Sotelo
11:30 Zhi Yun Li
11:45 Shiusen Yao
12:00 Oleg Gnatovskiy
12:15 Carlo Marini
12:30 Tan Luong
12:45 Joan Kim
1:00 Bill Kunyiha
1:15 Neil Nguyen
1:30 Yuet-Chi Lee
1:45 Shabana Hoque
2:00 Cesar Duran
2:15 Sassja Ceballos
2:30 Edmond Kong
2:45 Cuong Tham
3:00 Hong Ngo
3:15 Nick Tolentino
3:30 Yoshi
3:45 Rubic Christian
4:00 Steven Martin
4:15 Muhammad Ashfaque
4:30 Kunhan Kim
4:45 Your name

If all the time slots are full and you haven't yet signed up, add another slot at the end.

Comments on meetings

A great many people wrote code like this for unzip.

unzip :: [(a, b)] -> ([a], [b])
unzip [] = ([],[])
unzip xs = (foldr (:) [] (map fst xs), foldr (:) [] (map snd xs))


foldr (:) [] xs ~> xs

Writing code that does nothing is not a good way to demonstrate that you know what you're doing.

Here is a nice recursive definition of unzip. It's not what the question was looking for, but it illustrates an interesting point.

unzip [] = ([], [])
unzip ((x,y):zs) = (x:xs, y:ys)
     where (xs, ys) = unzip zs

In this definition, we apply unzip to zs, the remainder of the list, to get (xs, ys) and then we use the two components of the result of the recursive call, xs, and ys, in the top level of the definition.

There were other examples of code that made no real sense. I saw, for example,

length [0 .. n]

when what was really intended was n+1.

Please don't submit code unless you understand how it works.

Aug 4. Week 7: Functions as values

Thompson sections 10.1 - 10.3.

A random number generator.

Function composition (.)

Note the definition of the function composition operator (.) (p. 169).

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

Note: the above is what you get when you ask for the type of (.) in Hugs. The letters are different from (but equivalent to) those shown in the book.

The function composition operator (.) takes two functions f and g and returns the function h which is their composition.

((.) f g) x = f (g x)

Note that the output of g and the input to f must be of the same type. In this case, type a. What is the type of (f . g)? It is the function that takes the input to g and produces the output of f, i.e., c -> b.

Be sure that you understand that the (.) operator takes functions as input and returns a funcction as an output. It doesn't apply those functions to any arguments. If there were a function compositions operator in Java it might look something like this.

public int f(int x) { … } -- Declare f
public int g(int y) { … } -- Declare g
> h = f . g
 -- Creates something like this
public int h(int z) {return f(g(z));}

In other words, (.) takes two methods, f and g, and returns a method h which when executed on input z returns f(g(z)). The key is that (.) returns the method h itself. It does not apply f and g to any input. Once you have h, it can be applied to something. Or h can be created on the fly as in the following.

> h 5 where h = f . g

Anonymous λ (lambda) functions, using \ for λ

Here's how to use a λ function to define unzip on last week's homework.

Here's a basic version using foldr.

unZip :: [(a, b)] -> ([a], [b])
unZip xs = foldr unz ([], []) xs 
              where unz (x,y) (xs,ys) = (x:xs, y:ys)

The λ function version is the same except that instead of defining unz explicitly, it is defined in place and anonymously.

unZip :: [(a, b)] -> ([a], [b])
unZip xs = foldr (\(x,y) (xs,ys) -> (x:xs, y:ys)) ([], []) xs

Note the use of -> instead of = .

So even though you can't define functions at the Hugs prompt, there are at least two ways of getting around that—at least for small functions. Assume isOdd is not defined. You can define it in a where clause on the input line.

> isOdd 1 where isOdd x = x `mod` 2 == 1
~> True

You can define it as a λ function.

>  (\x -> x `mod` 2 == 1) 1 
~> True

comp2 (pp 173 - 174)

The following illustrates the example comp2 (pp 173 - 174).

Hugs> comp2 (^2) (+) 3 4 where comp2 f g = \x y -> g (f x) (f y)

This is the same as the following.

Hugs> (comp2 (^2) (+)) 3 4 where comp2 f g = \x y -> g (f x) (f y)

The same effect could be achieved (more traditionally) as the following. (Note: no parentheses before the where. comp2 takes 4 arguments in this case.)

Hugs> comp2 (^2) (+) 3 4 where comp2 f g a b = (\x y -> g (f x) (f y)) a b

And even more traditionally as the following. (Note: no parentheses before the where. comp2 takes 4 arguments in this case.)

Hugs> comp2 (^2) (+) 3 4 where comp2 f g a b = g (f a) (f b )

Homework 7

Tuesday: 10.2. Try it for various functions f. The first question at the bottom asks what are the input and output types of id in the three cases in the question if id is Int -> Bool. The second question at the bottom asks for the type f must have to be applied to id.
10.3 (Demonstrate it on a list of functions.)

Thursday: 10.8, 10.9, 10.10. (The output to 10.10 is a function which is the derivative function of the input function. This is numerical differentiation, not symbolic differentiation.)

Aug 11. Week 8: Partial application

I'll be away this week. I'd like you to teach this week's material to yourself. Alla Lanovenko, one of our graduate students will be here monitoring the class, but she won't be here to teach, just to make sure you don't get into any trouble. This week covers only two sections of the book (10.4 & 10.5). Discuss the book and the material on the wiki page below.

You might divide the material into the sections the book suggests (and add the material below) and proceed as we did last week. Here is the random number generator.

As usual, if you have questions post them to the Discussion page. I'm not sure how good my Internet access will be. If I have access, I'll look at your questions. Also, if I have access, I'll be cheching my email.

Thompson sections 10.4 and 10.5.

The basic message of 10.4 is the paragraph on p 179 under the heading

How many arguments do functions have?

Every function in Haskell takes exactly one argument.

That's why, for example

(*) :: Int -> Int -> Int

really means

(*) :: Int -> (Int -> Int)

This means that (*) maps an Int into a function that maps an Int to an Int. For example

((*) 4) :: Int -> Int

In other words, ((*) 4) is a function that multiplies its single remaining argument by 4. Try

> ((*) 4) 5
~> 20


> :t ((*) 4) 
~> (4 *) :: Num a => a -> a 


> f 5 where f = (*) 4
~> 20

Another way to look at it is that

(*) 4 5 ~> ((*) 4) 5

More generally

f :: a1 -> a2 -> a3 … -> an-1 -> an 

is the same as

f :: a1 -> (a2 -> (a3 … -> (an-1 -> an) … ))

Another way to look at it is to see how functions are applied to their arguments one at a time.

f x1 x2 x3 … xn-1 xn = ( …(((f x1) x2) x3) … xn-1) xn

The function f is applied to its first argument x1 to generate a function which is applied to the second argument x2 to generate a function which is applied to the third argument, etc.

Using partial application to reduce a 3-argument function to 2 arguments for use with foldr

Here is a version of filterLast that uses partial application on the function passed to foldr to convert it from a 3-argument function to a 2-argument function.

Initially we define a function

loopBody :: (a -> Bool) -> a -> (Bool,[a]) -> (Bool,[a])

loopBody p x (True, ys) = (True, x:ys)
loopBody p x (False, ys)
 | p x = (False, x:ys)
 | otherwise = (True, ys)

which expects as its first argument the predicate p that filterLast uses to filter the list. This is the same as we did above except that p is passed explicitly to p0.

The problem is that we can't use p0 as the first argument to foldr because foldr expects a function that takes two arguments as its first argument.

To solve that problem we pass (p0 p) as the first argument to foldr. Using partial application (p0 p) converts p0 from a 3-argument function to a 2-argument function which has the predicate p built in. This new function is used by foldr in the same way as p0 was used in the previous definition of filterLast.

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

filterLast p xs = snd (foldr (loopBody p) (False, []) xs)

Contributed by Brian Smith.

Operator sections

An operator section is just a fancy name for partial application using an operator. The argument that is supplied is taken as either the first or second argument to the operator depending on which side of the operator it is written.

> (/4) 5
~> 1.25


> (4/) 5
~> 0.8

Note that (-4) doesn't work as an operation section because Haskel interprets -4 as an integer. Also, ((-)4) 5 is interpreted as (-) applied first to 4, giving a function that subtracts its argument from 4. When that function is applied to 5, i.e., 4 - 5, the result is -1. If (-4) were interpreted as an operator section, the 4 would be taken as the second argument instead of the first as in the division example of (/4) 5.


(/) 4 5 ~> 0.8 


(/4) 5 ~> 1.25

Homework 8

Tuesday: 10.12, 10.13, 10.14. (p.180 and 183)

Thursday: 10.15, 10.16, 10.17. (Note picToRep in 10.17 converts a picture into a representation.)

Aug 18. Week 9: Overloading and type classes and introduction to lazy evaluation

Thompson sections 12.1, 12.2, 17.1, 17.2 (bottom of page 343 only), 17.4 Example 1. List minimum (p 351), and 17.6 including Example 1 but not Example 2 (p 364). (We will return to 17.3 next week.)

Chapter 12. Overloading and type classes

Section 12.1 says that overloading (for functions like (==)) is necessary because

  1. comparing two Ints really is different from comparing two Bools since they may be represented completely differently, but
  2. we mean the same thing by (==) whether the arguments are two Ints or two Bools.

Therefore we need a way to declare that functions like (==) operate on some class of types, including Int and Bool. This class will be the class that supports the (==) function. In Hugs it is called Eq.

Section 12.2 talks about how to define such type classes.

class Eq a where
  (==) :: a -> a -> Bool

Eq is the class of types that support (==). The definition says that a is a member of Eq if it has (==) defined on it—and that Eq is the class of all types for which (==) is defined. Here's what Hugs says about the type of (==)

> :t (==)
(==) :: Eq a => a -> a -> Bool

This says that (==) takes two arguments, both of some type a. But it also says that the type a must be a member of the Eq type class, i.e., that it must have (==) defined on it.

One might imagine that all types support (==), but that's not true. As 12.2 points out, the type of functions from integers to integers (Int -> Int) does not have an (==) since in general it is undecidable whether two function definitions define the same function. (You will learn more about this in CS 486 if you take it, which you should.) Unfortunately, this means that you can't ask whether two variables that refer to functions contain the same pointer values!

> (+) == (+)
ERROR - Cannot infer instance
*** Instance   : Eq (a -> a)
*** Expression : (+) == (+)

In this case, Cannot infer instance means that Hugs is unable to infer that "(+)" belongs to a type that is an instance of Eq. It can't infer that "(+)" belongs to a type that is an instance of Eq because the type

> :t (+)
(+) :: Num a => a -> a -> a

is not a member of Eq.

Chapter 17. Lazy evaluation (introduction)

The important sections are 17.1, 17.4 (example), 17.6 (through example 1) and Infinite list generators at end of 17.6

The key to lazy evaluation is that unlike most programming languages Haskell evaluates expressions from outside in rather than from inside out. This is explained on the bottom of p 343.

Notice how iSort works on p 351. Only as much of the evaluation is done as necessary. Thus (head . iSort) is a reasonable way to find the minimum of a list—even though it looks like it is asking for the list to be sorted.

Homework 9

Tuesday: 12.1 - 12.3 (p 214)

Thursday: 17.22. (p 369) This should not require 17.3 although you may use list comprehension if you wish. Note the box in the middle of p 369 in case you aren't getting any answers. We will discuss the order of evaluation next week.

Aug 25. Week 10: Lazy evaluation and list comprehension (order of evaluation)

Thompson section 17.3 and 17.7.

List comprehension is not limited to just one generator along with some tests as we have been using it. It may include many qualifiers, i.e., generators and tests. Look at the examples on p 344. They illustrate how the qualifiers are evaluated depth first (from left to right).

Look at the examples on page 344 and the top of 345.

Then look at the messy expression at the bottom of p 345. This shows why the evaluation is depth first. The first level of evaluation is to generate one list for each element of the first generator. All those lists are concatenated to produce the final result. But each of those lists is evaluated further based on the rest of the qualifiers, thereby nesting the evaluations and achieving a depth-first effect.

Then look at the triangle example at the bottom of 346 to see how depth-first works. I think it's easier to understand this by thinking of the evaluation in terms of a stack. Initially, the expression is one element in a stack of expressions — top to the left. Elements in the stack are shown in blue.

top[(x, y) | x <- [1 .. 3], y <- [1 ..x]]bottom

Evaluating the top element of the stack (the only element of the stack), x gets 1, keeping the rest of the x generator to do later, i.e., pushed back into the stack. The expression with x = 1 is also pushed onto the stack. The stack elements are separated by the concatenation operator (++).

~> top[(1, y) | y <- [1 .. 1]] ++ [(x, y) | x <- [2 .. 3], y <- [1 ..x]]bottom

The general rule is as follows.

  • If the top element of the stack is an expression, it is evaluated. It becomes either a single element, or it is split in two. In either case, both get pushed onto the stack — joined with (++) concatenation.
  • If the top element of the stack is a literal, it is popped from the stack.

Evaluating the top element of the stack, y gets 1, which completes the y generator.

~> top[(1, 1)] ++ [(x, y) | x <- [2 .. 3], y <- [1 ..x]]bottom

At this point the top element of the stack is a literal, so it is popped.

~> [(1, 1)] ++ 
     top[(x, y) | x <- [2 .. 3], y <- [1 ..x]]bottom

Now x gets 2 (at the top of the stack), and we push the rest of the x generator to do later.

~> [(1, 1)] ++ 
     top[(2, y) | y <- [1 .. 2]] ++ [(x, y) | x <- [3 .. 3], y <- [1 ..x]]bottom

y gets 1, and we keep the rest of the y generator to do later. We push the rest of y's generator onto the stack, which already contains the rest of x's generator. The following shows [(2, 1)] as having been popped from the stack since it is a literal.

~> [(1, 1)] ++ [(2, 1)] ++ 
     top[(2, y) | y <- [2 .. 2]] ++ [(x, y) | x <- [3 .. 3], y <- [1 ..x]]bottom

Now we do the initial concatenation.

 ~> [(1, 1), (2, 1)] ++ 
     top[(2, y) | y <- [2 .. 2]] ++ [(x, y) | x <- [3 .. 3], y <- [1 ..x]]bottom

Now y gets 2, completing the y generator again. So again we "backtrack" to the x generator. We show the result list as concatenated as the elements are generated and popped.

~> [(1, 1), (2, 1), (2, 2)] ++ top[(x, y) | x <- [3 .. 3], y <- [1 ..x]]bottom

Now x gets 3, completing the x generator (nothing to push onto the stack). All we have to do now is generate the y's.

~> [(1, 1), (2, 1), (2, 2)] ++ top[(3, y) | y <- [1 .. 3]]bottom
~> [(1, 1), (2, 1), (2, 2), (3, 1)]  ++ top[(3, y) | y <- [2 .. 3]]
~> [(1, 1), (2, 1), (2, 2), (3, 1), (3, 2)] ++ top[(3, y) | y <- [3 .. 3]]bottom
~> [(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3)]top bottom

Since the stack is empty, we are done.

Now look at the permuation example on p 347. (Note that the list difference operator (\\) is in the List module, which Chapter17.hs imports.)

Infinite lists as another form of recursion

The examples in 17.7 illustrate a second way to define something recursively. Consider the following definition of fibonaccis.

fibonaccis = 0:1:zipWith (+) fibonaccis (tail fibonaccis)

How should this be understood? The fibonaccis sequence is:

[0,1,1,2,3,5,8,13,21,34, …]

and (tail fibonaccis) is:

[1,1,2,3,5,8,13,21,34, …]

If you add them together you get

[1,2,3,5,8,13,21,34, …]

This shouldn't be surprising since fibonacci n is defined as fibonacci (n-1) + fibonacci (n-2). Since we are defining fibonaccis as starting with [0, 1, …] fibonaccis and (tail fibonaccis) are defined enough so that the third element of fibonaccis can be computed. Once that element is known, we can compute the fourth element, etc.

This approach leads to a nice method for computing factorials (due to Steve Martin of the CS 332F class, Summer 2006).

factorials = 1 : [a * b | (a,b) <- zip [1..] factorials ]

The way this works is to note that the result:

[1,1,2,6,24,120,720,5040,40320,362880, …]

is the list of factorials starting from 0!. Steve zipped this with [1 .. ] creating

[(1, 1), (2, 1), (3, 2), (4, 6), (5, 24), (6, 120), (7, 720) , …]

For each element x in this list (snd x) == ((fst x)-1)! That is, the first member is the next number for which we want the factorial. The second is the factorial of the first number's predecessor. Symbolically:

[(1, 0!), (2, 1!), (3, 2!), (4, 3!), (5, 4!), (6, 5!), (7, 6!) , …]

So all that's necessary to get the next factorial is to multiply (fst x) * (snd x). Of course, this only works because we provide the value of 0!, which is the second element of the first pair.

A somewhat simpler way of doing more or less the same thing is as follows.

factorials' = (0, 1) : [(n+1, (n+1)*nFac) | (n, nFac) <- factorials']

This generates

[(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720), … ]


[(0,0!),(1,1!),(2,2!),(3,3!),(4,4!),(5,5!),(6,6!), … ]

This approach may be easier to understand since it explicitly generates the n+1st element from the nth element. One could then strip out and return a list of the second elements as follows.

factorials' = map snd factorials'

This approach suggests even simpler versions of factorials and fibonaccis. (Recall that xs!!i is Haskell notation for the ith element of the list xs and that the first element of a list is at index 0, i.e., xs!!0.)

fibonaccis = 0 : 1 : [fibonaccis!!(n-2) + fibonaccis!!(n-1) | n <- [2 .. ]]

factorials = 1 : [n * factorials!!(n-1) | n <- [1 .. ]]

This approach is less efficient in that the index operation is used repeatedly.

These are really the same as the traditional recursive versions — but done iteratively.

fibonacci n = fibonacci (n-2) + fibonacci (n-1)

factorial n = n * (factorial (n-1)) 

They work because we supply the first (or first two) value(s), and Haskell uses lazy evaluation to compute the rest.

One can even define factorial and fibonacci in terms of these lists.

factorial n = factorials!!n

fibonacci n = fibonaccis!!n

Homework 10

Lab. 17.2, (p 350)

Tuesday. 17.23, and 17.24 (see example immediately below). (p 369)

> (runningSums [0 .. ]) 
[0,1,3,6,10,15,21,28,36,45, ...] 

Note that runningSums takes a list as an argument. It produces the running sums for that list.

Thursday. Last exercise of the term. In 1770, Lagrange proved that every integer can be represented as the sum of four squares. (See also Lagrange's Four-Square Theorem in Mathworld.} Write a program that generates an infinite list of pairs whose first element is an integer and whose second element is a list of four (or fewer) integers the sum of whose squares gives the first element.

listOfFourSquares :: [(Int, [Int])]
> listOfFourSquares
[(0, []), (1, [1]), (2, [1, 1]), (3, [1, 1, 1]), (4, [2]), (5, [2, 1]), 
 (6, [2, 1, 1]), (7, [2, 1, 1, 1]), (8, [2, 2])), (9, [3]),  ... ]

Note that although it's a good idea and works in a great many cases, the following greedy algorithm doesn't always find four integers the sum of whose squares is equal to a given integer. (Its strategy is always to use the largest integer whose square is less than or equal to the desired sum.)

squares 0 = []
squares n = m:(squares(n-m*m)) 
  where m = (floor (sqrt (fromInt n)))

The smallest number for which squares fails to return a list of length 4 or less is 23.

> head [(x, squares x) | x <- [0 .. ], length (squares x) > 4]

The answer should be (23, [3, 3, 2, 1]). The greedy algorithn fails because 4, which is the largest integer <= (floor (sqrt 23)) is the wrong number to use. If we use 3 instead, that leaves room for a second 3.

23 = 32 + 32 + 22 + 12

   = 9 + 9 + 4 + 1

To generate listOfFourSquares consider an approach similar to that used in pythagTriples (p 365).

(Here is how this problem was assigned in what appears to be an introductory C++ class.)

Sep 1. Final

Please sign up to see me individually.

Alternatively, you may send me email ( telling me what you think your grade should be and why you think that's the appropriate grade based on the your work and class presentations. (Please do this week's homework before writing to me.) If I agree (or if I think your estimate is too low) I'll write back confirming your grade (or a higher grade if I think you deserve more). Otherwise, I'll ask you to sign up to see me. To allow time for these communications, please send me your grade estimate by August 29—which means you will have to complete the final homework assignment early. This is entirely optional. If you prefer, you can just sign up to see me.

Please fill in the sign-up schedule from top to bottom. Don't leave any holes.
We'll meet in the classroom (E&T 210).

10:00 Smbat Bagdassarian
10:15 Bill Kunyiha
10:30 Kunhan Kim
10:45 Eugene Flock
11:00 Sassja Ceballos
11:15 Nick Tolentino
11:30 Steven Martin
11:45 Rubic Christian
12:00 Hong Ngo
12:15 Edmond Kong
12:30 Emmanuel Sotelo
12:45 Carlo Marini
1:00 Cesar Duran
1:15 Neil Nguyen
1:30 Roudabeh Moraghebi
1:45 Roudabeh Moraghebi
If you can come earlier, please reschedule your appointments.

Thanks. Russ Abbott