Overview

Functional programming takes as its central organizing principle the idea of evaluating expressions rather than executing instructions. It supports programming at a high level of abstraction and carefully controlling side effects, which are critical given the ever-increasing sophistication of software systems. This course explores functional programming in depth, combining practical programming experience in Haskell with a deep exploration of the underlying theory. Covered topics include algebraic data types and pattern matching, static type systems, recursion and induction, folds, lambda calculus, laziness, functors, and monads. A few weeks will also be spent learning about computer-checked formal proofs using the dependently typed functional language/proof assistant Agda.

Learning Goals

Upon completing this course, you will be able to:

• Induction and recursion
  • Design appropriate recursive data types to model data
  • Write recursive programs over recursive data types
• Type systems
  • Use types to aid in constructing and reasoning about programs
  • Understand and carry out the type inference process
• Haskell
  • Write moderately sophisticated Haskell programs to solve specific problems, using tools such as algebraic data types and pattern-matching
  • Design, use, and prove properties of recursion patterns such as maps, filters, and folds
  • Understand and apply the Functor, Applicative, and Monad hierarchy to solve problems
• λ-calculus
  • Explain the historical and continuing role of the λ-calculus as a foundational model of logic and computation
  • Become comfortable with the mechanics of the λ-calculus as a model of computation

---

Resources

• You will need to install a Haskell toolchain on your computer. Follow these instructions to install GHCup, which is a tool for managing all the major components of a Haskel toolchain (GHC, cabal, stack, haskell-language-server, etc.).

• For editing Haskell code, I recommend using Visual Studio Code, which has excellent Haskell support. But if you have a different favorite editor, it will probably work with Haskell just fine.

• You should follow this style guide when writing Haskell code in this class.

---

Calendar

Date	Topic	Code	Reading & Links	Due
W 17 Jan	No class (snow)
F 19 Jan	Rewriting systems		Verse Language Reference	Grading contract
				CSCI student info survey
M 22 Jan	Substitution; Haskell types and functions	HaskellIntro.hs	CFP Chapters 1 & 2
W 24 Jan	Functions	HaskellIntro.hs	CFP Chapters 2 & 3
F 26 Jan	More functions, tuples, recursion	HaskellIntro.hs		PS 1: Rewriting
M 29 Jan	Algebraic data types and pattern matching	ADT.hs
W 31 Jan	Algebraic data types and polymorphism	ADT.hs
		Polymorphism.hs
F 2 Feb	Polymorphism	Polymorphism.hs		PS 2: Functions & Haskell
M 5 Feb	Lists and list comprehensions	Lists.hs	CFP Chapters 5 & 6
W 7 Feb	Standard list functions	Lists.hs	CFP Chapters 6 & 7
F 9 Feb	More list functions	Lists.hs		PS 3: ADTs and polymorphism
M 12 Feb	Higher-order functions and recursion patterns	RecursionPatterns.hs	CFP Chapter 10
W 14 Feb	More recursion patterns, foldr	RecursionPatterns.hs	CFP Chapters 10 & 11
F 16 Feb	Wholemeal programming	Wholemeal.hs	CFP Chapter 11	PS 4: Lists
M 19 Feb	No class (Mid-winter break)
W 21 Feb	I/O	SideEffects.py
		IO.hs
Th 22 Feb				Grading contract evaluation I
F 23 Feb	More I/O	IO.hs		PS 5: Higher-Order Functions and Recursion Patterns
M 26 Feb	Case expressions & currying	Case.hs
		Currying.hs
W 28 Feb	Type classes	TypeClasses.hs
F 1 Mar	Semigroups & monoids	Monoids.hs		PS 6: I/O
M 4 Mar	More monoids, newtypes	Monoids.hs		Project 1
W 6 Mar	No class (Dr. Yorgey sick)
F 8 Mar	No class (Dr. Yorgey sick)
M 11 Mar	Kinds & functors	Kinds.hs
		Functor.hs
W 13 Mar	Functors	Functor.hs		PS 7: Type classes and monoids
F 15 Mar	Laziness	Laziness.hs
M 18 Mar	Spring break
M 25 Mar	Applicative	Applicative.hs
W 27 Mar	More Applicative	Applicative.hs
F 29 Mar	Applicative examples	Applicative.hs
M 1 Apr	Scanner	Scanner.hs
W 3 Apr	Introduction to Monads	Scanner.hs
		Monad.hs
		MonadInstances.hs
