You are previewing Thinking Functionally with Haskell.
O'Reilly logo
Thinking Functionally with Haskell

Book Description

Richard Bird is famed for the clarity and rigour of his writing. His new textbook, which introduces functional programming to students, emphasises fundamental techniques for reasoning mathematically about functional programs. By studying the underlying equational laws, the book enables students to apply calculational reasoning to their programs, both to understand their properties and to make them more efficient. The book has been designed to fit a first- or second-year undergraduate course and is a thorough overhaul and replacement of his earlier textbooks. It features case studies in Sudoku and pretty-printing, and over 100 carefully selected exercises with solutions. This engaging text will be welcomed by students and teachers alike.

Table of Contents

  1. Coverpage
  2. Halftitle page
  3. Title page
  4. Copyright page
  5. Contents
  6. Preface
  7. 1 What is functional programming?
    1. 1.1 Functions and types
    2. 1.2 Functional composition
    3. 1.3 Example: common words
    4. 1.4 Example: numbers into words
    5. 1.5 The Haskell Platform
    6. 1.6 Exercises
    7. 1.7 Answers
    8. 1.8 Chapter notes
  8. 2 Expressions, types and values
    1. 2.1 A session with GHCi
    2. 2.2 Names and operators
    3. 2.3 Evaluation
    4. 2.4 Types and type classes
    5. 2.5 Printing values
    6. 2.6 Modules
    7. 2.7 Haskell layout
    8. 2.8 Exercises
    9. 2.9 Answers
    10. 2.10 Chapter notes
  9. 3 Numbers
    1. 3.1 The type class Num
    2. 3.2 Other numeric type classes
    3. 3.3 Computing floors
    4. 3.4 Natural numbers
    5. 3.5 Exercises
    6. 3.6 Answers
    7. 3.7 Chapter notes
  10. 4 Lists
    1. 4.1 List notation
    2. 4.2 Enumerations
    3. 4.3 List comprehensions
    4. 4.4 Some basic operations
    5. 4.5 Concatenation
    6. 4.6 concat, map and filter
    7. 4.7 zip and zipWith
    8. 4.8 Common words, completed
    9. 4.9 Exercises
    10. 4.10 Answers
    11. 4.11 Chapter notes
  11. 5 A simple Sudoku solver
    1. 5.1 Specification
    2. 5.2 Lawful program construction
    3. 5.3 Pruning the matrix of choices
    4. 5.4 Expanding a single cell
    5. 5.5 Exercises
    6. 5.6 Answers
    7. 5.7 Chapter notes
  12. 6 Proofs
    1. 6.1 Induction over natural numbers
    2. 6.2 Induction over lists
    3. 6.3 The function foldr
    4. 6.4 The function foldl
    5. 6.5 The function scanl
    6. 6.6 The maximum segment sum
    7. 6.7 Exercises
    8. 6.8 Answers
    9. 6.9 Chapter notes
  13. 7 Efficiency
    1. 7.1 Lazy evaluation
    2. 7.2 Controlling space
    3. 7.3 Controlling time
    4. 7.4 Analysing time
    5. 7.5 Accumulating parameters
    6. 7.6 Tupling
    7. 7.7 Sorting
    8. 7.8 Exercises
    9. 7.9 Answers
    10. 7.10 Chapter notes
  14. 8 Pretty-printing
    1. 8.1 Setting the scene
    2. 8.2 Documents
    3. 8.3 A direct implementation
    4. 8.4 Examples
    5. 8.5 The best layout
    6. 8.6 A term representation
    7. 8.7 Exercises
    8. 8.8 Answers
    9. 8.9 Chapter notes
  15. 9 Infinite lists
    1. 9.1 Review
    2. 9.2 Cyclic lists
    3. 9.3 Infinite lists as limits
    4. 9.4 Paper–rock–scissors
    5. 9.5 Stream-based interaction
    6. 9.6 Doubly-linked lists
    7. 9.7 Exercises
    8. 9.8 Answers
    9. 9.9 Chapter notes
  16. 10 Imperative functional programming
    1. 10.1 The IO monad
    2. 10.2 More monads
    3. 10.3 The State monad
    4. 10.4 The ST monad
    5. 10.5 Mutable arrays
    6. 10.6 Immutable arrays
    7. 10.7 Exercises
    8. 10.8 Answers
    9. 10.9 Chapter notes
  17. 11 Parsing
    1. 11.1 Parsers as monads
    2. 11.2 Basic parsers
    3. 11.3 Choice and repetition
    4. 11.4 Grammars and expressions
    5. 11.5 Showing expressions
    6. 11.6 Exercises
    7. 11.7 Answers
    8. 11.8 Chapter notes
  18. 12 A simple equational calculator
    1. 12.1 Basic considerations
    2. 12.2 Expressions
    3. 12.3 Laws
    4. 12.4 Calculations
    5. 12.5 Rewrites
    6. 12.6 Matchings
    7. 12.7 Substitutions
    8. 12.8 Testing the calculator
    9. 12.9 Exercises
    10. 12.10 Answers
    11. 12.11 Chapter notes
  19. Index