Effective Haskell Solving Real-World Problems with Strongly Typed Functional Programming (Rebecca Skinner) (z-library.sk, 1lib.sk, z-lib.sk)

Early Praise for Effective Haskell As the author of the "State of the Haskell Ecosystem,” I’ve understood for some time that the Haskell ecosystem is missing a well-written book. But no longer. That well-written book is here. ➤ Gabriella Gonzalez Staff Engineer, Mercury Technologies The code written is readable, elegant, and pragmatic. It would be a must-have on my shelf or for anyone who cares about the craftsmanship of functional program- ming and reasoning. I can see myself coming back to this book again and again; it’s honestly the best Haskell book I’ve ever read. ➤ Krystal Maughan PhD student researcher and habitual Haskell enthusiast, University of Vermont As a professional Haskell programmer, it was always difficult to recommend a single up-to-date learning resource for new team members. This book fills that niche perfectly, providing both a gentle introduction to the language and a deeper hands-on dive into the practical side of software engineering in Haskell. ➤ Tikhon Jelvis Chair, Haskell.org Committee Even if you never use Haskell again, this book will teach you how to use strong typing and functional programming concepts to solve real-world problems in ways that are safe and elegant. ➤ Artem Chernyak Senior Software Developer, Horizon Investments

We've left this page blank to make the page numbers the same in the electronic and paper books. We tried just leaving it out, but then people wrote us to ask about the missing pages. Anyway, Eddy the Gerbil wanted to say “hello.”

Effective Haskell Solving Real-World Problems with Strongly Typed Functional Programming Rebecca Skinner The Pragmatic Bookshelf Raleigh, North Carolina

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and The Pragmatic Programmers, LLC was aware of a trademark claim, the designations have been printed in initial capital letters or in all capitals. The Pragmatic Starter Kit, The Pragmatic Programmer, Pragmatic Programming, Pragmatic Bookshelf, PragProg and the linking g device are trade- marks of The Pragmatic Programmers, LLC. Every precaution was taken in the preparation of this book. However, the publisher assumes no responsibility for errors or omissions, or for damages that may result from the use of information (including program listings) contained herein. For our complete catalog of hands-on, practical, and Pragmatic content for software devel- opers, please visit https://pragprog.com. The team that produced this book includes: CEO: Dave Rankin COO: Janet Furlow Managing Editor: Tammy Coron Development Editor: Michael Swaine Copy Editor: Karen Galle Indexing: Potomac Indexing, LLC Layout: Gilson Graphics Founders: Andy Hunt and Dave Thomas For sales, volume licensing, and support, please contact support@pragprog.com. For international rights, please contact rights@pragprog.com. Copyright © 2023 The Pragmatic Programmers, LLC. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form, or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior consent of the publisher. ISBN-13: 978-1-68050-934-2 Encoded using the finest acid-free high-entropy binary digits. Book version: P1.0—July 2023

Contents Acknowledgments . . . . . . . . . . . ix Foreword . . . . . . . . . . . . . . xi Introduction . . . . . . . . . . . . xiii 1. Getting Started with Haskell . . . . . . . . . 1 Exploring Haskell Interactively 2 Writing Your First Haskell Program 8 Formatting Haskell Code 9 Creating New Variables 9 Writing Functions 13 Precedence, Operators, and Fixity 21 Creating Local Variables Using Let Bindings 31 Running Code Conditionally Using Branches 34 Looping 37 Summary 44 Exercises 44 2. Working with Lists . . . . . . . . . . . 47 Writing Code Using Lists 47 Destructuring Values with Pattern Matching 66 Understanding How Programs Are Evaluated 74 Hands-On with Infinite Fibonacci Numbers 80 Summary 86 Exercises 87 3. Getting Started with Types . . . . . . . . . 89 Working with Basic Haskell Types 89 Annotating Values with Type Information 90 Looking Up Type Information 91 Writing Type Annotations for Functions 92

