Haskell in Depth (Vitaly Bragilevsky) (z-library.sk, 1lib.sk, z-lib.sk)

M A N N I N G Vitaly Bragilevsky Foreword by Simon Peyton Jones

Selected examples inside the book (Continues on inside back cover) Name Main features Section Extracting a vocabulary  Designing a small functional program  Using OverloadedStrings GHC extension  Working with Text from the text package  Formatting texts with fmt 1.2–1.4 Manipulating a radar antenna  Using type classes with derived instances  Defining your own type classes  Implementing type class instances  Exploiting randomness for testing 2.1 Arithmetic expressions  Converting recursive datatype values to Text  Implementing stateful imperative algorithms with the State monad  Exploiting complex monad transformer stacks with mtl  Handling exceptions in monad stacks  Controlling domain types with GADTs (generalized algebraic data types) 2.2, 5.2, 6.1, 7.2, 11.4 Stock quotes  Structuring a program with modules  Plotting graphs with Chart and Chart-diagrams  Generating HTML with blaze-html  Processing command-line arguments with optparse-applicative  Reading CSV files with cassava 3.1–3.3 Generating SQL  Processing potentially incorrect data with logging errors in the Writer monad  Using the traverse function  Applying GHC.Generics to generating SQL queries from data type declarations 5.1, 12.2 Disk usage  Manipulating files and directories  Working in IO-based monad transformer stacks 6.2 Sunrise and sunset  Dealing with times and time zones  Parsing JSON with aeson  Making HTTP requests with req  Designing an exception-handling strategy 7.4

Haskell in Depth VITALY BRAGILEVSKY FOREWORD BY SIMON PEYTON JONES M A N N I N G SHELTER ISLAND

For online information and ordering of this and other Manning books, please visit www.manning.com. The publisher offers discounts on this book when ordered in quantity. For more information, please contact Special Sales Department Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 Email: orders@manning.com ©2021 by Manning Publications Co. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps. Recognizing the importance of preserving what has been written, it is Manning’s policy to have the books we publish printed on acid-free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine. Manning Publications Co. Development editor: Jenny Stout 20 Baldwin Road Technical development editor: Marcello Seri PO Box 761 Review editor: Aleksandar Dragosavljević Shelter Island, NY 11964 Production editor: Lori Weidert Copy editor: Pam Hunt Proofreader: Katie Tennant Technical proofreader: Alexander Vershilov Typesetter: Gordan Salinovic Cover designer: Marija Tudor ISBN 9781617295409 Printed in the United States of America

To my mother

v brief contents PART 1 CORE HASKELL ................................................................1 1 ■ Functions and types 3 2 ■ Type classes 18 3 ■ Developing an application: Stock quotes 60 PART 2 INTRODUCTION TO APPLICATION DESIGN ............................97 4 ■ Haskell development with modules, packages, and projects 99 5 ■ Monads as practical functionality providers 132 6 ■ Structuring programs with monad transformers 170 PART 3 QUALITY ASSURANCE .....................................................203 7 ■ Error handling and logging 205 8 ■ Writing tests 246 9 ■ Haskell data and code at run time 281 10 ■ Benchmarking and profiling 310

BRIEF CONTENTSvi PART 4 ADVANCED HASKELL......................................................341 11 ■ Type system advances 343 12 ■ Metaprogramming in Haskell 387 13 ■ More about types 435 PART 5 HASKELL TOOLKIT ........................................................477 14 ■ Data-processing pipelines 479 15 ■ Working with relational databases 530 16 ■ Concurrency 567

vii contents foreword xv preface xvii acknowledgments xxiv about this book xxvi about the author xxxii about the cover illustration xxxiii PART 1 CORE HASKELL ......................................................1 1 Functions and types 3 1.1 Solving problems in the GHCi REPL with functions 4 1.2 From GHCi and String to GHC and Text 6 1.3 Functional programs as sets of IO actions 7 1.4 Embracing pure functions 10 Separating I/O from pure functions 10 ■ Computing the most frequent words by sorting them 13 ■ Formatting reports 14 Rule them all with IO actions 17

