This is the homepage for CS 254: 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.

News

• See a the final exam review notes to study for the exam!
• Here are some links for Tueday's lecture on Haskore and temporal media:
  • the Haskore page at haskell.org;
  • and the Haskore Wiki page;
  • a Powerpoint lecture about temporal media;
  • an academic paper about the algebraic theory of temporal media;
  • the home page for educational domain-specific languages;

• See the sample Haskell file ASCIIGraphics.hs for a very simple apporach to graphics; a better (and still easy) approach would be to generate something like a BMP file.
  For (much) more sophsitication, see Conal Elliot's paper on his Pan system.
• Revisions made to the Text Concordance lab: now with pictures!
• a tutorial (with pictures!) on list comprehensions
• See also these answers to the reduction lab (corrected!).
• See a the midterm review notes to study for the exam!
• see the file Cards.hs for our fun card-shuffling experiments from the Thursday before break!
• See a sample exam here to find out what typical structure and questions on the midterm might be!
• see the file mirrorproof.txt for a full-on version proof of the proof about tree mirroring from Lab 5.
• Mini-assignment: finish the gen function to pick out a list of people from a family tree, all those of the "nth generation". See the file for Rose trees from lecture.
  PS: I added some helpful hints to the latest lab!
• Snoc lists seen in the wild! Among other links that come up when googling for "snoc" is this one about a Haskell program to solve a game called SuperGhost.
• Mini-lab assignment: write (or finish) the tinsert function from lecture (the file is here).
  The idea is to follow the general plan of insert (which is in the file), but now we want to insert an item into a tree, specifically a binary search tree, so that the item goes appropriately left or right depending on whether it is smaller or larger than the value in the node of the tree we are inserting into.
• See also this this graphical version of the definition and use of reversal by accumulating parameter!
• Mini-homework from lecture: complete the definition of lfold (related to the Haskell Prelude's foldl) to generalize the definition of rev1 (related to the Prelude's reverse):

  rev1 xs = reva xs []
            where reva []     ys = ys
                  reva (x:xs) ys = reva xs (x:ys)
  
  lfold f u xs = lfolda xs u
                 where lfolda []     ys = ...
                       lfolda (x:xs) ys = ...

  (Hint: I have used the variable ys here, but note that this ys is not necessarily a list!)
• Here is the Alfa proof system sample I was looking for in lecture the other day; there are a whole heckuva lot of automated proof systems and similar tools out there. Finally, here is a paper about the MAG tool, which is similar to the system developed in later chapters of the textbook.
• See some "graphical thoughts" on the ROT13 problem and also some sample solutions in Haskell for lecture on Tue 29 Jan.
• Lab posted! (see below)
• No news is good news ... but welcome to the Spring 2008 class!

Labs and written homework(in rev. chron. order)

• Lab 7: Text concordance (due Thursday 24 Apr)
• Lab 6: Lookup trees (due Tuesday 8 April)
• Lab 5: Working with trees (due Tuesday 11 March)
• Lab 4: Proof by induction (due Thursday 21 February)
• Lab 3: Evaluating expressions (due Thursday 14 February)
• Lab 2: Some basic Haskell exercises (due Thursday 7 February)
• Lab 1: A Simple ROT-13 Utility (due Tuesday 29 January)

Handouts, examples for lecture, etc.

• our textbook, Introduction to Functional Programming using Haskell (2nd Edition), by Richard Bird
• Java vs. Haskell examples
• Some quick Haskell code
• Conal Elliot's Fran (animation)
• Jerzy's Clastic (textures)
• Paul Hudak's Haskore (music)
• some really long palindromes
• an English grammar
• a Haskell grammar

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).

• You might want to take a look at a tutorial or two from the Learning Haskell portion of the online Haskell Wiki pages.
• You might want to download a version of the Hugs compiler for use on your own machine. If you use a Mac, see above, and run Hugs from the command line (Terminal app) under Mac OS X. (There is also a Darwin port for Mac OS X, but it is rather more trouble to install.)
• If you want a more high-powered Haskell implementation, try the GHC compiler, but we probably won't need all this power for our purposes.
• The ZVON Haskell Reference
• Tour of the Haskell Prelude (a little bit out of date: some functions have moved to other modules, e.g., ord and chr)
• A Tour of the Haskell Syntax

Installing WinHugs

1. 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).
2. Create a shortcut on the desktop.
3. Right click on the shortcut and select Properties.
4. 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.
5. 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.
6. 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

"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 ☺ ).