Functional Data Structures and Algorithms: A Proof Assistant Approach

By: Nipkow, Tobias

This book is an introduction to data structures and algorithms for functional programming languages, with a focus on proofs. Starting with sorting and searching, it moves on to priority queues and advanced design and analysis techniques: dynamic programming, amortized analysis, splay trees, skew heaps and pairing heaps. The final part of the book covers a number of selected fun topics: graph algorithms, string search, Huffman's algorithm for generating optimal codes and alpha-beta pruning of game trees.

The book covers both correctness (does the algorithm do what it is supposed to do?) and running time analysis (does the algorithm terminate within a specified number of steps?). It does so in a unified manner with inductive proofs about functional programs and their running time functions.

What sets this book apart from existing books on algorithms is that all proofs have been machine-checked, by the proof assistant Isabelle. That is, in addition to the text in the book, which requires no knowledge of proof assistants , the Isabelle definitions and proofs are available online. The structured nature of Isabelle proofs permits even novices to follow the high-level arguments.

This book is aimed at teachers and students (it has been classroom-tested for a number of years) but is also a reference work for programmers and researchers who are interested in the (verified ) details of some algorithm or proof.

• Format: Paperback
• Language: English
• ISBN: B0FSD6B3ZR
• ISBN13: 9798400731594
• Release Date: September 2025
• Publisher: ACM Books
• Length: 418 Pages
• Weight: 1.57 lbs.
• Dimensions: 0.8" x 7.5" x 9.3"