CONTENTSviii 2 Type classes 18 2.1 Manipulating a radar antenna with type classes 19 The problem at hand 19 ■ Rotating a radar antenna with Eq, Enum, and Bounded 21 ■ Combining turns with Semigroup and Monoid 26 ■ Printing and reading data with Show and Read 30 ■ Testing functions with Ord and Random 33 2.2 Issues with numbers and text 38 Numeric types and type classes 38 ■ Numeric conversions 40 Computing with fixed precision 41 ■ More about Show and Read 43 ■ Converting recursive types to strings 47 2.3 Abstracting computations with type classes 51 An idea of a computational context and a common behavior 51 Exploring different contexts in parallel 53 ■ The do notation 54 Folding and traversing 56 3 Developing an application: Stock quotes 60 3.1 Setting the scene 61 Inputs 62 ■ Outputs 62 ■ Project structure 64 3.2 Exploring design space 68 Designing the user interface 69 ■ Dealing with input data 70 Formatting reports 72 ■ Plotting charts 73 Project dependencies overview 74 3.3 Implementation details 75 Describing data 76 ■ Plotting charts 80 ■ Preparing reports 85 Implementing the user interface 92 ■ Connecting parts 94 PART 2 INTRODUCTION TO APPLICATION DESIGN...................97 4 Haskell development with modules, packages, and projects 99 4.1 Organizing Haskell code with modules 100 Module structure, imports and exports, and module hierarchy 100 Custom Preludes 105 ■ Example: containers-mini 107 4.2 Understanding Haskell packages 111 Packages at the GHC level 111 ■ Cabal packages and Hackage 114 4.3 Tools for project development 121 Dependency management 122 ■ Haskell projects as a collection of packages 127 ■ Common project management activities and tools 129

CONTENTS ix 5 Monads as practical functionality providers 132 5.1 Basic monads in use: Maybe, Reader, Writer 133 Maybe monad as a line saver 133 ■ Carrying configuration all over the program with Reader 136 ■ Writing logs via Writer 140 5.2 Maintaining state via the State monad 147 Basic examples with the State monad 148 ■ Parsing arithmetic expressions with State 152 ■ RWS monad to rule them all: The game of dice 160 5.3 Other approaches to mutability 162 Mutable references in the IO monad 162 ■ Mutable references in the ST monad 166 6 Structuring programs with monad transformers 170 6.1 The problem of combining monads 171 Evaluating expressions in reverse Polish notation 171 Introducing monad transformers and monad stacks 174 6.2 IO-based monad transformer stacks 179 Describing a monad stack 182 ■ Exploiting monad stack functionality 184 ■ Running an application 188 ■ Can we do it without RWST? 189 6.3 What is a monad transformer? 190 Step 0: Defining a type for a transformer 191 ■ Step 1: Turning a monad stack into a monad 191 ■ Step 2: Implementing the full monad stack functionality 195 ■ Step 3: Supplying additional functionality 197 ■ Using a transformer 198 6.4 Monad transformers in the Haskell libraries 199 Identity is where it all starts 199 ■ An overview of the most common monad transformers 200 PART 3 QUALITY ASSURANCE ...........................................203 7 Error handling and logging 205 7.1 Overview of error-handling mechanisms in Haskell 206 The idea of exceptions 206 ■ To use or not to use? 208 Programmable exceptions vs. GHC runtime exceptions 209 7.2 Programmable exceptions in monad stacks 210 The ExceptT monad transformer 211 ■ Example: Evaluating RPN expressions 211

CONTENTSx 7.3 GHC runtime exceptions 216 An idea of extensible exceptions 216 ■ Throwing exceptions 218 Catching exceptions 219 7.4 Example: Accessing web APIs and GHC exceptions 222 Application components 225 ■ Exception-handling strategies 233 7.5 Logging 241 An overview of the monad-logger library 243 ■ Introducing logging with monad-logger into the suntimes project 244 8 Writing tests 246 8.1 Setting a scene: IPv4 filtering application 247 Development process overview 247 ■ Initial implementation 248 8.2 Testing the IPv4 filtering application 252 Overview of approaches to testing 253 ■ Testing Cabal projects with tasty 253 ■ Specifications writing and checking with Hspec 255 ■ Property-based testing with Hedgehog 262 Golden tests with tasty-golden 272 8.3 Other approaches to testing 276 Testing functions à la the REPL with doctest 276 ■ Lightweight verification with LiquidHaskell 278 ■ Code quality with hlint 279 9 Haskell data and code at run time 281 9.1 A mental model for Haskell memory usage at run time 282 General memory structure and closures 282 ■ Primitive unboxed data types 284 ■ Representing data and code in memory with closures 285 ■ A detour: Lifted types and the concept of strictness 290 9.2 Control over evaluation and memory usage 293 Controlling strictness and laziness 293 ■ Defining data types with unboxed values 299 9.3 Exploring compiler optimizations by example 301 Optimizing code manually 302 ■ Looking at GHC Core 308 10 Benchmarking and profiling 310 10.1 Benchmarking functions with criterion 311 Benchmarking implementations of a simple function 311 Benchmarking an IPv4 filtering application 316

