CSE 4510/CSE5400: Special Topics  Functional Programming (Fall 2017)
General info
Instructor
Ryan Stansifer
Office hours
Check my WWW page for upto date information;
you are welcome to send me email.
Lectures
Class meets from 3:30pm to 4:45 Tuesday and Thursday in LNK 255.
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: 9780596514983


Hutton 
Graham Hutton.
Programming in Haskell.
Cambridge University Press, 2007
ISBN13 9780521871723


Okasaki 
Chris Okasaki.
Purely Functional Data Structures.
Cambridge University Press, 1999
ISBN 0521663504


Reade 
Chris Reade.
Elements of Functional Programming.
Addison Wesley, 1989
ISBN 0201129159


Michaelson 
Greg J. Michaelson.
An Introduction to Functional Programming Through Lambda Calculus.
Addison Wesley, 1988
ISBN 0201178125
A freelydistributed version [400kb, pdf, 241 pages].

For information about Haskell:
For each student the
numeric scores for the
assignments and exams are recorded.
If you have any question about your standing in the class,
or if some score has been recorded wrong,
please contact me.
It goes without saying that students are expected to take the final exam
at the scheduled time during finals week.
Also, anyone representing someone else's work as their own,
will receive an F for the class.
Please keep in mind the
CS honor code.
If you receive ideas, code, or help from any source,
be sure to give proper credit and acknowledgment.
Please note, that copies of
some work (homework, projects, exams, etc) for undergraduate classes
may be kept on file.
This is done for two purposes.
For review by ABET,
for the purposes of maintaining the accreditation of the CS program,
and to detect plagiarism.
Assignments
 Read Can Programming Be Liberated from the von
Neumann Style?, Backus' Turing award lecture.
 Read
"Why Functional Programming Matters" by Hughs
and
the preface
to Real World Haskell.
Hughes & Sheeran, "Why Functional Programming Matters"
At q. v.
and Sebastian Funk, "Why Functional Programming Doesn't Matter"
q. v.
Turn in a 200 word answer to that question in a plain text, say why.txt
with reasonable line breaks (6080 characters);
due midnight, Fri, 25 Aug 2017.
submit
 Read Mathematical Preliminaries by Jean Gallier.
 Read Post system handout and
also Post system and Propositional Logic.
Post systems; exercises 1,2,3,7,9; due Fri, 1 Sep 2017.
Additional exercise, call it 'X':
Give a Post canonical system for strings with correctly
balanced and matched brackets of three types: {[()]}.
submit
You may work together on this assignment.
Text (txt) files, PDF, or clear images of paper may be submitted electronically.
 Learn Haskell, e.g., “Learn You a Haskell for Great Good!”
 Grid, due midnight, Fri, 22 Sep 2017
 Do the five logic exercises;
due Fri, 22 Sep 2017.
submit
You may work together on this assignment. Note that one question must be submitted by email.
 Additional questions:
6. Haskell data type for general Post systesm.
7. Haskell data type for propositional expressions constructed
from two symbols (P and Q) and two binary operators (And and OR).
8. Prove that the set of logical operators And and OR are not
truth functionally complete by showing not all 16 truth tables
are expressible.
 Wave, due midnight, Fri, 29 Sep 2017.
submit
 Triangle Game; due Friday, 6 Oct 2017.
submit
 Watch Lambda Calculus by Graham Hutton.
 Read Lambda Calculus chapter by Fernandez.
 Read Lambda Calculus tutorial by Rojas;
exercises 1,2,3,4,5,6,7,8,9,10; due Fri, 20 Oct 2017
submit
 Use a tree data structure of your own design to solve Spatial Structures.
Due Fri, 3 Nov 2017. You may work in groups.
submit
 Use a tree data structure of your own design to solve Frequent Values.
Due Fri, 17 Nov 2017. You may work in groups.
submit
 Read Unification Theory. [Too much!]
 Read HindleyMilner in blog by Diehl with Haskell code.
 Homework on types.
submit
 Add type rule for fix.
 Add tuples to the langauge and the type rule for them
 Encode in Haskell
\ x > (x+x, x=True)
. Derive, if possible, a typing for it.
 Encode in Haskell
let f = \ x > x in (f 3, f true)
. Derive, if possible, a typing for it.
 Encode in Haskell
\ g > let f = g in (f 3, f True)
. Derive, if possible, a typing for it.
 Project Treasure
submit
 Write an elegant Haskell solution for Gold Leaf.
submit

 Mosaics; due Friday, 29 Oct 2017.
submit
 RedBlack Trees
 Read Finger Trees by Hinze.
 Read The Curse of the Excluded Middle, by Erik Meijer
 Read OCaml for the Masses by Minksy.
 OCAML at Jane Street
 Read Max Subsequence Sum in Haskell.
 Read "Lazy DepthFirst Search ..." by King and Launchbury.
 Sinking Islands
submit
 Weirich's ICFP 2014 presentation on dependent types and redblack trees.
Weirich's talk
on .
 Baby Blocks,
submit
 Cow Pinball, dynamic programming
submit
 Extra Ombrophobic Bovines
Links
Important Notices
Title IX
What is Title IX?
Title IX of the Educational Amendments Act of 1972 is the federal law
prohibiting discrimination based on sex under any education program
and/or activity operated by an institution receiving and/or benefiting
from federal financial assistance. Behaviors that can be considered
“sexual discrimination” include sexual assault, sexual harassment,
stalking, relationship abuse (dating violence and domestic violence),
sexual misconduct, and gender discrimination. You are encouraged to
report these behaviors.
Reporting
Florida Tech can better support students in trouble if we know about
what is happening. Reporting also helps us to identify patterns that
might arise — for example, if more than one complainant reports having
been assaulted or harassed by the same individual. Florida Tech is
committed to providing a safe and positive learning experience. To
report a violation of sexual misconduct or gender discrimination,
please contact Security at 3216748111. * Please note that as your
professor, I am required to report any incidences to Security or to
the Title IX Coordinator (3216748700). For confidential reporting,
please contact CAPS at 3216748050.
Syllabus
 Introduction
 Turing machines, grammars, Post systems
 Lambdacalculus
 Combinators
 Haskell
 data types
 higherorder functions
 Monads, nonregular 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[xx<xs,x<s]++[s]++quicksort[xx<xs,x>=s]