Reading Type Errors 96 Working with Polymorphic Functions 100 Exploring the Type Space of an Application with Undefined 103 Getting Help from Type Holes 105 Looking at the Type of main 113 Summary 114 Exercises 114 4. Creating New Types . . . . . . . . . . 117 Creating Data Types and Records 117 Creating Sum Types 127 Creating Inductively Defined Data Structures 136 Building a Calculator 139 Functions as Values 144 Creating Type Aliases 148 Summary 152 Exercises 152 5. Creating And Structuring Haskell Projects . . . . . 155 Creating Haskell Projects 155 Using Code from Other Modules 167 Creating Your Own Modules 181 Choosing What to Export 187 Documenting Modules 203 Summary 207 Exercises 207 6. Type Classes . . . . . . . . . . . . 209 Using Ad Hoc Polymorphism with Type classes 209 Specifying Type Class Instances with Type Applications 229 Wrapping Types with Newtype 236 Understanding Higher Kinded Types and Polymorphism 240 Deriving Instances 247 Deriving More Things 250 Summary 260 Exercises 261 7. Understanding IO . . . . . . . . . . . 263 Talking About IO 263 Performing IO in a Pure, Lazy Language 264 Ordering and Combining IO Actions 270 Contents • vi

Independently Sequencing IO Actions 272 Mapping IO Values with fmap 274 Running IO in Real Applications 277 Summary 281 Exercises 282 8. Working with the Local System . . . . . . . . 283 Building Applications with IO 283 Procedural Shell, Functional Core 284 Creating a Pager 285 Viewing the Contents of an ASCII or UTF8 Encoded Text File 286 Viewing Text One Page at a Time 300 Adding a Status Line with Metadata 315 Showing the Status Bar and Refactoring runHCat 325 Summary 329 Exercises 329 9. Introducing Monads . . . . . . . . . . 333 Mapping Functors 333 Applying Applicatives 342 Working with the Monad Type Class 347 Understanding the Laws of the Land 352 Using the Functor Laws 352 Using the Monad Laws 354 Using the Applicative Laws 357 Summary 361 Exercises 362 10. Mutable Data in the Real World . . . . . . . . 365 Using Mutable References in a Pure Language 365 Working with IORefs 365 Building a Basic Metrics System with IORefs 376 Dealing with Laziness and IO 385 Summary 400 Exercises 400 11. Serializing Heterogenous Data . . . . . . . . 403 Heterogenous Data in Haskell 403 A First Pass at a File Archiver 403 Serializing with Type Classes 409 Building a List of FileData Values 419 Contents • vii

Summary 432 Exercises 432 12. Deserializing Heterogenous Data . . . . . . . 435 Extracting Heterogenous Values from the Archive 435 Deserialization as Parsing 438 Creating a Parsing Function 439 Building a Monadic Parser 443 Parsing a List of Values 453 Adding a Monad Instance 459 Adding a MonadFail Instance 463 Summary 465 Exercises 465 13. Building Applications with Many Effects . . . . . 467 Revisiting the Parsing Problem 468 Handling Errors in Other Computations 475 State, Transformed 480 Stacking Transformers Effectively 483 Building a File Archiver 489 Summary 510 Exercises 510 14. Building Efficient Programs . . . . . . . . 513 Building a Naive Spellchecker 513 Memoizing editDistance 529 Internal Mutability with ST 534 Optimizing Memory Layout with Vectors 543 The Fastest Edit Distance 547 Summary 551 Exercises 552 15. Programming with Types . . . . . . . . . 553 What Is Type Level Programming? 553 Types and Kinds 554 Functions from Types to Types 565 GADTs: Functions from Terms to Types 593 Type Classes: Functions from Types to Terms 602 Summary 613 Exercises 614 Index . . . . . . . . . . . . . . 617 Contents • viii

Acknowledgments Writing this book has been a monumental effort, and I wouldn’t have finished it without the incredible and generous help of the many people who contribut- ed their own time, knowledge, energy, and support. First and foremost, I would like to express my gratitude to the technical reviewers of this book. Tikhon Jelvis, who lent an incredible amount of technical knowledge and experience teaching in his reviews. Krystal Maughan, whose relentless posi- tivity and encouragement made me believe in the book even when I was in dispair over the difficulty in writing. Artem Chernyak, whose attentiveness and careful attention to detail helped me eliminate circular dependencies and improve the organization of the content. Ryan Jones, one of the first people I taught Haskell, who helped to find many bugs in the examples. Janet Riley, who helped me focus on the perspective of readers without Haskell experience. I would also like to thank Gabriella Gonzalez. Not only have I learned a great deal from her over the years, I deeply appreciate that she has taken time away from her own book to read and write a foreword for Effective Haskell. Next I would like to thank my editor, Michael Swaine, who offered guidance, acted as a sounding board, and spent several patient years tolerating my promises that “I only have three chapters left to write.” I would also like to thank Brian MacDonald, who gave me the inspiration and confidence to begin working on this book and everyone at The Pragmatic Programmers who have helped me to go from an idea to a truly amazing book. This book would also have not been possible without the support of my spouse, Ren Wilding, who was my frequent reader, sounding board, grammar consul- tant, and writers block remover. Without their knowledge of the process of writing, I would have been hopelessly mired in writers block or stuck searching for ways to reword awkward sentences. My parrot, George, has also been instrumental as both comic relief and inspiration for many of the examples in this book. report erratum • discuss