CONTENTS xi 10.2 Profiling execution time and memory usage 327 Simulating iplookup usage in the real world 328 ■ Analyzing execution time and memory allocation 329 ■ Analyzing memory usage 333 10.3 Tuning performance of the IPv4 filtering application 334 Choosing the right data structure 335 ■ Squeezing parseIP performance 336 PART 4 ADVANCED HASKELL............................................341 11 Type system advances 343 11.1 Haskell types 101 344 Terms, types, and kinds 344 ■ Delivering information with types 348 ■ Type operators 355 11.2 Data kinds and type-level literals 356 Promoting types to kinds and values to types 356 ■ Type-level literals 358 11.3 Computations over types with type families 362 Open and closed type synonym families 362 ■ Example: Avoid character escaping in GHCi 365 ■ Data families 368 Associated families 370 11.4 Generalized algebraic data types 372 Example: Representing dynamically typed values with GADTs 373 Example: Representing arithmetic expressions with GADTs 376 11.5 Arbitrary-rank polymorphism 378 The meaning 378 ■ Use cases 380 11.6 Advice on dealing with type errors 383 Be explicit about types 383 ■ Ask the compiler 385 ■ Saying more about errors 386 12 Metaprogramming in Haskell 387 12.1 Deriving instances 388 Basic deriving strategies 388 ■ The problem of type safety and generalized newtype deriving 393 ■ Deriving by an example with DerivingVia 400 12.2 Data-type-generic programming 401 Generic data-type representation 402 ■ Example: Generating SQL queries 405

12.3 Template Haskell and quasiquotes 410 A tutorial on Template Haskell 411 ■ Example: Generating remote function calls 421 13 More about types 435 13.1 Types for specifying a web API 436 Implementing a web API from scratch 436 ■ Implementing a web service with servant 445 13.2 Toward dependent types with singletons 447 Safety in Haskell programs 447 ■ Example: Unsafe interface for elevators 448 ■ Dependent types and substituting them with singletons 452 ■ Example: Safe interface for elevators 458 PART 5 HASKELL TOOLKIT ..............................................477 14 Data-processing pipelines 479 14.1 Streaming data 480 General components and naive implementation 481 ■ The streaming package 493 14.2 Approaching an implementation of pipeline stages 502 Reading and writing data efficiently 502 ■ Parsing data with parser combinators 504 ■ Accessing data with lenses 509 14.3 Example: Processing COVID-19 data 517 The task 517 ■ Processing data 519 ■ Organizing the pipeline 527 15 Working with relational databases 530 15.1 Setting up an example 531 Sample database 531 ■ Sample queries 533 ■ Data representation in Haskell 535 15.2 Haskell database connectivity 537 Connecting to a database 537 ■ Relating Haskell data types to database types 538 ■ Constructing and executing SELECT queries 539 ■ Manipulating data in a database 541 Solving tasks by issuing many queries 542 15.3 The postgresql-simple library 544 Connecting to a database 544 ■ Relating Haskell data types to database types 544 ■ Executing queries 545

CONTENTS xiii 15.4 The hasql ecosystem 547 Structuring programs with hasql 547 ■ Constructing type-safe SQL statements 548 ■ Implementing database sessions 552 Running database sessions 553 ■ The need for low-level operations and decoding data manually 554 15.5 Generating SQL with opaleye 556 Structuring programs with opaleye 556 ■ Describing database tables and their fields 557 ■ Writing queries 562 ■ Running queries 564 16 Concurrency 567 16.1 Running computations concurrently 568 An implementation of concurrency in GHC 568 ■ Low-level concurrency with threads 569 ■ High-level concurrency with the async package 577 16.2 Synchronization and communication 584 Synchronized mutable variables and channels 585 ■ Software transactional memory (STM) 592 appendix Further reading 603 index 605

