Free PDF Ebooks Files @AcrobatPlanet.Com

As a course on programming, it emphasizes the analysis and solution of problems, the development of correct and efficient algorithms and data structures that embody the solutions, and the expression of the algorithms and data structures in a form suitable for processing by a computer. The focus is more on the human thought processes than on the computer execution processes.

As a course on functional programming, it approaches programming as the construction of definitions for (mathematical) functions and data structures. Functional programs consist of expressions that use these definitions. The execution of a functional program entails the evaluation of the expressions making up the program. Thus the course’s focus is on problem solving techniques, algorithms, data structures, and programming notations appropriate for the functional approach.

This is not a course on functional programming languages. In particular, the course does not undertake an in-depth study of the techniques for implementing functional languages on computers. The focus is on the concepts for programming, not on the internal details of the technological artifact that executes the programs.

Of course, we want to be able to execute our functional programs on a computer and, moreover, to execute them efficiently. Thus we must become familiar with some concrete programming language and use an implementation of that language to execute our programs. To be able to analyze program efficiency, we must also become familiar with the basic techniques that are used to evaluate expressions. To be specific, this class will use a functional programming environment (i.e., an interpreter) called Hugs. The language accepted by Hugs is the “lazy” functional programming language Haskell 98. The Hugs interpreter uses a technique called graph reduction to evaluate the expressions in a program.

Being “practical” is not an overriding concern of this course. Although functional languages are increasing in importance, their use has not yet spread much beyond the academic and industrial research laboratories. While a student may take a course on C++ programming and then go out into industry and find a job in which the C++ knowledge and skills can be directly applied, this is not likely to occur with a course on functional programming.

However, the fact that functional languages are not broadly used does not mean that this course is impractical. A few industrial applications are being developed using various functional languages. Many of the techniques of functional programming can also be applied in more traditional programming and scripting languages. More importantly, any time programmers learn new approaches to problem solving and programming, they become better programmers. A course on functional programming provides a novel, interesting, and, probably at times, frustrating opportunity to learn more about the nature of the programming task. Enjoy the semester!

Contents
1 INTRODUCTION

1.1 Course Overview
1.2 Excerpts from Backus’ 1977 Turing Award Address
1.3 Programming Language Paradigms
1.4 Reasons for Studying Functional Programming
1.5 Objections Raised Against Functional Programming

2 FUNCTIONS AND THEIR DEFINITIONS

2.1 Mathematical Concepts and Terminology
2.2 Function Definitions
2.3 Mathematical Induction over Natural Numbers

3 FIRST LOOK AT HASKELL
4 USING THE HUGS INTERPRETER

4.1 Starting Hugs
4.2 Hugs Haskell Source Files
4.3 Command Line Toggles
4.4 Other Command Line Options
4.5 Interpreter Commands
4.6 Environment Variables
4.7 Example

5 HASKELL BASICS

5.1 Built-in Types
5.2 Programming with List Patterns
5.2.1 Summation of a list (sumlist)
5.2.2 Length of a list (length’)
5.2.3 Removing adjacent duplicates (remdups)
5.2.4 More example patterns

5.3 Infix Operations
5.4 Recursive Programming Styles

5.4.1 Appending lists (++)
5.4.2 Reversing a list (rev)
5.4.3 Terminology
5.4.4 Tail recursive reverse (reverse’)
5.4.5 Local definitions (let and where)
5.4.6 Fibonacci numbers

5.5 More List Operations

5.5.1 Element selection (!!)
5.5.2 List-breaking operations (take and drop)
5.5.3 List-combining operations (zip)

5.6 Rational Arithmetic Package
5.7 Exercises

6 HIGHER-ORDER FUNCTIONS

6.1 Maps
6.2 Filters
6.3 Folds
6.4 Strictness
6.5 Currying and Partial Application
6.6 Operator Sections
6.7 Combinators
6.8 Functional Composition
6.9 Lambda Expressions
6.10 List-Breaking Operations
6.11 List-Combining Operations
6.12 Rational Arithmetic Revisited
6.13 Cosequential Processing
6.14 Exercises

7 MORE LIST NOTATION

7.1 Sequences
7.2 List Comprehensions
7.2.1 Example: Strings of spaces
7.2.2 Example: Prime number test
7.2.3 Example: Squares of primes
7.2.4 Example: Doubling positive elements
7.2.5 Example: Concatenate a list of lists of lists
7.2.6 Example: First occurrence in a list

7.3 Exercises

8 MORE ON DATA TYPES

8.1 User-Defined Types
8.2 Recursive Data Types
8.3 Exercises

9 INPUT/OUTPUT
10 PROBLEM SOLVING

10.1 Polya’s Insights
10.2 Problem-Solving Strategies

11 HASKELL “LAWS”

11.1 Stating and Proving Laws
11.2 Associativity of ++
11.3 Identity Element for ++
11.4 Relating length and ++
11.5 Relating take and drop
11.6 Equivalence of Functions
11.7 Exercises

12 PROGRAM SYNTHESIS

12.1 Fast Fibonacci Function
12.2 Sequence of Fibonacci Numbers
12.3 Synthesis of drop from take
12.4 Tail Recursion Theorem
12.5 Finding Better Tail Recursive Algorithms
12.6 Text Processing Example
12.6.1 Line processing
12.6.2 Word processing
12.6.3 Paragraph processing
12.6.4 Other text processing functions

12.7 Exercises

13 MODELS OF REDUCTION

13.1 Efficiency
13.2 Reduction
13.3 Head Normal Form
13.4 Pattern Matching
13.5 Reduction Order and Space
13.6 Choosing a Fold

14 DIVIDE AND CONQUER ALGORITHMS

14.1 Overview
14.2 Divide and Conquer Fibonacci
14.3 Divide and Conquer Folding
14.4 Minimum and Maximum of a List

15 INFINITE DATA STRUCTURES

15.1 Infinite Lists
15.2 Iterate
15.3 Prime Numbers: Sieve of Eratosthenes

Download
PDF Ebook Notes on Functional Programming with Haskell