Th 4 Apr				Grading contract evaluation II
F 5 Apr	Monads	Monad.hs		PS 8: Applicative
M 8 Apr	No class (solar eclipse)
T 9 Apr				Final project proposal
W 10 Apr	Lambda calculus
F 12 Apr	More lambda calculus	LambdaCalc.hs
		nat.lc
		lc.tgz
S 13 Apr				PS 9: Monad
M 15 Apr	Introduction to Agda	intro.agda
W 17 Apr	More Agda, Curry-Howard Isomorphism	intro.agda
F 19 Apr	Agda, proving properties of addition	intro.agda		PS 10: Lambda calculus
M 22 Apr	Agda, proving properties of programs	programs.agda
W 24 Apr	Simply typed lambda calculus, encoding type systems in Agda	LambdaCalc.agda
F 26 Apr	Encoding STLC in Agda	LambdaCalc.agda
F 3 May	Final project presentations (2-5pm)			Final project

---

Grading

Grading contracts

You will prepare and submit for my approval a grading contract explaining your chosen final grade and what you will do to achieve it. You will then earn your chosen final grade by fulfilling the agreed-upon contract.

This may be different than what you are used to. Professor Cathy Davidson of CUNY perfectly sums up the reasons for doing things this way:

The advantage of contract grading is that you, the student, decide how much work you wish to do this semester; if you complete that work on time and satisfactorily, you will receive the grade for which you contracted. This means planning ahead, thinking about all of your obligations and responsibilities this semester and also determining what grade you want or need in this course. The advantage of contract grading to the professor is no whining, no special pleading, on the student’s part. If you complete the work you contracted for, you get the grade. Done. I respect the student who only needs a C, who has other obligations that preclude doing all of the requirements to earn an A in the course, and who contracts for the C and carries out the contract perfectly.

Required components of a grading contract

There is no specific format required for a grading contract, but it must have the following components:

• Your desired course grade. You may choose to contract for an A, B, or C (if you’re wondering about D’s and F’s, see below). Note that your grading contract should not explain the reasons for your choice. I will not judge you because of your choice, and you do not need to justify it: there are as many different valid reasons for choosing to work toward a particular final grade as there are students. If you do wish to explain to me the reasons for your choice—which you are in no way required to do—you may do so in an email, a personal conversation, etc., but it should not go in your contract.

• A description of the work and requirements you will complete, in checklist format. It doesn’t have to be super detailed, but you do have to explicitly include everything. For example, you can’t just say “I will complete all the assignments listed in the syllabus”; you must actually list them. This is so that you and I both know that you are explicitly aware of the requirements, and to help you keep track of what you have completed and what you have yet to complete. You also have some choice in terms of which assignments you complete, so you must record your choice in the contract.

Example grading contract

For example, a grading contract might look like this:

My desired course grade in Functional Programming is a B. To achieve this grade, I will complete the following:

• CSCI student info survey
• Grading contract
  • Submit grading contract
  • Grading contract evaluation 1
  • Grading contract evaluation 2
• Projects (7 points)
  • Project 1 (individual, Level 2)
  • Project 2 (Level 3)
  • Final Project (Level 2)
• Problem sets (all but 3)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

Grading contract submission

You must turn in an initial proposed grading contract by the start of class on Friday, January 19th. After the initial submission, I may require some revisions before I approve your contract.

Contract evaluation and adjustment

Two times during the semester (Thursday, February 22 and Thursday, April 4) you are required to reflect on your progress in the course and complete an evaluation of your work, comparing it against what you agreed to in your grading contract. Your evaluation should:

1. Contain a copy of your original grading contract, with items you have completed checked off.

2. Revise your grading contract with more specific details as appropriate, for example, regarding which projects you intend to complete.

3. Include a 1-2 paragraph reflection, which answers questions such as the following:

   • What have you done well?
   • What have you learned?
   • What could you do to improve your learning?
   • What could I (the instructor) do to improve your learning?
   • Are there ways in which you have not lived up to the requirements of your contract, and if so, what steps are you taking, or will you take, to rectify that?