xv foreword Many introductory books on Haskell are out there, as well as lots of online tutorials, so the first steps in learning Haskell are readily available. But what happens after that? Haskell has a low “floor” (anyone can learn elementary Haskell) but a stratospheri- cally high “ceiling.” Haskell is a uniquely malleable medium: its support for abstrac- tion, thorough algebraic data types, higher kinds, type classes, type families, and so on is remarkable. But this power and flexibility can be daunting. What are we to make of the following: traverse :: Applicative f => (a -> f b) -> t a -> f (t b) What are f and t? What on earth does this function do? What is Applicative, anyway? It’s all too abstract! Becoming a power user of Haskell means getting a grip on abstractions like these, not as a piece of theory, but as living, breathing code that does remarkably useful stuff. As we learn these abstractions and see how they work, we realise they are not baked in—they are just libraries—so we can build new abstractions of our own, implemented in libraries. This book exposes you to many of these techniques. It covers many of the more sophisticated parts of the language: not just type classes, but existentials, GADTs, type families, kinds and kind polymorphism, deriving, metaprogramming, and so on. It describes many of the key abstractions (Functor, Applicative, Traversable, etc.) and a carefully chosen set of libraries (for parsing, database, web frameworks, stream- ing, and data-type-generic programming). As well as being useful in their own right,

FOREWORDxvi each part illustrates in a concrete way how Haskell’s features can be combined in pow- erful and unexpected ways. Finally, the book covers aspects of software engineering. How do you design a func- tional program? How do you test it? How do you benchmark it? What error handling is appropriate? These classic issues show up in rather different guises when you are thinking about functional programming. Functional programming lets you think “big thoughts.” It reduces the brain-to- code distance by allowing you to program at a very high level. We are still learning what those high-level abstractions should be. This book will help put you in the van- guard of that journey. SIMON PEYTON JONES, SENIOR PRINCIPAL RESEARCHER AT MICROSOFT RESEARCH, CAMBRIDGE, ENGLAND

xvii preface The history of Haskell started more than 30 years ago, in 1987 (see “A History of Haskell: Being Lazy with Class” at https://www.microsoft.com/en-us/research/publication/ a-history-of-haskell-being-lazy-with-class/ for many exciting details). Nowadays, Haskell is a mature programming language. It is full of features and has a stable implementation, the Glasgow Haskell Compiler, a helpful and friendly community, and a big ecosystem. Paraphrasing the Haskell 2010 Language Report (https://www.haskell.org/ onlinereport/haskell2010/), which is an effective standard description of the Haskell language, we can give it the following definition. Haskell is a general-purpose, purely functional programming language fea- turing higher-order functions, nonstrict semantics, static polymorphic typing, user-defined algebraic data types, pattern matching, a module system, a monadic I/O system, and a rich set of primitive data types (including lists, arrays, arbitrary- and fixed-precision integers, and floating-point numbers). This definition is feature centric but gives a little information about how to use all these features professionally. Haskell is by far not the most popular programming language in the world, however. Two unfortunate myths contribute a lot to its limited adoption: ■ It is hopeless to program in Haskell without a PhD in math. ■ Haskell is not ready/suitable for production. I believe that both of these claims are false. In fact, we can use Haskell in production without learning and doing math by ourselves. The truth is that the deep mathemati- cal concepts behind the language itself give us a tool that can be used to write flexible,

PREFACExviii expressive, and performant code that is resilient to frequent changes in requirements, well suited to massive refactoring, and less prone to mistakes. If you like these software qualities, then Haskell is definitely for you and your team. When talking about any programming language in general and its use in industry, we usually discuss the following components: ■ Language features, programming style, and how they affect one another ■ The set of libraries (packages) available to developers and their distribution ■ The tooling that forms a convenient programming environment Figure 1 presents these components for the Haskell programming language. They form a language ecosystem and make building software for the real world possible. This is precisely what I talk about in this book: what Haskell is nowadays with respect to the language itself, the tooling around it, the libraries available to get things done, and the programming styles (sometimes known as best practices) supported. The Haskell definition mentions three of the most valuable Haskell features, namely: ■ Support for functional programming ■ Static polymorphic typing ■ Nonstrict semantics (more often referred to as lazy evaluation) These Haskell features greatly affect the programming style of Haskellers, who write programs by exploiting functional style with higher-order functions and various manipulations over functions. They use Haskell’s type system to express their inten- tions about data and functions. They count on laziness to write clear code without los- ing performance guarantees. Let’s review these three features in general and then talk about the other Haskell ecosystem components. Libraries OS distributions Stackage Hackage Lazy evaluation Haskell platformStackCabal Tooling Glasgow Haskell compiler Development environment, CI, and other services Language features and programming style Haskell language Functional programming Static typing with type inference Figure 1 Haskell ecosystem