Introduction to the Code Examples

This page gives access to code examples related to subjects covered in COP 4020 at UCF, as taught by Gary T. Leavens. It does not cover concepts, definitions, proofs, and examples of such that are not embodied in code.

Examples

Functional Programming in Haskell

See haskell.org for reference material and other tutorial information about Haskell.

Haskell Programs and I/O

Demonstration of how a complete program in Haskell works. This is to give context. In most of the class we focus on the function part, not the I/O part.

The main program is in TempConvertMain.lhs. It uses the function defined in TemperatureConversion.hs with tests in TemperatureConversionTests.hs.

Functions over Integers

Write functions over the Integers:

Fact.hs with tests in FactTests.hs.

Pattern Matching

Use pattern matching to write functions over tuples:

FstSnd.hs, shows fst and snd, which are built-in.

Yodaize.hs with tests in YodaizeTests.hs.

Max3.hs with tests in Max3Tests.hs

Use pattern matching to write functions over lists:

HeadTail.hs shows head and tail, which are built-in.

RemoveConsecutiveDuplicates.hs with tests in RemoveConsecutiveDuplicatesTests.hs. This is an example of more advanced pattern matching on lists.

Use built-in functions to write functions over data represented as lists:

Movies.hs with tests in MoviesTests.hs.

Use function definition syntax in Haskell to define functions:

FunctionDefinitionSyntaxExamples.hs

Functions over flat lists

Write recursive functions on lists, either explicitly or using a list comprehension:

Map.hs shows various ways to program map, which is built-in.

Filter.hs shows various ways to program filter, which is built-in.

ProductBy.hs with tests in ProductByTests.hs.

Concat.hs shows various ways to program concat, which is built-in.

AddPairs.hs with tests in AddPairsTests.hs.

AddLists.hs with tests in AddListsTests.hs

FindIndices.hs with tests in FindIndicesTests.hs

Add1ToEach.hs with tests in Add1ToEachTests.hs

InsertWhen.hs with tests in InsertWhenTests.hs

All.hs with tests in AllTests.hs

DeleteFirst.hs with tests in DeleteFirstTests.hs. Compare the recursion pattern of this function with that of DeleteAll.hs.

DeleteAll.hs with tests in DeleteAllTests.hs. Compare the recursion pattern of this function with that of DeleteFirst.hs.

QuickSort.hs with a driver in QuickSortRun.hs and QuickSortRunHelpers.hs.

Write tail recursive functions on lists:

Len.hs with tests in LenTests.hs

ListOperations.hs with tests in ListOperationsTests.hs

IndexOf.hs with tests in IndexOfTests.hs

TailrecListExamples.hs with tests in TailrecListExamplesTests.hs

Reverse.hs with tests in ReverseTests.hs

Functions over Other Grammars

Write recursive functions over new grammars. Many of the examples in this section are discussed in the paper Following the Grammar with Haskell.

Temperature Grammar

The Temperature grammar has only base cases. It is found in Temperature.hs.

SelectOuterWear.hs with tests in SelectOuterWearTests.hs.

Nat Grammar

The Nat grammar represents the natural numbers in unary notation. It is found in Nat.hs.

Naturals.hs, which has various operations on natural numbers programmed. See also NaturalsTests.hs.

LispList Grammar

The LispList grammar (see LispList.hs) is an alternative to the Haskell grammar for lists, and can be thought of as representing linked lists (as in Lisp).

LispListFuns.hs, which has various operations on LispLists programmed. See also LispListFunsTests.hs.

NonEmptyList Grammar

NonEmptyList.hs, which defines a grammar for non-empty lists, with tests in NonEmptyListTests.hs.

Instances of the class Show for the type NonEmptyList are found in NonEmptyListShow.hs (with tests in NonEmptyListShowTests.hs) and NEListShow.hs (with tests in NEListShowTests.hs).

Text Grammar

The Text grammar has two productions, each with one case containing a list. It is found in Text.hs.

The file TextExamples.hs has 3 examples written over the Text grammar. See also TextExamplesTests.hs.

A higher-order abstraction of the examples in TextExamples.hs is shown in FoldText.hs. See also FoldTextTests.hs.

ISeq Grammar

The ISeq grammar has only one recursive case. It is found in ISeq.hs. (In Haskell one can do similar things with infinite lists more conveniently.)

ISeqOps.hs contains several examples of functions defined on this grammar, including iSeqMap. There are tests in ISeqOpsTests.hs, which includes an efficient way to compute Fibonacci numbers.

Infinite Lists

Be able to take advantage of laziness in Haskell by writing functions that work on infinite lists. The grammar for infinite lists of elements of some type a can be thought of as follows:

data [a] = a : [a]

Note that there is no base case in this grammar.

Hailstone.lhs describes the Hailstone or 3x+1 problem, which uses laziness in the trajectory function. There is a main function in Hailstone.lhs that prints some interesting statistics and also tests in HailstoneTests.hs.

HailstonePeaks.lhs has functions that produce lazy lists, with a main that prints some statistics and tests in HailstonePeaksTests.hs.

Window Layout Grammar