Your evaluation is also an opportunity to request an adjustment to your contract in either direction. If you find that you will be unable to meet the obligations of your contract, you may request to move to a lower grade and its requirements. Contrariwise, if you find that you’ve been performing above the obligations of your contract, you may request to fulfill the requirements for a higher grade.

Note, however, that you don’t have to wait for an evaluation to adjust your contract. If your life has really gone off the rails (or if, say, you are finding the class easier and more enjoyable than you thought!) just come and talk to me about adjusting your contract.

A, B, and C grades

• To earn an A in the course, you must:
  • Earn at least 5 project points
  • Complete at least one project individually
  • Complete all but 1 of the assigned weekly problem sets.
  • Complete all the requirements for a C.
• To earn a B in the course, you must:
  • Earn at least 4 project points
  • Complete at least one project individually
  • Complete all but 3 of the assigned weekly problem sets.
  • Complete all the requirements for a C.
• To earn a C in the course, you must:
  • Complete the CSCI student information survey.
  • Submit and agree on a grading contract with the instructor.
  • Complete two grading contract evaluations.
  • Earn at least 3 project points.
  • Complete all but 5 of the assigned weekly problem sets.

D and F grades

[Adapted from Cathy Davidson.] You cannot intentionally contract for a grade of D (and certainly not for an F). However, I reserve the right to award a grade of D or F to anyone who fails to meet their contractual obligations in a systematic way. A “D” grade denotes some minimal fulfilling of the contract (typically, I would want to see at least 5 projects complete). An “F” denotes absence of enough satisfactory work, as contracted, to warrant passing of the course. Both a “D” and “F” denote a breakdown of the contractual relationship.

---

Coursework and policies

Problem sets

12 weekly problem sets will be assigned, with a mix of coding and written exercises. Problem sets will generally be assigned and due each Friday. Coding exercises must be submitted in .hs or .lhs format; written exercises must be submitted as a .pdf.

• Problem sets will feature exercises with a range of difficulties, generally ordered from easiest to hardest.
• Each exercise will be graded on a credit/no credit basis; submissions not receiving credit will be returned along with descriptive feedback explaining what must be revised to receive credit.
• Each problem set will specify a set number of exercises that must be completed in order to receive credit for the entire problem set. For example, a problem set with ten exercises may specify that any seven of the exercises must be completed. You are expected to choose an appropriate subset of exercises, depending on your interest and background.

#	Topic	Assigned	Due
1	Rewriting and substitution	F 19 Jan	F 26 Jan
2	Functions & Haskell	F 26 Jan	F 2 Feb
3	ADTs & Polymorphism	F 2 Feb	F 9 Feb
4	Lists	F 9 Feb	F 16 Feb
5	HOFs & Recursion Patterns	F 16 Feb	F 23 Feb
6	I/O	F 23 Feb	F 1 Mar
7	Type classes and monoids	S 2 Mar	W 13 Mar
	dickens-editor.tgz
8	Applicative	F 29 Mar	F 5 Apr
	AParser.hs, SExpr.hs
9	Monad	S 6 Apr	S 13 Apr
	risk.tgz
10	Lambda calculus	F 12 Apr	F 19 Apr
	lc.tgz

Projects

In addition to problem sets, there will be two larger coding projects in the course.

Each project will be worth up to 3 points, depending on the level to which it is completed. Each project will have a specification explaining what you must do to complete the project to each level. Generally speaking, level 1 denotes a minimal completion of the basic learning objectives for the project, level 2 denotes a fuller completion of the learning objectives, and level 3 requires some extra depth.

Projects may be completed individually, or in groups of up to 3. However, note that in order to get an A or B in the course, you must complete at least one project individually.

Project	Assigned	Due
Project 1: Game	M 12 Feb	M 4 Mar
Final project	M 1 Apr	F 3 May

Tokens

Each student starts the semester with five virtual tokens which they can spend however they wish. Tokens are non-transferable.

• Two tokens may be spent to turn in any assignment (problem set or project) late.
  • All assignments must be submitted at the latest by Friday, May 3 (the day of the final project presentations).
