Student Homework and Presentation Record.
Functional Programming: Hugs: Haskell/HUGS, Text: Haskell: The Craft of Functional Programming (code: Downloads), Wiki bulletin board for new HUGS users.
Prolog: SWI Prolog
Introduction to functional programming and HUGS: Thompson, Chapters 1 and 2.
Homework due 4/5:
Types and Definitions: Thompson, Chapter 3.
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 ->
> 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
> 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.
Also note that to load Chapter3.hs or Chapter3.lhs you must modify the import statement:
> import Prelude hiding
> import Char hiding (toUpper, isDigit)
Apparently the Char library was extracted from the Prelude.
I can't get 4 'max' 5 to work. Can you? David Anthropoulos pointed out that it should be 4 `max` 5, using the backquote, the key to the left of the '1' key.
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 = 5
declares the identifier "five" to be of type Integer and giving it a value of 5. When you write
> square :: 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 due 4/12:
Introduction to Logic Programming and Prolog: Clocksin, Chapter 1.
To experiment with the last example in the chapter (p 11), create a file with the following content.
Load that file into Prolog; then run the goal:
?- trace, human(X), honest(X).
Homework due 4/14:
Recursion, tuples, and Lists: Thompson, Chapters 4 - 7 (selected parts).
> switch:: (Int -> Int ->
Int) -> (Int -> Int -> Int)
> switch (-) = (+)
> switch (+) = (-)
After the preceding definitions: (switch (-)) 3 4 yields 7.
However: (switch (+)) 3 4 also yields 7.
Apparently, it is not possible to compare two identifiers to determine
whether they refer to the same function.
Homework due 4/19:
Recursion and Lists: Clockson, Chapters 2 and 3 (selected parts).
Homework due 4/21: the "Practice" exercises on the following pages: 19 (second "Practice"), 22, 24 (part 3 only), 32, 33 (don't do the "Practice" but fix setify/2 so that it works correctly even on backtracking. It's a simple change to the 3rd clause. It requires that you use not or "\+" which Clockson hadn't covered to that point in the book.), 35 (write the program alternate/3), 37.
Also write a single prolog predicate zipUnzip/3 that does the equivalent of zip and unzip in Haskell.
?- zipUnzip([1, 2, 3], [a, b, c], Z) .
Z = [(1, a), (2, b), (3, c)]
?- zipUnzip(A, B, [(1, a), (2, b), (3, c)]).
A = [1, 2, 3]
B = [a, b, c]
In other words, zipUnzip/3 works both "forwards" and "backwards."
Polymorphism and higher order functions: Thompson, Sections 5.7 and 9.2.
Homework due 4/26:
The "cut": Clockson, Chapter 4.
Homework due 4/28:
Folding and primitive recursion: Thompson, Section 9.3. (We are skipping Section 9.4.)
Homework due 5/10:
The "cut": Clockson, Complete Chapter 4.
Homework due 5/12: Write predicates called eq/2 and notEq/2 that are equivalent to == and \==.
That is, eq(X, Y) should be identical to A == B, and notEq(X, Y) should be identical to X \== Y.
Note that A \== B is the same as \+ (A == B). So notEq(X, Y) should be the same as \+ eq(X, Y). (It's ok to define notEq/2 in terms of eq/2 or vice versa, whichever is easier.)
The call eq(A, B) should succeed if:
It should fail in all other cases. Of course, eq(A, B) should not change A or B. If they start as variables they should finish as variables. If they were not unified prior to the call eq(A, B), they should not be unified after the call.
For example, both
?- A = B, A == B.
?- A = C, B = D, f(A, B) == f(C, D).
succeed, whereas both
?- A == B.
?- f(A, B) == f(C, D).
In all cases, A, B, C, and D remain variables and do not become unified other than as indicated explicitly in the examples.
Note that different/2 in Clockson p. 50 is not the same as \==. If A and B have not been unified, different(A, B) fails, but A \== B succeeds. Clockson's different/2 means only that its arguments cannot unify, not that they are not eq/2.
% T is already ground. Do nothing
makeGround(T) :- ground(T), !.
% T is a variable. Make it the atom '$$$'. Not a good idea, but it will do for now.
makeGround(T) :- var(T), !, T = '$$$'.
% T is a list. Walk down the list and make each entry ground.
makeGround([T | Ts]) :- !, makeGround(T), makeGround(Ts).
% T is some other structure. Use Univ to convert T into a list. Once
% we have a list, we can ignore the functor, which is always ground,
% and walk down the list or arguments, making each of them ground.
makeGround(T) :- T =.. [_F | Args], makeGround(Args).
Functions as values. Thompson sections 10.1 - 10.3
Homework due 5/17: Exercises 10.2, 10.3, 10.7, 10.8, 10.9. Exercise 10.10 is optional..
Homework due 5/19: .
This week this class will be taught using technologically mediated tools. Read the sections in advance. Then meet during the class period in the chat room on the CS_332 YahooGroups web site. Discuss the material amongst yourselves. Look over the homework during the discussion to be sure that you can handle it. Use the CS_332 mailing list as usual for problems you encounter after the chat room discussion.
Partial application. Thompson sections 10.4 and 10.9.
Homework due 5/24: Exercises 10.12, 10.13, 10.33, 10.34.
findall/3. Look up findall/3 in the online SWI-Prolog reference manual: http://www.swi.psy.uva.nl/projects/SWI-Prolog/Manual/allsolutions.html. You will find it is very much like list comprehension in Haskell. Although they are quite similar, findall/3 is the simplest and most intuitive of the three Prolog predicates: findall/3, bagof/3,and setof/3.
Homework due 5/26: .Write findall/3 versions of setify/2, union/3, intersection/3, setDifference/3, and zip/3. Be sure that union/3 and intersection/3 return sets, i.e., no duplicates.
Overloading and type classes. Thompson sections 12.1 and 12.2.
Homework due 5/30: Exercises 12.1 - 12.3
Difference Lists. Clockson Chapter 5.
Homework due 6/2: .
Define the following predicates:
Lazy programming. Thompson sections 17.1, 17.2 (page 343 only), Example 1. List minimum (p 351), and 17.6 including Example 1 but not Example 2.
Homework due at final: exercises 17.24 and 17.25. See examples immediately below.
Main> take 10 (runningSum [0 .. ])
[0,1,3,6,10,15,21,28,36,45] :: [Integer]
Main> take 10 (infiniteProduct [0 .. ] [ 0 .. ])
[(0,0),(1,0),(1,1),(2,0),(2,1),(2,2),(3,0),(3,1),(3,2),(3,3)] :: [(Integer,Integer)]
Hint. To write infiniteProduct, use the technique used in pythagTriples (p. 365) but generate all possible pairs of indices into the two argument lists. (If you have taken CS 486, this should be familiar as a technique for generating certain infinite sets such as the set of all rational numbers.) Recall that if xs is a list, xs!!j is the jth element of xs. It's not clear to me how to use infiniteProduct of just two lists to generate the Pythagorean triples. It makes more sense to me to write infiniteProduct to take three arguments rather than two. Then test each of the triples to see if it is Pythagorean. If you do that, the indices themselves could be the triples to be tested, so you are back to the original code for pythagTriples. But write infiniteProduct with two (or three) argument lists anyway. It should work no matter what the lists are.
Please sign up for an appointment in lieu of a final exam. The sign up sheet is at the course web site at: http://groups.yahoo.com/group/CS_332/files/. Use the sheet with the latest version letter (a, b, c, ...). Select a convenient time and fill in your name and email address. Then increment the version letter (a -> b -> c -> d ...) and upload the revised sheet. If you find that someone else has already uploaded a signup sheet with that version letter, the two of you were modifying the sheet at the same time, and the other person beat you. Start again with the new latest version.
My home page