Introduction to Computation: Haskell, Logic and Automata

ISBN-13: 9783030769079 / Angielski / Miękka / 2022 / 366 str.

Donald Sannella; Michael Fourman; Haoran Peng

Recenzje

"This book is intended as a textbook for an introductory course in computation for students beginning in informatics. No prerequisites are needed, all concepts, even elementary ones ... . it is also very suited for self-study, even if a reader is interested in Haskell or symbolic logic alone. ... Comprehension is supported by exercises for each chapter ... ." (Dieter Riebesehl, zbMATH 1497.68005, 2022)

Spis treści

1 Sets 13

2 Types 19

3 Simple Computations 27

4 Venn Diagrams and Logical Connectives 35

5 Lists and Comprehensions 45

6 Features and Predicates 55

7 Testing Your Programs 63

8 Patterns of Reasoning 73

9 More Patterns of Reasoning 81

10 Lists and Recursion 91

11 More Fun with Recursion 101

12 Higher-Order Functions 111

13 Higher and Higher 123

14 Sequent Calculus 131

15 Algebraic Data Types 143

16 Expression Trees 157

17 Karnaugh Maps 175

18 Relations and Quantifiers 183

19 Checking Satisfiability 191

20 Data Representation 203

21 Data Abstraction 221

22 Efficient CNF Conversion 237

23 Counting Satisfying Valuations 249

24 Type Classes 263

25 Search in Trees 275

26 Combinatorial Algorithms 285

27 Finite Automata 299

28 Deterministic Finite Automata 311

29 Non-Deterministic Finite Automata 321

30 Input/Output and Monads 341

31 Regular Expressions 359

32 Non-Regular Languages 369

Index 377

O autorze

Prof. Donald Sannella, Prof. Michael Fourman, and Prof. Philip Wadler are each at the University of Edinburgh's School of Informatics, Edinburgh, UK.  Mr. Haoran Peng is also at the same university department.

Blurb

Computation is a process of calculation involving arithmetic and logical steps, following a given set of rules (an algorithm).

This uniquely accessible textbook introduces students to computation using a very distinctive approach, quite rapidly leading them into essential topics with sufficient depth, yet in a highly intuitive manner. The work is anchored in coverage of functional programming (in Haskell), symbolic logic, and finite automata-- each a critical component of the foundations of Informatics, and together offering students a clear glimpse into an intellectual journey beyond mere mastery of technical skills. From core elements like types, Venn diagrams and logic, to patterns of reasoning, sequent calculus, recursion and algebraic data types, the book spans the breadth of key concepts and methods that will enable students to readily progress with their studies in Computer Science.

Topics and features:

• Spans the key concepts and methods that underpin computation
• Develops symbolic logic, with a view toward honing clarity of thought; and automata, as a foundation for future study of both their applications and related theoretical topics
• Introduces powerful functional programming ideas that will be useful regardless which programming languages are used later
• Provides numerous exercises to support a clear and open, accessible approach
• Offers a dedicated website with resources for instructors and students, including code and links to online information
• Includes a wide array of marginal notes, empowering readers to "go beyond" the content presented
• Approaches logic and automata through Haskell code, to bring key concepts alive and foster understanding through experimentation

Assuming no formal background in programming, this highly practical and accessible textbook provides the grounding fundamentals of computation for undergraduate students. Its flexible, yet clear expository style also makes the book eminently suitable as a self-study instructional guide for professionals or nonspecialists interested in these topics.

Prof. Donald Sannella, Prof. Michael Fourman, and Prof. Philip Wadler are each at the University of Edinburgh's School of Informatics, Edinburgh, UK. Mr. Haoran Peng will soon pursue research interests in machine learning and machine intelligence at Cambridge University, Cambridge, UK.