• One token may be spent to submit a revised problem set at any time.
• You must have enough tokens to spend before receiving a grade or feedback on a late submission or revision.

Conversely, additional tokens may be earned at any time:

• Scheduling and attending an office hours meeting with Dr. Yorgey earns one token.
• Creating a practice problem for some topic covered in the course, along with a correct solution, earns one token.
• Solving any problem on Open Kattis in Haskell earns two tokens. To prove it, send me your Haskell code along with a screenshot of your submission showing that the code was accepted by Kattis. Hint:

    main = interact solve
  
    solve :: String -> String
    solve = ...
  

• Creating an educational video for the course earns 4 tokens.
  • Videos should be around 2-4 minutes long and cover a single topic.
  • The audience for videos should be other students in the course (or students in a future offering of the course).
  • Feel free to be creative in how you record the video and what kinds of visual aids you use. For example, you might record yourself writing on a whiteboard, or on a piece of paper; or you could record your screen while you type, or draw; you could create some slides or animations to display.
  • With your permission, and appropriate attribution, videos you create will be posted to the course website.

Final project

Overview/important dates

You may complete a final project which extends or ties together some of the things we have learned over the course of the semester.

Important dates:

• Tuesday, April 9 – Project proposals due
• Friday, May 3, 2:00-5:00pm – Final project presentations

Format

You may work by yourself, or in groups of up to three students. Groups of five are right out.

You have quite a bit of latitude in what sort of project you choose to complete (subject to approval, of course). Possible types of projects include (but are not limited to):

• Developing some sort of Haskell application or library
• Encoding some proofs using Agda
• An expository presentation; e.g. pick a functional pearl (I’m happy to suggest some good ones), or a functional data structure, etc., understand and possibly re-implement it, and present it to the class.

Your project should somehow go beyond what we have covered in class, that is, completing the project should require you to learn something new.

Project proposal

You must submit a project proposal by Tuesday, April 9th explaining what you intend to do. The proposal should be about 1 page, and must clearly explain:

• What you intend to do
• Your specific goals for the project, i.e. what are the criteria for a successful project?
• An explanation of what you expect to learn, i.e. how does your project go beyond what we have covered in class?

I will provide feedback on your proposal to ensure that your project is at an appropriate level of difficulty.

Presentations

During the afternoon on Friday, May 3, you will give a short presentation of your project. The presentation could take many forms depending on the type of project. For example, it could just be a demo, if you primarily produced some sort of artifact; it could be a presentation with slides or a chalkboard talk explaining something.

Since giving a good presentation is not really a learning goal of this course, there is no particular specification or set of criteria that a presentation must meet. However, here are some suggestions for giving a good presentation:

• Give a practice run-through to a friend or two. This will help you be more familiar with what you plan to say.
• Don’t just scroll through your code (it tends to be very boring for the audience). If there are particular parts of your code that you want to highlight, copy them onto slides.
• You don’t have to make slides, but they can be helpful. If you do make slides, make sure each slide has just a few words or phrases.
• Include a live demo of your project if at all possible (and if this makes sense for your project).

Final submission

You may submit your project in one of two ways:

• By submitting a .tar, .tgz or .zip file

• By submitting a link to a publically accessible source repository, e.g. on github or bitbucket. Be sure to submit a link to one or more specific commits, tags, etc. representing what you would like to be graded, rather than just to the repository in general.

Specification

• To complete the project to Level 1:

  • Turn in a 1-2 paragraph proposal, and have it accepted.
  • The project must explore a topic relevant to the course.
  • It must compile and run successfully.
  • You must give a presentation/demo of your project during the scheduled final exam period.

