Alejandro Serrano Mena - Practical Haskell: A Real-World Guide to Functional Programming

Practical Haskell

A Real-World Guide to Functional

Programming

Third Edition

Alejandro Serrano Mena

Practical Haskell: A Real-World Guide to Functional Programming

Alejandro Serrano Mena

Utrecht, The Netherlands

ISBN-13 (pbk): 978-1-4842-8580-0

ISBN-13 (electronic): 978-1-4842-8581-7

https://doi.org/10.1007/978-1-4842-8581-7

Copyright 2022 by Alejandro Serrano Mena

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed.

Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.

While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein.

Managing Director, Apress Media LLC: Welmoed Spahr

Acquisitions Editor: Steve Anglin

Development Editor: James Markham

Coordinating Editor: Gryffin Winkler

Cover designed by eStudioCalamar

Cover image by Shubham Dhage on Unsplash (www.unsplash.com)

Distributed to the book trade worldwide by Apress Media, LLC, 1 New York Plaza, New York, NY 10004, U.S.A. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail orders-ny@springer-sbm.com, or visit www.

springeronline.com. Apress Media, LLC is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation.

For information on translations, please e-mail booktranslations@springernature.com; for reprint, paperback, or audio rights, please e-mail bookpermissions@springernature.com.

Apress titles may be purchased in bulk for academic, corporate, or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Print and eBook Bulk Sales web page at http://www.apress.com/bulk-sales.

Any source code or other supplementary material referenced by the author in this book is available to readers on GitHub (https://github.com/Apress). For more detailed information, please visit http://www.

apress.com/source-code.

Printed on acid-free paper

To Elena, and my two boys Quique and Julio,

who bring me joy every single day.

Table of Contents

About the Author xv About the Technical Reviewer xvii Acknowledgments xix Introduction xxi Part I: First Steps 1

Chapter 1: Going Functional 3

Why Haskell? 3

Why Pure Functional Programming? 4

Why Strong Static Typing? 6

The Haskell Ecosystem 7

The History of Haskell 8

Your Working Environment 9

First Steps with GHCi 10

The Time Machine Store 13

Summary 14

Chapter 2: Declaring the Data Model 15

Characters, Numbers, and Lists 15

Characters 16

Numbers 17

Strings 19

Lists 20

Creating a New Project 25

Creating a Project with Cabal 25

Creating a Project with Stack 27

v

Table of ConTenTs

Understanding Modules 29

Cabal and Stack 31

Defining Simple Functions 32

Creating a Simple Function 32

Specifying the Functions Type 33

Developing a Robust Example 33

Returning More Than One Value 36

Working with Data Types 38

Pattern Matching 43

Records 54

Summary 60

Chapter 3: Increasing Code Reuse 63

Parametric Polymorphism 64

Functions As Parameters 67

Higher-Order Functions 68

Anonymous Functions 70

Partial Application of a Function 72

More on Modules 76

Module Imports 77

Smart Constructors and Views 79

Diving into Lists 82

Folds 82

Lists and Predicates 87

Lists Containing Tuples 94

List Comprehensions 96

Haskell Origami 101

Summary 106

vi

Table of ConTenTs

Chapter 4: Using Containers and Type Classes 107

Using Packages 107

Managing Dependencies 108

Building Packages 111

Obtaining Help 116

Containers: Maps, Sets, Trees, Graphs 116

Maps 117

Sets 122

Trees 124

Graphs 127

Ad Hoc Polymorphism: Type Classes 130

Declaring Classes and Instances 130

Built-In Type Classes 135

Binary Trees for the Minimum Price 141

Step 1: Simple Binary Trees 141

Step 2: Polymorphic Binary Trees 143

Step 3: Binary Trees with Monoidal Cache 145

Container-Related Type Classes 148

Functors 148

Foldables 151

Summary 153

Chapter 5: Laziness and Infinite Structures 155

An Infinite Number of Time Machines 156

Lazy Evaluation Model 161

Understanding Evaluation in Haskell 161

Problems with Laziness 166

Pattern Matching and Laziness 169

Profiling with GHC 172

Strictness Annotations 177

Summary 180

vii

Table of ConTenTs

Part II: Data Mining 183

Chapter 6: Knowing Your Clients Using Monads 185

Data Mining 186

Implementing K-means 186

Lenses 193

Discovering Monads 202

Watching Out for Incomplete Data 202

Combinators for State 205

Dissecting the Combinators 209

do Notation 211

Monad Laws 215

Different Sorts of State 217

State and Lenses 217

Reader, Writer, and RWS 219

Mutable References with ST 224

Summary 226

Chapter 7: More Monads: Now for Recommendations 229

Returning More Than One Value 230

The List Monad 230

A New View over Monads 232

Failures and Alternatives 233

Association Rule Learning 237

Flattening Values into Transactions 238

The Apriori Algorithm 241

Search Problems 246

Paths in a Graph 247

The Logic Monad 248

Monads and Lists, Redux 251

Combining Values Under a Monad 252

Monad Comprehensions 255

viii

Table of ConTenTs

Combining Monads 259

Monad Transformers 260

Monad Classes 264

Summary 267

Chapter 8: Working in Several Cores 269

Parallelism, Concurrency, and Distribution 269

The Par Monad 271

Futures 272

Dataflow Parallelism with IVars 275

Parallelizing the Apriori Algorithm 277

Software Transactional Memory 280

Concurrent Use of Resources 280

Atomic Transactions 283

Rolling Back Transactions 286

Producer-Consumer Queues 288

Single-Process Queues 289

Message Queues Using AMQP 291

AMQP in Haskell 293

Summary 297

Part III: Resource Handling 299

Chapter 9: Dealing with Files: IO and Conduit 301

Basic Input and Output 301

Randomness 307

Working with Files 310