Department of Computer Sciences

CSE 4510/CSE5400: Special Topics -- Functional Programming (Spring 2012)

General info

Instructor

Ryan Stansifer

Office hours

Check my WWW page for upto date information; you are welcome to send me e-mail.

Lectures

Lectures are from 6:30 to 7:45 Mondays and Wednesdays in OEC-137.

Overview

This is a course about programming in functional languages. We will focus on the Haskell programming language. Since there is little exposure to functional languages in the usual curriculum, it is impossible to effectively compare programming in a functional language with programming in an imperative language. In this course we attempt to provide the opportunity to program significant programs in Haskell.

Functional languages are important because they are easier to understand and reason about. They have an important impact on the design of all new programming languages. Imperative languages are based on the needs of the computing machinery, functional languages are closer to the way humans think.

Prerequisites

Students are expected to know how to program in an imperative language like Java, Ada or Pascal, and to know about algorithms and data structures. Such material is taught in CSE 1001, 1002, 2010 in the undergraduate curriculum.

Resources

Some books on Haskell are:

O'Sullivan et al.	Bryan O'Sullivan, John Goerzen, and Don Stewart. Real World Haskell. Sebastopol, California: O'Reilly Meida, 2008. ISBN: 978-0-596-51498-3
Hutton	Graham Hutton. Programming in Haskell. Cambridge University Press, 2007 ISBN-13 9780521871723
Okasaki	Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1999 ISBN 0-52166350-4
Reade	Chris Reade. Elements of Functional Programming. Addison Wesley, 1989 ISBN 0-201-12915-9
Michaelson	Greg J. Michaelson. An Introduction to Functional Programming Through Lmabda Calculus. Addison Wesley, 1988 ISBN 0-201-17812-5 A freely-distributed version [400kb, pdf, 241 pages].

• haskell.org
• Haskell tutorial: “Learn You a Haskell for Great Good!”

1. Read the preface to Real World Haskell and "Why Functional Programming Matters" by Hughs.
2. Read Post system handout and also Post system and Propositional Logic.
3. Post systems; exercises 1,2,3,7,9; due Mon, 30 Jan 2012. Additional exercise, call it 'X': Give a Post canonical system for strings with correctly balanced and matched brackets of three types: {[()]}.
4. Read Endo
5. Endo, part I, our first step in saving Endo. Due Fri, 3 Feb 2012.
   1. Write the program in the C programming language.
   2. Write the program in the Haskell programming language.
6. (Read Mathemtical Preliminaries.)
7. Read Lambda Calculus tutorial by Rojas; exercises 1,2,3,4,5,6,7,8,9,10; due Wed, 15 Feb 2012
8. Grid, due midnight, Mon, 20 Feb 2012
9. (Optional) Wave, due midnight, Mon, 20 Feb 2012
10. Rope-A-Dope; due midnight, Mon, 12 Mar 2012.
11. Read OCaml for the Masses by Minksy.
12. Read Max Subsequence Sum in Haskell.
13. Read a quick note about records records in Haskell.
14. Triangle Game; due midnight, Fri, 31 March 2012
15. Repeat Rope-A-Dope II; due midnight, Fri, 14 Mar 2012.
16. Read Finger Trees by Hinze.
17. Read "Lazy Depth-First Search ..." by King and Launchbury.
18. Sinking Islands
20. Read Can Programming Be Liberated from the von Neumann Style?, Backus' Turing award lecture.

Save endo!

Links

• Formal systems visualized: Turing machine, grammar, Post system

Syllabus

• Introduction
• Turing machines, grammars, Post systems
• Lambda-calculus
• Combinators
• Haskell
  • data types
  • higher-order functions
  • Monads, non-regular recursive types (e.g., finger trees)
  • Type inference
• Coq

"Spookey effects" of lazy evaluation.

minima k xs = take k (sort xs)

From Real World Haskell.

"Evoluation of a Haskell Programmer" List comprehension

quicksort  []    = []
quicksort (s:xs) =
  quicksort[x|x<-xs,x=s]

---

Ryan Stansifer <ryan@cs.fit.edu>

Last modified: Wed Mar 28 13:06:21 EDT 2012