Finally, I want to thank the Haskell community and all of the many people who have worked on the Haskell language, its compilers, libraries, tools, and ecosystem. The world is a richer, grander place thanks to all of you and the work you have done. Acknowledgments • x report erratum • discuss

Foreword When Rebecca asked me to write a foreword to her book I didn’t have to think twice about endorsing it. Our paths had crossed numerous times before. I’ve been a professional Haskell programmer for almost a decade now and I’ve been teaching and evangelizing Haskell for even longer. If you’ve used Haskell you’ve probably used one of my packages or read one of my blog posts. Rebecca immediately made an impression on me when we met at the Haskell Love conference. I was struck by her extremely sensible and pragmatic approach to Haskell. Now I know Rebecca as a colleague as well as an active member of the Haskell community. She’s an engineering manager for a Haskell team, a Haskell.org committee member, and has presented and hosted workshops at numerous Haskell conferences. Rebecca knows Haskell. As the author of the “State of the Haskell Ecosystem,” I’ve understood for some time that the Haskell ecosystem is missing a well-written book. But no longer. That well-written book is here. Yes, Rebecca writes well, but I think the secret ingredient in Rebecca’s teaching style is patience. I don’t just mean that she’s a patient teacher; she instills patience in her students, too. Haskell is a language that rewards patience by paying amazing dividends in the long run. But “in the long run” means that the payoff doesn’t come until you get beyond the beginner level. Rebecca truly understands how to mold beginners into intermediate Haskell programmers. You might be one of the many Haskell beginners looking for some way to graduate to that intermediate Haskell programmer where you really leverage the strengths of Haskell. If that’s you, then look no further: Effective Haskell is the book for you. You’ll find that this book is patient but not tedious; you might even say it’s effective. You’ll derive value from the book early on because Rebecca expertly interleaves foundational concepts with opportunities to get your hands dirty with useful applications. report erratum • discuss

If that sounds like what you’re looking for, then read on. With Effective Haskell you’re well on your way to pursuing a long and rewarding journey with a remarkably powerful language. Gabriella Gonzalez Foreword • xii report erratum • discuss

Introduction Software development is harder than it’s ever been, and the unfortunate reality is that every year things continue to get harder. Much of this difficulty is due to the complexity inherent in modern systems. Today, software needs to do more things, it needs to do them at a larger scale, and the consequences for failure are higher. To be effective in the market today, we have to use every tool at our disposal to rein in the complexity of our systems. I believe that Haskell is one of the greatest tools that we have at our disposal today to help us craft systems that are both more reliable and less complex. Haskell isn’t a new language. In fact, the first version of Haskell was published in 1990, a year before Python and five years before Java. In many ways Haskell has always been a remarkably successful language. It’s been used widely in both industry and academia for the research and development of programming languages, and the design of Haskell has been incredibly influential in shaping other languages that are in wide use today. Although it’s been wildly successful as a research tool and programming language “influencer,” industrial adoption of Haskell has lagged behind. Today, there are more Haskell jobs than ever, and more companies are choosing Haskell to build their products and key parts of their infrastructure. Right now, Haskell remains more of a secret weapon than a mainstream tool, but the clear benefits of Haskell for the kinds of systems that people are building today means that an inflection point in the popularity of the language is inevitable. If Haskell doesn’t become the next big thing, then the next big thing will certainly end up looking even more like Haskell than any of the other myriad of languages that have been influenced by it. Why Choose Haskell? The reason that Haskell is such a good choice for modern software is that it gives us everything we need to build reliable, predictable, and maintainable systems that run efficiently and can be easily scaled horizontally. This is report erratum • discuss