• To complete the project to Level 2:

  • Accomplish what you set out to do in your proposal, or something of comparable scope.
    • It is normal for projects to diverge somewhat from the proposal. If you are concerned whether you will meet this criterion, please talk to me about it. (Somewhat paradoxically, being concerned about this is often a sign that you need not be!)

  • Ensure that your code uses good Haskell style.

  • Make sure your code is simplified as much as possible, for example, without redundant pattern-matching.

  • Turn on {-# OPTIONS_GHC -Wall #-} and make sure your code generates no warnings.

  • Ensure your project is well-documented, with plenty of comments explaining the code, thorough README and INSTALLING files, good examples (if appropriate), etc.

  • You must demonstrate evidence that you put energy and effort into your project and that you have learned something. In your presentation, or in a document accompanying your project, you should be sure to highlight work you did and things you learned, especially if it is not obvious from looking at the final product. For example, if you spent a bunch of time trying an approach that ultimately did not work, you should talk about that and what you learned from the experience.

• To complete the project to Level 3, the project must go beyond the content of the course in some significant way. I am aware that this is rather vague; if you would like to get Level 3 credit for the project, I encourage you to talk to me about it during the planning phase so that we can agree on an appropriate topic, and get feedback from me before the final deadline to make sure you are on track.

I will provide feedback on final projects that do not meet the specifications, allowing you an opportunity to address the issues and turn in a revised project.

Expectations

Although you and I play different roles in the course, we both have your learning as a common goal. There are things I expect from you as a student in the course, but there are also things you can expect of me as the course instructor and facilitator.

If I am not fulfilling my responsibilities outlined below, you are welcome (and encouraged!) to call me out, perhaps via the anonymous feedback form. I will also initiate a conversation if you are not fulfilling yours. However, none of us will meet all of the expectations perfectly—me included!—so it’s also important that we have grace and patience with one another.

	What I expect from you	What you can expect from me
Communication	Check your email and Teams for occasional course announcements. Let me know via email or Teams message if you will need to miss class for some reason. Let me know as soon as possible if you feel you are struggling, would like extra help, or have something going on that will affect your engagement in the course or your ability to fulfill your responsibilities.	Clearly communicate expectations, assignment details and dates, and grading standards. Return grades and feedback on submitted work within two weekdays of submission. Respond to emails within 24 hours.
Preparation	Come prepared to fully engage in class meetings, with distractions minimized, to the best of your ability. Spend time outside of class actively practicing unfamiliar or shaky concepts or skills (not just reading over notes).	Have a concrete plan for how we will spend each class meeting, prepared to lead you through the plan.
Engagement	Actively engage in lectures by taking notes and asking questions. Be proactive and intentional about spending time working on assignments. Abide by the College's Academic Integrity Policy and the Computer Science-specific Academic Integrity Policy.	Make myself available to meet outside of class, and give you my full attention during a meeting. Be committed to your learning, open to feedback and willing to respond in substantive ways to your suggestions or concerns.

Attendance

Attendance in this class is not required as part of your grade. However, I do expect you to attend and appreciate knowing in advance if you will need to miss class.

Disabilities

If you have a documented disability or some other reason that you cannot meet the above expectations, and/or your learning would be best served by a modification to the usual course policies, I would be happy to work with you—please get in touch (via Teams or email)! The course policies are just a means to an end; I don’t care about the policies per se but I do care about you and your learning.

It is the policy of Hendrix College to accommodate students with disabilities, pursuant to federal and state law. Students should contact Julie Brown in the Office of Academic Success (505.2954; brownj@hendrix.edu) to begin the accommodation process. Any student seeking accommodation in relation to a recognized disability should inform the instructor at the beginning of the course.

Diversity and Inclusion

Hendrix College values a diverse learning environment as outlined in the College’s Statement on Diversity. All members of this community are expected to contribute to a respectful, welcoming, and inclusive environment for every other member of the community. If you believe you have been the subject of discrimination please contact Dean Mike Leblanc at leblanc@hendrix.edu or 501-450-1222 or the Title IX Coordinator Allison Vetter at titleix@hendrix.eduor 501-505-2901. If you have ideas for improving the inclusivity of the classroom experience please feel free to contact me. For more information on Hendrix non-discrimination policies, visit hendrix.edu/nondiscrimination.

Mental and Physical Health

Hendrix recognizes that many students face mental and/or physical health challenges. If your health status will impact attendance or assignments, please communicate with me as soon as possible. If you would like to implement academic accommodations, contact Julie Brown in the office of Academic Success (brownj@hendrix.edu). To maintain optimal health, please make use of free campus resources like the Hendrix Medical Clinic or Counseling Services (501.450.1448). Your health is important, and I care more about your health and well-being than I do about this class!