About the course
This is the homepage for
CS 154: Introduction to Functional Programming,
a course offered by
Fritz Ruehr at the
Computer Science Department of
Willamette University.
This course provides a broad introduction to programming in the functional
style, including motivations, history, programming techniques and theory.
Functional programming provides concise and elegant solutions to many problems,
using an approach based on mathematics, logic and proof.
The course will be taught in Haskell, a powerful, modern programming language
which can be used for both mathematical investigations and serious system
development. Topics covered will include a broad introduction to computing,
symbolic representation of data, list manipulation, recursion, algebraic data
types, higher-order functions and type systems.
The study of functional programming languages provides a useful foundation
and perspective for further study of topics in algebra, logic, programming
languages, computer science theory and linguistics.
New (2012) News
Welcome to the 2012 homepage for CS 154!
[I have left some useful links from the 2009 and 2010 versions of the class in
an “Old News” section below.]
- Study for the final exam using the
2012 final exam review notes!
- OK, in anticipation of Wednesday, you can listen to my transcription
of Nick Lowe’s song “You Make Me”
at this link (a MIDI file);
and you can hear the original (on YouTube) for comparison
here.
And, if you want to ruminate on the idea of how music evokes emotion
(and related topics), you might want to read the discussion
here,
including especially some of the
references cited.
(You know the drill.)
- Oh, and here’s the page for the
Nikki and the Robots game, written with Haskell.
- Find information on Paul Hudak’s Haskore here:
- Hey! Lab 8 is up and ready to go!
Looking for “inspiration” for your graphics project?
Check out these links to:
Pssssst! Nathaniel’s anti-aliasing code and examples are here,
including “smooth Mickey”.
- The functional graphics files are here:
- Here are papers for the special Thanksgiving Day lecture on tree drawing:
- The Sudoku code from Professor Bird’s article can be found
here
… and, by the way, it looks like
light isn’t the only thing that adds up to white.
- The various code “scratch files” we’ve developed during lecture can now be found
here.
- This is
not a pineapple!
(via Phil Wadler
from JIMWICh
via Boing Boing.)
- Note that I have added
Homework 3 and
Lab 7
below!
(Oh, and here are the sample proofs from lecture about
map and append
and about
map and length.)
- The (syntax-highlighted) version of the sample
Rot13 solutions
I used the other day in class are
here; I also found an old graphic file explaining
some of the ideas in a visual way
here.
- Here are some pictures of abstraction techniques:
- Here is the mirror proof we will look at on Wednesday:
mirrorproof.txt
;
and here are some ideas about (admittedly rather informal)
rules for proofs (PDF)
.
- I mentioned a great paper by Richard Bird (from Oxford) in which he develops a Sudoku solver in Haskell
from "first principles"; I found
a copy on-line here.
There are also a whole bunch of Sudoku solvers available on
the Haskell wiki Sudoku page.
-
That dizzy feeling you get from too much recursion ...
;
you know what I mean
?
- Here's a handy list of
common errors in Hugs;
it may be a little out of date, but probably still helpful.
- Study for the midterm using the
2012 midterm exam review!
Also see the (abbreviated but representative) sample exam!
- I've clarified a couple of exercises from Lab 4 based on feedback from Friday's
guinea pigs, umm, lab students.
- Check here for the sample of an approach to code development.
- Check here for the type-checking diagram for map.
- We will probably have fun if we play in
this little diagrams sandbox.
- ... and some movies of some slightly more compelling graphics via Haskell via
this Quake 3 level viewer.
- You can get the installer for the Command Line Tools
(needed to install the Haskell Platform on Macs)
for System 10.7 here.
- Here's the course syllabus as a PDF file.
Haskell language resources
(See also the section on software tools below.)
Labs (in rev. chron. order)
Written homework (in rev. chron. order)
Written homework will be posted here as it is assigned;
some homework may be collected and graded — some may be self-graded with an answer key.
Handouts, examples for lecture, etc.
On-line references
We will be using the Haskell programming language as
our main implementation vehicle. There are plenty of links there about the
language, how to use it and some implementations (check out the wiki in
particular for programming advice).
Installing Hugs (Mac) or WinHugs (Windows)
On the Mac, you can either try to install the newer version of Hugs (but this requires DarwinPorts,
which is little trickier) or you can install this previous version (which should be straightforward,
although it may have some minor differences with the one in the lab):
Older (2002) version of Hugs
(Basically, if you are handy with Unix, or if you already have the Apple Developer Tools installed,
you should at least try the newer DarwinPorts one; otherwise use the older, 2002 version.)
For a text editor on the Mac, I recommend the free program TextWrangler;
you can also use TextEdit (already on your Mac for free), or vi/vim or emacs, if you know one of those.
On Windows, install the latest version of WinHugs and Crimson Editor (since this is what we use in lecture and lab) as follow:
- Install WinHugs; you can find
an installation for Windows here
(installations for Macs and Linux don't give you the cute Winhugs interface and
are a little trickier, but you can find information for them on the same page).
- Don't use the default installation directory!
Program Files contains a space,
which can mess things up: I recommend just C:\Haskell instead. (This should
create a directory C:\Haskell\Hugs.)
- Create a shortcut on the desktop.
- Right click on the shortcut and select
Properties.
- Modify the
Start In: box to set the default directory.
In the lab, we use H:\ to default to the home drive
(you have to have the drive mapped for this to work).
Students setting this up on their own computers can select whatever directory they want to use.
- Open WinHugs and set up some options:
- in
File:Options:WinHugs, change the font size to 11 (or whatever you find legible);
- in
File:Options:WinHugs, change the default editor option to:
"C:\Program Files\Crimson Editor\cedt.exe /L:%d %s "
(just the stuff between the quotes, not the quotes themselves)
(note that there are spaces between the 2 words in the folder names and there is a
space after the %s!)
- change the system environment variable
Path
to include the path to the WinHugs folder.
- Install Crimson Editor:
- create a shortcut on the desktop and change the icon from the rabbit to the
paper/pencil;
- in
Tools:Preferences:General: select "use spaces in place of tabs";
- in
Tools:Preferences:Files: Deselect "load recent..."
(although students may want to leave this on their own computers);
- add 2 files to
C:\Program Files]Crimson Editor\spec folder:
haskell.spc and
haskell.key
Old News
- Study for the final using the
final exam review!
- Regarding the Haskell community:
- I made some miscellaneous notes on Haskore here.
- Here's a link to Paul Hudak's CS 431 class homepage
with links to his new Euterpea music system. (And here's his new book.)
- As we saw in lecture, inorder traversal of a tree yields a list that looks like a "squashed" version
of the tree ... and here's the relevant film!.
- I mentioned a great paper by Richard Bird (from Oxford) in which he develops a Sudoku solver in Haskell
from "first principles"; somewhat to my surprise, I found
a copy on-line here.
There are also a whole bunch of Sudoku solvers available on
the Haskell wiki.
- The file with Haskell definitions for trees (and Ben Gardiner's family!) is
here (Trees.hs).
- a tutorial (with pictures!) on list comprehensions
- Midterm Review: the Movie! Now available at
this link
(you can use the controls at the bottom to switch between a view of the actual room, via
the camera, or a view of the computer screen as it was during the presentation;
either way the sound should keep running. The screen is hard to read, but you
can bring up the review sheet from this page in another tab or window to follow along.)
Special thanks to Cheryl Cramer at WITS for facilitating this production!
I'd also like to thank the Academy ... ☺ .
- Study for the midterm using the
midterm exam review
and take a look at a (very short) sample exam, too!
-
“Say, Fritz, what was that sample exercise you suggested for exam study?”
Why, the permutations function perms :: [a] -> [[a]] which behaves like this:
Hugs> perms "abc"
[ "abc", "bac", "bca",
"acb", "cab", "cba" ]
(and yes, that line break in there is supposed to provide a hint; look for the patterns!).
- Click here for the discussion and sample
solutions to the segment problem from the labs.
- See this graphical version of the
definition and use of reversal by accumulating parameter!
- I have written a (rather lengthy) guide to installing Hugs on the Mac; I hope this helps.
You might also try installing the the Haskell Platform
which will give you a ghci command on your command line; Kristen tried it in lab and it seemed to work fine for her.
Update! Here's some advice from Anthony Somerset about installing Hugs on Snow Leopard.
- Lab 2 is (finally!) posted; see below in the labs listing! (Sorry for the delay.)
- Now that everyone's handed in the written homework, here's
an answer key
(albeit in .txt format, and without "proof justification" comments)
- Here are a few exercises about expression “chunking” (or grouping), as promised.
These exercises will not be collected or graded—you can find solutions on the second page.
- You can review our little IRC adventure from the other day (including Mark's prank on me)
at the log of the IRC
#haskell channel
(just search for fritz or Willamette).
- Here's the (corrected!) course syllabus as a PDF file (by request).
- Some useful links into the Haskell community:
- OK, still not exactly news, but still fun:
a blog post with a fun unit of measure for learning Haskell.
(But see this cartoon for
an alternative perspective!)
- Some more "outside news", this time a couple of nice, concise blog posts
reporting on why Haskell is appealing:
Brad Clow's Why Haskell?
and
Matthieu Riou's Why Not Haskell?
.
- It requires GHC (a different compiler), but the
HLint tool from Neil Mitchell
is very cool, and might be helpful (as we reach an intermediate coding level) for cleaning
up your code.
- The file of Natural number classes is here:
Natty.hs
- For an example of an application of Haskell to a problem in mathematics and computation,
see
Conal Elliott's latest paper,
Beautiful Differentiation.
- For more about folds and unfolds, you might want to read
Jeremy Gibbon's chapter in the festschrift for Richard Bird
called
Origami Programming. [link fixed]
- Here's a link to the proof about reversal and mirroring.
... and here's a link to the proof from lecture about the
commutativity of plus over the Nat data type.
- Here are some links related to formal proofs and proof systems:
- I really cannot make this stuff up! Tonight (Mon 20 April 2009) on reddit,
there was an announcement about Haskabelle, a tool which checks proofs about Haskell code.
... and example #2 in
this demonstration code?
(updated link here).
That would be the exact example of proof we did in lecture
about reversal and mirroring!
- See
these notes on possible end-of-class topics.
- Here are some links to class material on monads:
- You can find the "Rubik's Waffle" files here:
Waffle.hs (for the main code) and
ANSI.hs (for the ANSI terminal code utilities).
- The introduction to web programming with Haskell pages are
here.
- The "recipe for folds" handout is
here.
- Don't believe everything you
read on the internet about exams.
"Pop culture", Haskell advocacy and miscellaneous links
Here are a few fun, interesting or otherwise difficult to categorize links that came up
in lecture at various points.
- Haskell, Epic Games and Unreal Tournament: here's a presentation on
the next mainstream programming language by
Tim Sweeney,
CEO and Chief Architect of Epic Games, creator of Unreal Tournament and
the Unreal game engine, about how Haskell and related technologies are crucial to the gaming
architectures of the future.
- Sweeney interview: just for good meaure, here's an interview
Sweeney did about
programming language issues for games
(this was in January 2000, before he'd been completely bitten by the Haskell bug
☺ ).
(Haskore vintage.)