The Window Layout grammar is found in WindowLayout.hs.

AddToSize.hs with tests in AddToSizeTests.hs.

DoubleSize.hs with tests in DoubleSizeTests.hs.

TotalWidth.hs with tests in TotalWidthTests.hs.

Music Grammar

The Music grammar is found in Music.hs.

MusicFuns.hs with tests in MusicFunsTests.hs.

FoldMusic.hs with tests in FoldMusicTests.hs. Note that at the end of FoldMusicTests.hs there are several definitions that show how foldMusic is used to write the functions in MusicFuns.hs.

RealMusic Grammar

The RealMusic grammar is found in RealMusic.hs. It is similar to the Music.hs, but only allows chords to be composed of notes, not arbitrary (Real)Music values.

RealMusicFuns.hs with tests in RealMusicFunsTests.hs.

Boolean Expression Grammar

The Boolean expression grammar is found in Bexp.hs.

BEval.hs with tests in BEvalTests.hs

NegateBexp.hs with tests in NegateBexpTests.hs

Sales Data Grammar

The Sales Data grammar is contained in SalesData.hs.

NormalizeSalesData.hs with tests in NormalizeSalesDataTests.hs

Statements and Expressions Grammar

The Statements and Expressions grammar contains 2 mutually recursive nonterminals. It is found in StatementsExpressions.hs.

StmtAdd1.hs with tests in StmtAdd1Tests.hs

SubstIdentifier.hs with tests in SubstIdentifierTests.hs

SETypeCheck.hs with tests in SETypeCheckTests.hs

A Grammar of Expressions

Eval.hs with tests in EvalTests.hs

A Grammar for the Lambda Calculus

The data definitions for this grammar are found in Lambda.hs.

Several examples, including counting variable references (countVarrefs), free variables (fv), bound variables (bv), and evaluation (eval) are found in LambdaExamples.hs. Tests for these are in LambdaExamplesTests.hs.

A generalization of the above examples is in FoldLambda.hs. Tests for these are in FoldLambdaTests.hs, which shows how to use foldLambda to recover countVarrefs, fv, bv, and eval. This example is interesting in that it doesn't recurse automatically into the bodies of Lambda expressions, because the Lambda cases of bv and eval need the body as an expression, instead of just the result of the recursion.

A similar grammar is found in LambdaExpression.hs. The following demonstrates the concepts of free and bound variables over this grammar.

FreeBoundVars.hs codes the notions of free and bound variable references in the LambdaExpression.hs grammar. See also the tests in FreeBoundVarsTests.hs.

A Grammar for "Core Haskell"

The data definitions for this grammar are found in CoreHaskellAST.hs.

CoreHaskellFreeVars with tests in CoreHaskellFreeVarsTests.hs.

CoreHaskellBoundVars with tests in CoreHaskellBoundVarsTests.hs.

Abstract Data Types

Write Abstract Data Types (ADTs) using modules.

Fraction.hs with tests in FractionTests.hs

CoreHaskellSet.hs with tests in CoreHaskellSetTests.hs.

Higher-Order Functions

Write higher order functions.

All.hs with tests in AllTests.hs

Compose.hs with tests in ComposeTests.hs

Seq.hs, with tests in SeqTests.hs.

Predicates.hs, with tests in PredicatesTests.hs.

BoolOps.hs, with tests in BoolOpsTests.hs, is an example of embedding. An instance of the Show class for BoolOps written as a client in BoolOpsShow.hs, with tests in BoolOpsShowTests.hs.

AndOr.hs, which demonstrates how to use foldr. See also the tests in AndOrTests.hs.

FoldrExercise.hs, which demonstrates the use of foldr in programming map, concatMap, and filter. See also the tests in FoldrExerciseTests.hs

LispListFuns.hs, which has various operations on LispLists programmed. See also LispListFunsTests.hs.

Gravity.lhs, which shows that fields are curried functions. See also GravityTests.hs.

Fix.hs, which contains a fixpoint combinator fix and a use of it to define the factorial function. See also FixTests.hs.

SKICombinators.lhs, which describes the S, K, and I combinators, with tests in SKICombinatorsTests.hs.

CombinatorsQuiz.lhs, which shows the power of combinators and higher-order curried functions.

Write higher-order functions that abstract some programming pattern.

A higher-order abstraction of the examples in TextExamples.hs is shown in FoldText.hs. See also FoldTextTests.hs.

FoldR.hs, which abstracts from some examples (see the file) of recursion over lists. See also FoldRTests.hs.

FoldMusic.hs with tests in FoldMusicTests.hs. Note that at the end of FoldMusicTests.hs there are several definitions that show how foldMusic is used to write the functions in MusicFuns.hs.

FoldTree.hs, which abstracts from some examples (see the file) of recursion over trees. See also FoldTreeTests.hs.

BetterTree.hs, which abstracts from some examples (see the file) of recursion over another kind of binary trees. The function fbt is the functional abstraction. See also BetterTreeTests.hs.

Tailrec.hs, which abstracts from some examples (see the file) of tail recursions. See also TailrecTests.hs.

