دانلود کتاب Introduction to Computation: Haskell, Logic and Automata

فهرست مطالب :

Preface
Contents
1 Sets
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Things and Equality of Things
Sets, Set Membership and Set Equality
Subset
Set Comprehensions
Operations on Sets
Ordered Pairs and Cartesian Product
Relations
Functions
Exercises
2 Types
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Sets Versus Types
Types in Haskell
Polymorphic Types
Equality Testing, Eq and Num
Defining New Types
Types Are Your Friend!
Exercises
3 Simple Computations
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Arithmetic Expressions
Int and Float
Function Definitions
Case Analysis
Defining Functions by Cases
Dependencies and Scope
Indentation and Layout
Exercises
4 Venn Diagrams and Logical Connectives
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Visualising Sets
Visualising Operations on Sets
Logical Connectives
Truth Tables
Exercises
5 Lists and Comprehensions
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Lists
Functions on Lists
Strings
Tuples
List Comprehensions
Enumeration Expressions
Lists and Sets
Exercises
6 Features and Predicates
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Logic
Our Universe of Discourse
Representing the Universe
Things Having More Complex Properties
Checking Which Statements Hold
Sequents
Exercises
7 Testing Your Programs
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Making Mistakes
Finding Mistakes Using Testing
Testing Multiple Versions Against Each Other
Property-Based Testing
Automated Testing Using QuickCheck
Conditional Tests
Test Case Generation
Testing Polymorphic Properties
Exercises
8 Patterns of Reasoning
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Syllogisms
Relationships Between Predicates
A Deductive Argument
Negated Predicates
Contraposition and Double Negation
More Rules
Exercises
9 More Patterns of Reasoning
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Denying the Conclusion
Venn Diagrams with Inhabited Regions
Contraposition Again
Checking Syllogisms
Finding Counterexamples
Symbolic Proofs of Soundness
Deriving All of the Sound Syllogisms
Exercises
10 Lists and Recursion
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Building Lists
Recursive Function Definitions
More Recursive Function Definitions
Sorting a List
Recursion Versus List Comprehension
Exercises
11 More Fun with Recursion
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Counting
Infinite Lists and Lazy Evaluation
Zip and Search
Select, Take and Drop
Natural Numbers
Recursion and Induction
Exercises
12 Higher-Order Functions
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Patterns of Computation
Map
Filter
Fold
foldr and foldl
Combining map, filter and foldr/foldl
Curried Types and Partial Application
Exercises
13 Higher and Higher
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Lambda Expressions
Function Composition
The Function Application Operator $
Currying and Uncurrying Functions
Bindings and Lambda Expressions
Exercises
14 Sequent Calculus
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Combining Predicates
The 147Immediate148 Rule
De Morgan\'s Laws
Sequents Again
Adding Antecedents and Succedents
Sequent Calculus
Proofs in Sequent Calculus
Exercises
15 Algebraic Data Types
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
More Types
Booleans
Seasons
Shapes
Tuples
Lists
Optional Values
Disjoint Union of Two Types
Exercises
16 Expression Trees
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Trees
Arithmetic Expressions
Evaluating Arithmetic Expressions
Arithmetic Expressions with Infix Constructors
Propositions
Evaluating Propositions
Satisfiability of Propositions
Structural Induction
Mutual Recursion
Exercises
17 Karnaugh Maps
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Simplifying Logical Expressions
Conjunctive Normal form and Disjunctive Normal form
Karnaugh Maps
Converting Logical Expressions to DNF
Converting Logical Expressions to CNF
Exercises
18 Relations and Quantifiers
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Expressing Logical Statements
Quantifiers
Relations
Another Universe
Dependencies
Exercises
19 Checking Satisfiability
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Satisfiability
Representing CNF
The DPLL Algorithm: Idea
The DPLL Algorithm: Implementation
Application: Sudoku
Exercises
20 Data Representation
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Four Different Representations of Sets
Rates of Growth: Big-O Notation
Representing Sets as Lists
Representing Sets as Ordered Lists Without Duplicates
Representing Sets as Ordered Trees
Representing Sets as Balanced Trees
Comparison
Polymorphic Sets
Exercises
21 Data Abstraction
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Modular Design
Sets as Unordered Lists
Sets as Ordered Lists Without Duplicates
Sets as Ordered Trees
Sets as AVL Trees
Abstraction Barriers
Abstraction Barriers: SetAsOrderedTree and SetAsAVLTree
Abstraction Barriers: SetAsList and SetAsOrderedList
Testing
Exercises
22 Efficient CNF Conversion
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
CNF Revisited
Implication and Bi-implication
Boolean Algebra
Logical Circuits
The Tseytin Transformation
Tseytin on Expressions
Exercises
23 Counting Satisfying Valuations
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
2-SAT
Implication and Order
The Arrow Rule
Complementary Literals
Implication Diagrams with Cycles
Exercises
24 Type Classes
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Bundling Types with Functions
Declaring Instances of Type Classes
Defining Type Classes
Numeric Type Classes
Functors
Type Classes are Syntactic Sugar
Exercises
25 Search in Trees
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Representing a Search Space
Trees, Again
Depth-First Search
Breadth-First Search
Best-First Search
Exercises
26 Combinatorial Algorithms
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
The Combinatorial Explosion
Repetitions in a List
Sublists
Cartesian Product
Permutations of a List
Choosing k Elements from a List
Partitions of a Number
Making Change
Eight Queens Problem
Exercises
27 Finite Automata
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Models of Computation
States, Input and Transitions
Some Examples
Deterministic Finite Automata
Some More Examples
How to Build a DFA
Black Hole Convention
Exercises
28 Deterministic Finite Automata
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Diagrams and Greek Letters
Deterministic Finite Automata, Formally
Complement DFA
Product DFA
Sum DFA
Exercises
29 Non-deterministic Finite Automata
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Choices, Choices
Comparing a DFA with an NFA
Some More Examples
Non-deterministic Finite Automata, Formally
NFAs in Haskell
Converting an NFA to a DFA
ε-NFAs
Concatenation of ε-NFAs
Exercises
30 Input/Output and Monads
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Interacting with the Real World
Commands
Performing Commands
Commands That Return a Value
do Notation
Monads
Lists as a Monad
Parsers as a Monad
Exercises
31 Regular Expressions
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Describing Regular Languages
Examples
Simplifying Regular Expressions
Regular Expressions Describe Regular Languages
Regular Expressions Describe All Regular Languages
Exercises
32 Non-Regular Languages
Donald Sannella 慮搠 Michael Fourman 慮搠 Haoran Peng 慮搠 Philip Wadler
Boundaries of Expressibility
Accepting Infinite Languages Using a Finite Number of States
A Non-Regular Language
The Pumping Lemma
Proving That a Language Is Not Regular
Exercises
A Supplementary Information
Appendix: The Haskell Ecosystem
The Haskell Website
The Haskell Language
The Haskell Compiler GHC and Interactive Environment GHCi
The Haskell Library, Hackage, and Hoogle
The Cabal Installation Tool
The Haskell Profiler and Debugger
Indexheight12pt depth0pt width0pt
Index