CS 454 Haskell code files from lecture

The code files:

• Bases.hs

  Using stylized unfolds for conversion between integers and numeral strings in various bases (via divMod and sumProd; unfoldl is defined here).

• Calc.hs

  An early version of the first in the Calc sequence below; see the file Calc0.hs instead.

• Calc0.hs,   Calc1.hs,   Calc2.hs

  Three files which implement some simple expression interpreters for different semantic domains, using a stylized form with folds, then ultimately eliminate these folds in favor of direct parsing to semantic interpretation (this last step in Calc).

  Algebraic syntax with numeric literals and binary operators is extended with single variables, and interpretations in numbers, strings and "calculation traces" are extended to include parameterization by the variable's value (i.e., lifted to functions). A polynomial interpretation of univariate expressions is also given, along with a fold-based interpretation of polynomials using Horner's method.

  (Types Expr, Token and Op are defined here, as well as functions scan, parse, eval prti, calc and poly.)

• Data.hs

  Basic algebraic data types are introduced here, including simple colors, Peano-style natural numbers and a user-defined version of lists (as opposed to the Haskell's built-in lists).

• Fac.hs

  A couple of basic variations on factorial and FIbonacci are here.

• FList.hs

  This file was an attempt to explain or reconstruct efficient approaches to string concatenation from a novel perspective, namely starting from the idea that lists with "fast access to the end" can be represented as functions from lists to lists (so that append becomes function composition).

  We never finished this one up in lecture, but it was meant to tie into the the final versions of the efficient form of reverse developed in the Rev file (specifically, versions rev6 through rev8). The end of the file is meant to show that even this rather rarefied view of lists (as functions) can be used to realize significant efficiency gains, via the tree printing ("flattening") example, as in the text.

• Foo.hs

  This very short file merely demonstrates the syntax for definitions (none of them parametrized) and modules; there are a couple of sample "points-free" definitions of functions here.

• Interactive.hs

  Examples of IO and user interaction using do and monads.

• IODemo.hs

  Better examples of user interaction, using do notation.

• ListFuns.hs

  This file contains some initial examples of recursion and pattern-matching on lists: many Prelude functions are re-defined from scratch under stupid-looking names (to avoid conflicts with the Prelude), including len, append, mapp, philter, undex, unz, elem' and rev. (This file was formerly named IDunno in a moment of obvious desperation.)

• Lab5.hs

  (Not yet!)

• Length.hs

  Here are some over-blown variations on the length function, plus a test list, used to show how complicated even such a simple function can be made, using higher-order functions (but also to point out that the efficiency losses are not huge). Variations include replacing every element in the list with a "1" value and then summing (lpf) and replacing every element of the list with the successor function, then composing them all together and applying them to 0. (I suppose there is some value here in anticipating the technqiue of lists as functions/append as composition, see file FList above.)

• Pal.hs

  A simple palindrome checker; also apparently our first use of the "where" clause syntax, and the technique of keeping a list of test cases for simple regression testing.

• Rev.hs

  A long lecture on the fold function, efficient versions of reverse (essentially a derivation of foldl) and algebraic data types, introducing various trees and their folds. There is a nice "graphic" view of foldr and foldl in terms of interspersion here, as well as a short series of functions on lists written both with direct recursion and in terms of fold. There are also multiple versions of the reverse function comprising an attempt to show how accumulating parameters are used, and how foldl can be derived as a generalziation of this idea. treesort is here, along with some basic applications of tree folds, e.g., depth and size.

• Rewriting.hs and Rules.hs

  A simple equational rewriting engine based on the idea of representing successive applications as a function with a list of arguments (this involves some annoying "splicing", but gives quick access to the head).

  This was used in class to demonstrate ...

• Sorts.hs

  These are a bunch of sorting functions, based on different algorithms, but done in a stylized way which tries to draw out the relationships between the different algorithms. This material will not be on the first exam (since we haven't covered it yet).

• Tabulate.txt

  This is not a Haskell code file, although it contains a lot of code-like fragments; rather, it is a kind of "backwards development" showing several different ways one might approach writing the "tabulate" function from lab.

• Titling.hs

  Like the tabulate file above, this is a sample of how one might write a lab assignment (the "titling" function on strings). This one is a bit shorter, but shows how one might improve a function (and its performance) by consolidating "loops" (really maps).

• Trees.hs

  This file provides a simple binary tree type and its fold, along with several functions which can be defined using the fold. It also has the standard, recursive non-fold versions of these functions (for inorder traversal, summation and product, size and depth): this probably makes for a good comparison for study purposes. Finally, treesort and the number base conversion functions are here.

• Twist.hs

  This is a little sample file which shows how we can get more flexibility out of polymorphic lists by playing some tricks: Twists are like lists, but they have alternating type elements. The definitions here allow them to look a lot like lists and provide some list-like functions.

• Unfold.hs

  This file defines breadth-first tree traversal in terms of unfold (following a derivation due to Jeremy Gibbons).

• Upper.hs

  This file holds a very first pass at IO examples (see also file Interactive.hs soon).

• Webby.hs

  Using the Text.Html library to generate web pages.