FoldLambda.hs, which generalizes from the examples in LambdaExamples.hs (see above). See also FoldLambdaTests.hs, which shows how to use foldLambda to recover countVarrefs, fv, bv, and eval.

FloatTesting.hs, which builds on Testing.lhs, to add capabilities for testing floating point computations.

Monadic Programming

Write monadic programs, using the IO monad or other monads.

Testing.lhs, which is designed for testing. Many examples of its use appear above.

DivideAndConquer.hs, abstracts the pattern of divide and conquer algorithms in the Par monad. See its use in ParQSortRun1.hs.

Declarative Parallel Programming

Write parallel programs using Eval and Strategies.

HailstonePeaksRun4.hs is a parallel implementation of the Hailstone peaks search.

PQSortRun4.hs is a parallel implementation of quicksort. See also QuickSortRunHelpers.hs. Unfortunately, this code does not seem to run any faster than the sequential version in QuickSortRun.hs.

Write parallel programs using the Par monad.

DivideAndConquer.hs, abstracts the pattern of divide and conquer algorithms in the Par monad. See its use in ParQSortRun1.hs. This is a better way to parallelize sorting, and does give a modest speedup over the sequential version of the same algorithm. See also QuickSortRunHelpers.hs.

Actor Programming with Erlang

See erlang.org for reference material and tutorial material.

For testing Erlang programs, you may find the Makefile in this directory useful.

Functional Programming in Erlang

Write functional programs in Erlang.

deleteall.erl illustrates full recursion over flat lists. See also deleteall_tests.erl.

zip.erl illustrates simultaneous full recursion over flat lists. See also zip_tests.erl.

quicksort.erl implements the quicksort algorithm. See also quicksort_tests.erl.

Write functional programs in Erlang that involve records.

The birds module that shows uses of the measure.hrl and species.hrl header files. See also birds_tests.erl.

The birdtuples module that shows what it would be like to use tuples instead of records for the above example (birds.erl). See also birdtuples_tests.erl.

windowlayoutexamples.erl has 3 examples (addToSize, doubleSize, and totalWidth) using the Window Layout grammar (see windowlayout.erl and window.hrl). See also windowlayoutexamples_tests.erl.

Another version of addToSize that shows how to use curried functions as well as the Erlang fun expressions to interact with lists:map as well as windowlayout records. See also addToSize_tests.erl.

Write parallel programs in Erlang.

factorial.erl is a parallel implementation of the factorial function, written using tail recursion. See also factorial_tests.erl.

hailstone.erl has some basic computations relating to the Collatz (or hailstone or 3x+1) function. It also contains a higher-order function, graph. See also hailstone_tests.erl.

higherorder.erl shows the code for foreach, foldr, map, and foldl in Erlang. These are all in the lists module in Erlang. See also higherorder_tests.erl.

testing.erl provides higher-order functions for testing Erlang code.

Server Programming

Understand the primitives and idioms for using them in Erlang.

concurrencydemo.erl demonstrates several idioms in Erlang, including use of spawn, send, and receive.

sendreceive.erl demonstrates how spawn, send, and receive work.

Write a simple stateless server in Erlang.

factserver.erl is a simple server that computes factorials of integers. See factclient.erl for the client code that works with this server. See also factserver_tests.erl.

mathserver.erl is a simple server that computes compositions of functions found in Erlang's math module. See mathclient.erl for the client code that works with this server. See also mathserver_tests.erl.

Write a simple stateful server in Erlang.

countserver.erl is a simple stateful server that counts add messages. See also countserver_tests.erl.

printspooler.erl is a simple server that acts as a print spooler. See printer.erl for code that mimics the way that a printer would interact with the spooler. See printclients.erl for the client code that works with this spooler.

resourcearbiter.erl is a simple server that acts as a resource arbiter (like a semaphore or mutual exclusion lock). See resourcearbiterclient.erl for the client code that works with this resource arbiter and see resourcearbiter_tests.erl for tests.

readerswriters.erl is server that implements readers/writers concurrency, so that any number of readers may be reading, but only one writer at any time. See readerswriters_tests.erl for tests, which are interesting themselves.

buffer.erl is a simple server that acts as a buffer. See buffer_tests.erl for tests.

craigslist.erl is a server that acts like the Craig's List server, allowing one to post and read ads by category. This file also contains client functions (at the end). See craigslist_tests.erl for tests.

dropbox.erl is a simple server that keeps track of a folder of files. See dropbox_tests.erl for tests.

server1.erl is a simple server that is quoted from section 16.1 of Joel Armstrong's book Programming Erlang (Pragmatic Press, 2007).

gauge_server.erl is a simple server that keeps track of a count. It is written using server1.erl. See gauge_server_tests.erl for tests.

shoppinglist.erl is a simple server that keeps track of a shopping list (a list of atoms). It is written using server1.erl. See shoppinglist_tests.erl for tests.

Write a stateful server using Erlang's gen_server module.

runavg.erl is a server that keeps track of the running average of three floats. It is written using Erlang's gen_server module. See runavg_tests.erl for tests.


Last modified $Date: 2019/11/15 02:11:07 $.