thanks to Haskell’s design as a lazy pure functional language with an excep- tionally powerful and expressive static type system. When you think of functional programming, the first thing that likely comes to mind are the sorts of functional programming features that are recently being added to mainstream object-oriented languages. These include things like: • Support for closures or lambda functions • Using functions like map and reduce instead of traditional loops • Immutable data structures that copy their results rather than mutating their inputs Haskell is different. The benefits we get from Haskell go far beyond being able to pass around functions and have immutable data structures. Thanks to its purity, Haskell can offer us strict guarantees about immutability across our entire program. This means that we never have to worry about unintended changes to shared or global state causing our program to crash, or think about how to coordinate access to mutable data. One of the reasons that Haskell can give us strong guarantees about what our program does where other languages can’t is thanks to the power of its type system. Haskell’s type system is more expressive than the type system of any other mainstream programming language in use these days. Thanks to the type system, a Haskell program can keep track of information about what kind of data a variable holds, where it came from, what can be done with it, and even whether the function that calculates that value could possibly fail. Of course, this type information doesn’t just help us write better programs once. Every time we make changes to our program, the type checker does its job to ensure that we haven’t introduced any new problems, and helps us track down things that might need to change. As applications grow and teams get larger, the power of the type system to help us refactor becomes even more important. Types become a way that we can communicate with our peers, to provide guard rails for how they use our code, and to make sure we are using the code they wrote as it was intended. In this way, Haskell doesn’t just solve for the problems of complexity with the software we’re writing, it also helps with the complexity inherent in building that software with a large team. Why This Book Haskell can offer enormous benefits to individuals and developers who want to write high quality software, but as the saying goes, “if it were easy, everyone would do it.” The benefits of Haskell come at the cost of a steep learning curve. Haskell is hard to learn, but this book will help. Introduction • xiv report erratum • discuss

Learning Haskell can be hard in part because it’s so different from other languages you’ve probably used. This ends up being a particularly hard problem because many of the most unusual concepts that you need to learn often show up all at the same time, leading to circular dependencies in your learning plan. This book has been carefully designed, especially in the first half, to provide an on-ramp to the language that avoids the need to get into circular knowledge references. Rather than teach you how to translate your programs from other languages, in this book you’ll develop an intuition for how to think about programs in Haskell from the ground up. This will make it easier for you to read other developers’ code, make you more effective at writing code, and help you with troubleshooting. Most of the chapters in this book build on concepts from previous chapters, and no content in any chapter relies on concepts that have not yet been introduced. You’ll never be forced to use something that hasn’t yet been fully explained. In the last half of this book, once you have worked through the fundamental materials, you may be able to approach some material out of order if there are particular areas that you are interested in. Some features of Haskell can seem unnecessarily complex the first time you encounter them. Some people, when they are faced with a feature that makes no sense, will assume the feature was a bad idea and give up on learning it altogether. Other people will put the concept on a pedestal and assign it dispro- portionate significance. In either case, the lack of motivation for the things Haskell does differently can be a barrier to learning. To help with that, each time a new concept is introduced in this book, we’ll dedicate a significant amount of time to establishing a motivation for that concept to help you better internalize the reason for the design decisions Haskell makes. Understanding the motivation will ensure you’re better positioned to make informed choices about how to design your applications, and when and how to use features of the language. Since you’ll be learning to think about programming in an entirely new way, we’ll approach the material quite slowly in the beginning, carefully outlining all of the intermediate steps that go into executing some code and walking through multiple examples. As you approach the middle of the book, the pace will pick up, and by the last few chapters you should be learning new concepts at the pace of a native Haskell developer. What to Expect as You Read This book focuses on teaching through the demos and hands-on example code. Most of the chapters in this book will start with a motivating example followed report erratum • discuss Why This Book • xv

by several interactive demonstrations of a concept that you can reproduce using the interactive Haskell development environment ghci. Most chapters will also include some projects you can build as you are working through material. The chapters will include all of the code you need to build a func- tioning minimal example, but you are encouraged to make modifications and experiment with the code as you are working through the book. At the end of each chapter you’ll also have some exercises that build on the examples you wrote. These examples will help you learn how to navigate Haskell’s documentation and work within its ecosystem to self teach, so you are better equipped to continue learning after you’ve finished the book. Compared to other programming language communities, parts of the Haskell community can tend to be a little “math jargon” heavy. It’s not uncommon to see terms from theoretical computer science and math make their way into blog posts, articles, and even library documentation. This book aims to teach Haskell without requiring either a strong background in mathematics or familiarity with mathematical jargon. Since knowing the jargon and getting comfortable using it will ultimately help make you a more effective Haskell developer, common jargon terms will be introduced, defined, and then used consistently throughout the book. If you are skipping ahead and see some intimidating sounding language, turn back a few pages and you’re likely to find a definition and several examples to help you make sense of the words before they start being used regularly. How to Read This Book This book has been designed to be read cover-to-cover as a tutorial and workbook, or to be used in a classroom or reading group setting. Starting with Chapter 1, each new chapter will continue a theme or build on some knowledge that you picked up in the previous chapter. If you have some prior experience with Haskell, it’s worthwhile to start reading from the beginning so that you can follow along with the subsequent references to earlier material. For more experienced Haskell developers, this book can also serve as a useful resource to help you learn some practical ways to apply more advanced techniques. If you’ve used Haskell in school or written a few small programs and are looking to move into building larger production applications, you may find it helpful to skim the first half of this book and then start reading the second half more thoroughly. As you are working through the book, you’ll encounter several different kinds of example code. You should always be able to tell what type of environment you should be working in based on the formatting of the examples: Introduction • xvi report erratum • discuss

• Code that starts with a λ character should be typed into ghci. • Lines that start with user@host$ should be typed into a shell like bash or zsh. • Other code can be written in Haskell files using your text editor, or written directly into ghci at your discretion. Until you have finished Chapter 5, create a new directory for each chapter. Inside of the directory you create for each chapter, create a file named after the current chapter, for example, Chapter1.hs. You can use this for keeping track of example code and experiments you want to run. You’ll also create several files named Main.hs as you are working through the examples. You can put each of these in a subdi- rectory, for example, one subdirectory per chapter, or you can rename your old Main.hs files when you are no longer actively working through them. Whatever organizational scheme you prefer, ensure you keep around all your examples and experiments since you’ll want to refer to them frequently as you are learning. Once you’ve worked through the chapter on Cabal on page 155 you’ll be better equipped to create fully stand-alone projects that you can build. You’ll also learn how to re-use code that you’ve written. From that point onward, you can create a new project for each chapter or each major example. Following Along with Example Code As you read this book, you’ll work through examples iteratively, making changes to earlier code and adding new features. Once you’ve learned about how to import code from other modules, we’ll begin introducing new features iteratively that require adding additional imports. Similarly, once you’ve learned how to work with language extensions, we’ll add them as we work through examples. The rest of this section will discuss how we’ll approach introducing new imports and extensions in example code. Don’t worry too much about the syntax yet. As you work through the book, you’ll learn about imports and language extensions before they are required for any examples. For now, skim this section and feel free to come back to it later if you need to. Most of the chapters in this book will focus on building up a few small example programs. In some cases, we’ll explicitly define a new module when we’re starting a new example. In this case, these new modules may start out including a few language extensions or imports. {-# LANGUAGE TypeApplications #-} {-# LANGUAGE DerivingStrategies #-} module Main Where import Data.Text (Text) main :: IO () main = print helloWorld report erratum • discuss How to Read This Book • xvii

As we iterate through the example, we’ll add new features that might require additional language extensions or add-ons. When we’re getting ready to use a new module or extension, we’ll add them to the top of an example: {-# LANGUAGE OverloadedStrings #-} import Data.ByteString (ByteString) helloWorld :: ByteString helloWorld = "Hello, World" In your own code, you should add these to the relevant parts of your module. Here’s an example of what your own code should look like as you follow along with the examples: {-# LANGUAGE TypeApplications #-} {-# LANGUAGE DerivingStrategies #-} {-# LANGUAGE OverloadedStrings #-} module Main Where import Data.ByteString (ByteString) import Data.Text (Text) helloWorld :: ByteString helloWorld = "Hello, World" main :: IO () main = print helloWorld Not all of the examples that you work through will start with a module and a set of imports or extensions. In these cases, you can start with your own empty module, or you can work though the examples in ghci. Compiler Versions, Language Standards, and Extensions Although there have been several different implementations of Haskell over the years, the Glasgow Haskell Compiler (GHC) is the de facto standard Haskell compiler. In this book we’ll focus on Haskell as implemented by GHC 9.4, which is the newest stable release at the time of this writing. All of the examples have also been tested with GHC 8.10. Compiler Version Differences A few examples in this book will use newer features of GHC not available in version 8.10. Look out for an aside, like this one, to learn about newer features and how to write code without those features when you need to support older compilers. As Haskell evolves, new features are typically added through extensions. Language extensions allow you to enable and disable specific language fea- tures. The Haskell2010 language standard is the default language version Introduction • xviii report erratum • discuss