程序代写CS代考 python data structure javascript compiler Java Haskell algorithm PRAISE FOR LEARN YOU A HASKELL FOR GREAT GOOD! – cscodehelp代写

PRAISE FOR LEARN YOU A HASKELL FOR GREAT GOOD!
“The thing that’s most impressive about Learn You a Haskell for Great Good! is how well written it is. This book is just fantastic.”
—GREGORY COLLINS, GOOGLE SWITZERLAND
“Managed to walk me through all important Haskell concepts without ever making any of the material sound complicated. A good introduction to functional programming.”
—MARIJN HAVERBEKE, AUTHOR OF ELOQUENT JAVASCRIPT
“This is a fantastic book and I highly recommend it as the first book on Haskell—and possibly even the second.”
—MICHAEL FOGUS, AUTHOR OF THE JOY OF CLOJURE
“A fantastic, fun, thorough introduction to Haskell, spiced up by Miran’s great sense of humor and zany illustrations.”
—BRENT YORGEY, THE MATH LESS TRAVELED
“ has done a fantastic job of writing a book aimed at beginning Haskell programmers. I like his very straightforward writing style of introducing each topic with the minimum of complexity.” —BRYAN BELL, MATH AND MORE
“This is a remarkable book and may be just what this beautiful language was missing.”
—MICHAEL KOHL, CITIZEN428
“The best way I know to obtain the Haskell foundation you need for fluency.” —JEREMY BOWERS, JERF.ORG
“A terrific book. It takes what might otherwise seem impenetrable mathy- code and makes it fun and approachable.”
—SIMON REYNOLDS

Learn You a
Haskell for
Great Good! A Beginner’s Guide
ˇ a
San Francisco

LEARN YOU A HASKELL FOR GREAT GOOD! Copyright © 2011 ˇa
All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher.
Twelfth printing
23 22 21 20 12 13 14 15
ISBN-10: 1-59327-283-9 ISBN-13: 978-1-59327-283-8
Publisher:
Production Editors: and Cover and Interior Design: Octopod Studios Developmental Editor:
Technical Reviewer:
Copyeditor:
Compositor:
Proofreader:
Indexer: information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly:
No Starch Press, Inc.
245 8th Street, San Francisco, CA 94103
phone: 1.415.863.9900; www.nostarch.com
Library of Congress Cataloging-in-Publication Data
Lipovaca, Miran.
Learn you a Haskell for great good! : a beginner’s guide / by .
p. cm.
ISBN-13: 978-1-59327-283-8
ISBN-10: 1-59327-283-9
1. Haskell (Computer program language) I. Title. QA76.73.H37L69 2012
005.1’3-dc22
2011000790
No Starch Press and the No Starch Press logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark.
The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the infor- mation contained in it.

BRIEF CONTENTS
Introduction ………………………………………………………………. xv Chapter 1: Starting Out …………………………………………………….. 1 Chapter 2: Believe the Type …………………………………………………. 23 Chapter 3: Syntax in Functions……………………………………………….. 35 Chapter 4: Hello Recursion! …………………………………………………. 51 Chapter 5: Higher-Order Functions ……………………………………………. 59 Chapter 6: Modules ……………………………………………………….. 87 Chapter 7: Making Our Own Types and Type Classes …………………………….109 Chapter 8: Input and Output………………………………………………….153 Chapter 9: More Input and More Output………………………………………..169 Chapter 10: Functionally Solving Problems ………………………………………203 Chapter 11: ………………………………………………217 Chapter 12: Monoids……………………………………………………….243 Chapter 13: A Fistful of Monads ………………………………………………267 Chapter 14: For a Few Monads More ………………………………………….297 Chapter 15: Zippers ………………………………………………………..343 Index…………………………………………………………………….363

CONTENTS IN DETAIL
INTRODUCTION xv
So, What’s Haskell? …………………………………………………….. xv What You Need to Dive In ……………………………………………….. xvii Acknowledgments ………………………………………………………. xviii
1
STARTING OUT 1
Calling Functions ……………………………………………………….. 3 Baby’s First Functions ……………………………………………………. 5 An Intro to Lists…………………………………………………………. 7
Concatenation………………………………………………….. 8 Accessing List Elements …………………………………………… 9 Lists Inside Lists …………………………………………………. 9 Comparing Lists ………………………………………………… 9 More List Operations …………………………………………….. 10
Texas Ranges ………………………………………………………….. 13 I’m a List Comprehension…………………………………………………. 15 Tuples………………………………………………………………… 18
Using Tuples……………………………………………………. 19 UsingPairs…………………………………………………….. 20 Finding the Right Triangle…………………………………………. 21
2
BELIEVE THE TYPE 23
Explicit Type Declaration …………………………………………………. 24 Common Haskell Types ………………………………………………….. 25 TypeVariables…………………………………………………………. 26 Type Classes 101 ………………………………………………………. 27
The Eq Type Class ………………………………………………. 28 The Ord Type Class ……………………………………………… 28 The Show Type Class…………………………………………….. 29 The Read Type Class …………………………………………….. 29 The Enum Type Class…………………………………………….. 31 The Bounded Type Class………………………………………….. 31 The Num Type Class …………………………………………….. 32 The Floating Type Class ………………………………………….. 32 The Integral Type Class…………………………………………… 33 Some Final Notes on Type Classes …………………………………. 33

3
SYNTAX IN FUNCTIONS 35
Pattern Matching ……………………………………………………….. 35 Pattern Matching with Tuples………………………………………. 37 Pattern Matching with Lists and List Comprehensions……………………. 38 As-patterns …………………………………………………….. 40
Guards, Guards! ……………………………………………………….. 40 where?! ………………………………………………………………. 42 where’s Scope………………………………………………….. 44 Pattern Matching with where ………………………………………. 44 Functions in where Blocks…………………………………………. 45 letItBe……………………………………………………………….. 45 let in List Comprehensions ………………………………………… 47 let in GHCi…………………………………………………….. 47 case Expressions ……………………………………………………….. 48
4
HELLO RECURSION! 51
Maximum Awesome …………………………………………………….. 52 A Few More Recursive Functions …………………………………………… 53 replicate ………………………………………………………. 53 take ………………………………………………………….. 54 reverse………………………………………………………… 55 repeat ………………………………………………………… 55 zip …………………………………………………………… 55 elem………………………………………………………….. 56 Quick, Sort! …………………………………………………………… 56 The Algorithm ………………………………………………….. 56 The Code ……………………………………………………… 57 Thinking Recursively …………………………………………………….. 58
5
HIGHER-ORDER FUNCTIONS 59
Curried Functions……………………………………………………….. 59 Sections……………………………………………………….. 62 Printing Functions ……………………………………………….. 63
Some Higher-Orderism Is in Order …………………………………………. 63 Implementing zipWith ……………………………………………. 64 Implementing flip ……………………………………………….. 65
The Functional Programmer’s Toolbox ………………………………………. 66 The map Function ……………………………………………….. 66 The filter Function ……………………………………………….. 67 More Examples of map and filter …………………………………… 68 Mapping Functions with Multiple Parameters …………………………. 70
Lambdas ……………………………………………………………… 71 viii Contents in Detail

I Fold You So ………………………………………………………….. 73 Left Folds with foldl………………………………………………. 74 Right Folds with foldr …………………………………………….. 75 The foldl and foldr1 Functions ……………………………………… 76 Some Fold Examples …………………………………………….. 76 Another Way to Look at Folds……………………………………… 77 Folding Infinite Lists ……………………………………………… 78 Scans…………………………………………………………. 79
Function Application with $ ………………………………………………. 80 FunctionComposition……………………………………………………. 82 Function Composition with Multiple Parameters ……………………….. 83 Point-Free Style …………………………………………………. 84
6
MODULES 87
Importing Modules ……………………………………………………… 88 Solving Problems with Module Functions …………………………………….. 90 CountingWords………………………………………………… 90 Needle in the Haystack…………………………………………… 91 Salad…………………………………………….. 92 On Strict Left Folds ………………………………………………. 94 Let’s Find Some Cool Numbers …………………………………….. 95 Mapping Keys to Values …………………………………………………. 98 Almost As Good: Association Lists ………………………………….. 98
Enter Data.Map ………………………………………………… 100 Making Our Own Modules……………………………………………….. 104 A Geometry Module …………………………………………….. 104 Hierarchical Modules ……………………………………………. 106
7
MAKING OUR OWN TYPES AND TYPE CLASSES 109
Defining a Type ……………………………………………….. 109 Shaping Up……………………………………………………………. 110 Improving Shape with the Point Data Type……………………………. 112 Exporting Our Shapes in a Module …………………………………. 113 Record Syntax …………………………………………………………. 114 Type Parameters ……………………………………………………….. 117 Should We Parameterize Our Car?…………………………………. 119 Vector von Doom ……………………………………………….. 121 Derived Instances……………………………………………………….. 122 Equating People ………………………………………………… 123 Show Me How to Read…………………………………………… 124 Order in the Court! ……………………………………………… 125 Any Day of the Week ……………………………………………. 126
Contents in Detail ix

Type Synonyms ………………………………………………………… 127 Making Our Phonebook Prettier ……………………………………. 128 Parameterizing Type Synonyms ……………………………………. 129 Go Left, Then Right………………………………………………. 130
Recursive Data Structures…………………………………………………. 132 Improving Our List ………………………………………………. 133 Let’s Plant a Tree………………………………………………… 135
Type Classes 102 ………………………………………………………. 138 Inside the Eq Type Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 A Traffic Light Data Type …………………………………………. 139 Subclassing ……………………………………………………. 140 Parameterized Types As Instances of Type Classes …………………….. 141
A Yes-No Type Class ……………………………………………………. 143 The Functor Type Class…………………………………………………… 146 Maybe As a Functor …………………………………………….. 147 Trees Are Functors, Too…………………………………………… 148 Either a As a Functor …………………………………………….. 149 Kinds and Some Type-Foo………………………………………………… 150
8
INPUT AND OUTPUT 153
Separating the Pure from the Impure………………………………………… 153 Hello, World! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Gluing I/O Actions Together ……………………………………………… 156
Using let Inside I/O Actions……………………………………….. 158
Putting It in Reverse ……………………………………………… 159 Some Useful I/O Functions ……………………………………………….. 161 putStr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 putChar……………………………………………………….. 162 print . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 when ………………………………………………………….163 sequence ……………………………………………………… 164 mapM …………………………………………………………165 forever………………………………………………………… 165 forM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 I/O Action Review ……………………………………………………… 167
9
MORE INPUT AND MORE OUTPUT 169
Files and Streams……………………………………………………….. 169 Input Redirection………………………………………………… 170 Getting Strings from Input Streams ………………………………….. 171 Transforming Input ………………………………………………. 173
x Contents in Detail

Reading and Writing Files………………………………………………… 175 Using the withFile Function………………………………………… 177 It’s Bracket Time ………………………………………………… 178 Grab the Handles! ………………………………………………. 179
To-Do Lists …………………………………………………………….. 180 Deleting Items ………………………………………………….. 181 Cleaning Up …………………………………………………… 183
Command-Line Arguments………………………………………………… 184 More Fun with To-Do Lists ………………………………………………… 185 A Multitasking Task List …………………………………………… 186 Dealing with Bad Input …………………………………………… 190 Randomness …………………………………………………………… 190 Tossing a Coin …………………………………………………. 193 More Random Functions ………………………………………….. 194 Randomness and I/O ……………………………………………. 195 Bytestrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 Strict and Lazy Bytestrings ………………………………………… 199 Copying Files with Bytestrings ……………………………………… 201
10
FUNCTIONALLY SOLVING PROBLEMS 203
Reverse Polish Notation Calculator …………………………………………. 203 Calculating RPN Expressions ………………………………………. 204 Writing an RPN Function …………………………………………. 205 Adding More Operators………………………………………….. 207
Heathrow to London …………………………………………………….. 208 Calculating the Quickest Path ……………………………………… 209 Representing the Road System in Haskell …………………………….. 211 Writing the Optimal Path Function ………………………………….. 212 Getting a Road System from the Input ……………………………….. 215
11
APPLICATIVE FUNCTORS 217
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 I/O Actions As Functors ………………………………………….. 218 Functions As Functors…………………………………………….. 220
Functor Laws…………………………………………………………… 223 Law1 …………………………………………………………223 Law2 …………………………………………………………224 Breaking the Law ……………………………………………….. 225
Using ……………………………………………….. 227 Say Hello to Applicative ………………………………………….. 228 Maybe the Applicative Functor …………………………………….. 229 The Applicative Style …………………………………………….. 230
Contents in Detail xi

Lists …………………………………………………………..232 IO Is An Applicative Functor, Too…………………………………… 234 Functions As Applicatives …………………………………………. 235 Zip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Applicative Laws………………………………………………… 238
Useful Functions for Applicatives …………………………………………… 238 12
MONOIDS 243
Wrapping an Existing Type into a ………………………………… 243 Using newtype to Make Type Class Instances …………………………. 246 On newtype Laziness…………………………………………….. 247 type vs. newtype vs. data ………………………………………… 249
About Those Monoids……………………………………………………. 250 The Monoid Type Class ………………………………………….. 252 The Monoid Laws ……………………………………………….. 253
Meet Some Monoids…………………………………………………….. 253 Lists Are Monoids ……………………………………………….. 253 Product and Sum………………………………………………… 254 Any and All ……………………………………………………. 256 The Ordering Monoid ……………………………………………. 257 Maybe the Monoid ……………………………………………… 260
Folding with Monoids……………………………………………………. 262 13
A FISTFUL OF MONADS 267
Upgrading Our ……………………………………….. 267 Getting Your Feet Wet with Maybe ………………………………………… 269 The Monad Type Class ………………………………………………….. 272 Walk the Line ………………………………………………………….. 274
Code, Code, Code ……………………………………………… 274 I’ll Fly Away……………………………………………………. 276 Banana on a Wire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
do Notation …………………………………………………………… 280 Do As I Do . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 …………………………………………………… 282 Pattern Matching and Failure………………………………………. 284
The List Monad…………………………………………………………. 285 do Notation and List Comprehensions……………………………….. 288 MonadPlus and the guard Function …………………………………. 288 A Knight’s Quest………………………………………………… 290
Monad Laws…………………………………………………………… 292 Left Identity …………………………………………………….. 293 Right Identity …………………………………………………… 294 Associativity……………………………………………………. 294
xii Contents in Detail

14
FOR A FEW MONADS MORE 297
Writer? I Hardly Knew Her! ………………………………………………. 298 Monoids to the Rescue …………………………………………… 300 The Writer Type ………………………………………………… 302 Using do Notation with Writer …………………………………….. 303 Adding Logging to Programs………………………………………. 304 Inefficient List Construction ………………………………………… 306 Using Difference Lists…………………………………………….. 307 Comparing Performance………………………………………….. 309
Reader? Ugh, Not This Joke Again…………………………………………. 310 Functions As Monads…………………………………………….. 311 The Reader Monad ……………………………………………… 312
Tasteful Stateful Computations …………………………………………….. 313 Stateful Computations ……………………………………………. 314 Stacks and Stones……………………………………………….. 314 The State Monad ……………………………………………….. 316 Getting and Setting State …………………………………………. 318 Randomness and the State Monad………………………………….. 320
Error Error on the Wall…………………………………………………… 321 Some Useful Monadic Functions …………………………………………… 323 liftM and Friends………………………………………………… 323 The join Function………………………………………………… 326 filterM ………………………………………………………… 328 foldM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 Making a Safe RPN Calculator ……………………………………………. 332 Composing Monadic Functions ……………………………………………. 335 Making Monads ……………………………………………………….. 336
15
ZIPPERS 343
Taking a Walk …………………………………………………………. 344 A Trail of Breadcrumbs …………………………………………… 346 Going Back Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Manipulating Trees Under Focus …………………………………… 350 Going Straight to the Top, Where the Air Is Fresh and Clean! ……………. 351
Focusing on Lists ……………………………………………………….. 352 A Very Simple Filesystem…………………………………………………. 353 Making a Zipper for Our Filesystem ………………………………… 355 Manipulating a Filesystem ………………………………………… 357 Watch Your Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 Thanks for Reading! …………………………………………………….. 360
INDEX 363
Contents in Detail xiii

INTRODUCTION
Haskell is fun, and that’s what it’s all about!
This book is aimed at people who have experience programming in im- perative languages—such as C++, Java, and Python—and now want to try out Haskell. But even if you don’t have any significant programming experience, I’ll bet a smart person like you will be able to follow along and learn Haskell.
My first reaction to Haskell was that the language was just too weird. But after getting over that initial hurdle, it was smooth sailing. Even if Haskell seems strange to you at first, don’t give up. Learning Haskell is almost like learning to program for the first time all over again. It’s fun, and it forces you to think differently.
NOTE If you ever get really stuck, the IRC channel #haskell on the freenode network is a great place to ask questions. The people there tend to be nice, patient, and understand- ing. They’re a great resource for Haskell newbies.
So, What’s Haskell?
Haskell is a purely functional programming language.
In imperative programming languages, you give the computer a sequence
of tasks, which it then executes. While executing them, the computer can change state. For instance, you can set the variable a to 5 and then do some stuff that might change the value of a. There are also flow-control structures for executing instructions several times, such as for and while loops.

Purely functional programming is differ- ent. You don’t tell the computer what to do— you tell it what stuff is. For instance, you can tell the computer that the factorial of a number
is the product of every integer from 1 to that number or that the sum of a list of numbers is the first number plus the sum of the remaining numbers. You can express both of these opera- tions as functions.
In functional programming, you can’t set a
variable to one value and then set it to some-
thing else later on. If you say a is 5, you can’t just change your mind and
say it’s something else. After all, you said it was 5. (What are you, some kind of liar?)
In purely functional languages, a function has no side effects. The only thing a function can do is calculate something and return the result. At
first, this seems limiting, but it actually has some very nice consequences. If a function is called twice with the same parameters, it’s guaranteed to return the same result both times. This property is called referential transparency. It lets the programmer easily deduce (and even prove) that a function is cor- rect. You can then build more complex functions by gluing these simple functions together.
Haskell is lazy. This means that
unless specifically told otherwise,
Haskell won’t execute functions
until it needs to show you a result.
This is made possible by referential
transparency. If you know that the
result of a function depends only
on the parameters that function is
given, it doesn’t matter when you
actually calculate the result of the
function. Haskell, being a lazy lan-
guage, takes advantage of this fact
and defers actually computing re-
sults for as long as possible. Once
you want your results to be displayed, Haskell will do just the bare minimum computation required to display them. Laziness also allows you to make seemingly infinite data structures, because only the parts of the data struc- tures that you choose to display will actually be computed.
Let’s look at an example of Haskell’s laziness. Say you have a list of num- bers, xs = [1,2,3,4,5,6,7,8], and a function called doubleMe that doubles every element and returns the result as a new list. If you want to multiply your list by 8, your code might look something like this:
doubleMe(doubleMe(doubleMe(xs)))
xvi Introduction

An imperative language would probably pass through the list once, make a copy, and then return it. It would then pass through the list another two times, making copies each time, and return the result.
In a lazy language, calling doubleMe on a list without forcing it to show you the result just makes the program tell you, “Yeah yeah, I’ll do it later!” Once you want to see the result, the first doubleMe calls the second one and says it wants the result immediately. Then the second one says the same thing to the third one, and the third one reluctantly gives back a doubled
1, which is 2. The second doubleMe receives that and returns 4 to the first one. The first doubleMe then doubles this result and tells you that the first ele- ment in the final resulting list is 8. Because of Haskell’s laziness, the doubleMe calls pass through the list just once, and only when you really need that to happen.
Haskell is statically typed. This means that when you compile your program, the compiler knows which piece of code is a number, which is a string, and so on. Static typing means that a lot of possible errors can be caught at compile time. If you try to add together a number and
a string, for example, the compiler will whine at you.
Haskell uses a very good type system that
has type inference. This means that you don’t
need to explicitly label every piece of code with a type, because Haskell’s type system can intelligently figure it out. For example, if you say a = 5 + 4, you don’t need to tell Haskell that a is a number—it can figure that out by itself. Type inference makes it easier for you to write code that’s more gen- eral. If you write a function that takes two parameters and adds them to- gether, but you don’t explicitly state their type, the function will work on any two parameters that act like numbers.
Haskell is elegant and concise. Because it uses a lot of high-level con- cepts, Haskell programs are usually shorter than their imperative equiva- lents. Shorter programs are easier to maintain and have fewer bugs.
Haskell was made by some really smart guys (with PhDs). Work on Haskell began in 1987 when a committee of researchers got together to design a kick-ass language. The Haskell Report, which defines a stable ver- sion of the language, was published in 1999.
What You Need to Dive In
In short, to get started with Haskell, you need a text editor and a Haskell compiler. You probably already have your favorite text editor installed, so we won’t waste time on that. The most popular Haskell compiler is the Glasgow Haskell Compiler (GHC), which we will be using throughout this book.
The best way to get what you need is to download the . The includes not only the GHC compiler but also a bunch of useful Haskell libraries! To get the for your system, go to
Introduction xvii

xviii
Introduction
http://hackage.haskell.org/platform/ and follow the instructions for your oper- ating system. Make sure to choose the full installer.
GHC can compile Haskell scripts (usually with an .hs extension), and
it also has an interactive mode. From there, you can load functions from scripts and then call them directly to see immediate results. Especially when you’re learning, it’s much easier to use the interactive mode than it is to compile and run your code every time you make a change.
Once you’ve installed the , open a new terminal win- dow, assuming you’re on a Linux or Mac OS X system. If your operating sys- tem of choice is Windows, go to the command prompt. Once there, type ghci and press ENTER to start the interactive mode. (If your system fails to find the GHCi program, you can try rebooting your computer.)
If you’ve defined some functions in a script—for example, myfunctions.hs— you can load these functions into GHCi by typing :l myfunctions. (Make sure that myfunctions.hs is in the same folder from which you started GHCi.)
If you change the .hs script, run :l myfunctions to load the file again or run :r, which reloads the current script. My usual workflow is to define some functions in an .hs file, load it into GHCi, mess around with it, change the file, and repeat. This is what we’ll be doing in this book.
Acknowledgments
Thanks to everyone who sent in corrections, suggestions, and words of en- couragement. Also thanks to Keith, Sam, and Marilyn for making me look like a real writer.

1
STARTING OUT
If you’re the horrible sort of person who doesn’t read introductions, you might want to go back and read the last section anyway—it explains how to use this book, as well as how to load functions with GHC.
First, let’s start GHC’s interactive mode and call some functions, so we can get a very basic feel for Haskell. Open a terminal and type ghci. You will be greeted with something like this:
GHCi, version 8.0.1: http://www.haskell.org/ghc/ 😕 for help
Prelude>
NOTE GHCi’s default prompt is Prelude>, but we’ll be using ghci> as our prompt for the ex- amples in this book. To make your prompt match the book’s, enter :set prompt “ghci> ” into GHCi. If you don’t want to do this every time you run GHCi, create a file called .ghci in your home folder and set its contents to :set prompt “ghci> “.

Congratulations, you’re in GHCi! Now let’s try some simple arithmetic:
ghci> 2 + 15
17
ghci> 49 * 100
4900
ghci> 1892 – 1472
420
ghci> 5 / 2
2.5
ghci> (50 * 100) – 4999
1
ghci> 50 * 100 – 4999
1
ghci> 50 * (100 – 4999)
-244950
If we use several operators in one expression, Haskell will execute them in an order that takes into account the precedence of the operators. For instance, * has higher precedence than -, so 50 * 100 – 4999 is treated as (50 * 100) – 4999.
We can also use parentheses to explicitly specify the order of operations, like this:
Pretty cool, huh? (Yeah, I know it’s not, yet, but bear with me.)
One pitfall to watch out for is negative number constants. It’s always best to surround these with parentheses wherever they occur in an arith- metic expression. For example, entering 5 * -3 will make GHCi yell at you, but entering 5 * (-3) will work just fine.
Boolean algebra is also straightforward in Haskell. Like many other pro- gramming languages, Haskell has the Boolean values True and False, and uses the && operator for conjunction (Boolean and), the || operator for dis- junction (Boolean or ), and the not operator to negate a True or False value:
ghci> True && False
False
ghci> True && True
True
ghci> False || True
True
ghci> not False
True
ghci> not (True && True)
False
2 Chapter 1

We can test two values for equality or inequality with the == and /= opera- tors, like this:
ghci> 5 == 5
True
ghci> 1 == 0
False
ghci> 5 /= 5
False
ghci> 5 /= 4
True
ghci> “hello” == “hello”
True
Watch out when mixing and matching values, however! If we enter some- thing like 5 + “llama”, we get the following error message:
No instance for (Num [Char]) arising from the use of `+’
In the expression: 5 + “llama”
In an equation for `it’: it = 5 + “llama”
What GHCi is telling us here is that “llama” is not a number, so it does not know how to add it to 5. The + operator expects both of its inputs to be numbers.
On the other hand, the == operator works on any two items that can be compared, with one catch: they both have to be of the same type. For instance, if we tried entering True == 5, GHCi would complain.
NOTE 5 + 4.0 is a valid expression, because although 4.0 isn’t an integer, 5 is sneaky and can act like either an integer or a floating-point number. In this case, 5 adapts to match the type of the floating-point value 4.0.
We’ll take a closer look at types a bit later.
Calling Functions
You may not have realized it, but we’ve actually been using functions this whole time. For in- stance, * is a function that takes two numbers and multiplies them. As you’ve seen, we apply (or call) it by sandwiching it between the two numbers we want to multiply. This is called an infix function.
Most functions, however, are prefix func- tions. When calling prefix functions in Haskell, the function name comes first, then a space,
Starting Out 3

then its parameters (also separated by spaces). As an example, we’ll try call- ing one of the most boring functions in Haskell, succ:
ghci> succ 8 9
The succ function takes one parameter that can be anything that has a well-defined successor, and returns that value. The successor of an integer value is just the next higher number.
Now let’s call two prefix functions that take multiple parameters, min and max:
ghci> min 9 10
9
ghci> min 3.4 3.2
3.2
ghci> max 100 101
101
The min and max functions each take two parameters that can be put in some order (like numbers!), and they return the one that’s smaller or larger, respectively.
Function application has the highest precedence of all the operations in Haskell. In other words, these two statements are equivalent.
ghci> succ 9 + max 5 4 + 1
16
ghci> (succ 9) + (max 5 4) + 1
16
This means that if we want to get the successor of 9 * 10, we couldn’t simply write
ghci> succ 9 * 10
Because of the precedence of operations, this would evaluate as the suc- cessor of 9 (which is 10) multiplied by 10, yielding 100. To get the result we want, we need to instead enter
ghci> succ (9 * 10)
This returns 91.
If a function takes two parameters, we can also call it as an infix function by surrounding its name with backticks (`). For instance, the div function takes two integers and executes an integral division, as follows:
ghci> div 92 10
9
4 Chapter 1

However, when we call it like that, there may be some confusion as to which number is being divided by which. By using backticks, we can call it as an infix function, and suddenly it seems much clearer:
ghci> 92 `div` 10
9
Many programmers who are used to imperative languages tend to stick to the notion that parentheses should denote function application, and they have trouble adjusting to the Haskell way of doing things. Just remember,
if you see something like bar (bar 3), it means that we’re first calling the bar function with 3 as the parameter, then passing that result to the bar function again. The equivalent expression in C would be something like bar(bar(3)).
Baby’s First Functions
ghci> :l baby
[1 of 1] Compiling Main
Ok, modules loaded: Main.
ghci> doubleMe 9
18
ghci> doubleMe 8.3
16.6
The syntax of a function definition is similar
to that of a function call: the function name is followed by parameters, which are separated by spaces. But then the parameter list is followed by the = operator, and the code that makes up the body of the function follows that.
As an example, we’ll write a simple func- tion that takes a number and multiplies it by two. Open up your favorite text editor and type in the following:
doubleMe x = x + x
Save this file as baby.hs. Now run ghci, mak- ing sure that baby.hs is in your current directory. Once in GHCi, enter :l baby to load the file. Now we can play with our new function:
( baby.hs, interpreted )
Because + works on integers as well as on floating point numbers (in- deed, on anything that can be considered a number), our function also works with any of these types.
Starting Out 5

Now let’s make a function that takes two numbers, multiplies each by two, then adds them together. Append the following code to baby.hs:
doubleUs x y = x * 2 + y * 2
NOTE Functions in Haskell don’t have to be defined in any particular order, so it doesn’t matter which function comes first in the baby.hs file.
Now save the file, and enter :l baby in GHCi to load your new function. Testing this function yields predictable results:
ghci> doubleUs 4 9
26
ghci> doubleUs 2.3 34.2
73.0
ghci> doubleUs 28 88 + doubleMe 123
478
Functions that you define can also call each other. With that in mind, we could redefine doubleUs in the following way:
doubleUs x y = doubleMe x + doubleMe y
This is a very simple example of a common pattern you will see when using Haskell: Basic, obviously correct functions can be combined to form more complex functions. This is a great way to avoid code repetition. For example, what if one day mathematicians figure out that 2 and 3 are actually the same, and you have to change your program? You could just redefine doubleMe to be x + x + x, and since doubleUs calls doubleMe, it would now also automatically work correctly in this strange new world where 2 is equal to 3.
Now let’s write a function that multiplies a number by 2, but only if that number is less than or equal to 100 (because numbers bigger than 100 are big enough as it is!).
doubleSmallNumber x = if x > 100
then x
else x*2
This example introduces Haskell’s if statement. You’re probably already familiar with if statements from other languages, but what makes Haskell’s unique is that the else part is mandatory.
Programs in imperative languages are essentially a series of steps that the computer executes when the program is run. When there is an if state- ment that doesn’t have a corresponding else, and the condition isn’t met, then the steps that fall under the if statement don’t get executed. Thus, in imperative languages, an if statement can just do nothing.
On the other hand, a Haskell program is a collection of functions. Func- tions are used to transform data values into result values, and every function
6 Chapter 1

should return some value, which can in turn be used by another function. Since every function has to return something, this implies that every if has to have a corresponding else. Otherwise, you could write a function that has a return value when a certain condition is met but doesn’t have one when that condition isn’t met! Briefly: Haskell’s if is an expression that must return a value, and not a statement.
Let’s say we want a function that adds one to every number that would be produced by our previous doubleSmallNumber function. The body of this new function would look like this:
doubleSmallNumber’ x = (if x > 100 then x else x*2) + 1
Note the placement of the parentheses. If we had omitted them, the function would only add one if x is less than or equal to 100. Also note the apostrophe (‘) at the end of the function’s name. The apostrophe doesn’t have any special meaning in Haskell’s syntax, which means it’s a valid char- acter to use in a function name. We usually use ‘ to denote either a strict ver- sion of a function (i.e., one that isn’t lazy), or a slightly modified version of a function or variable with a similar name.
Since ‘ is a valid character for function names, we can write a function that looks like this:
conanO’Brien = “It’s a-me, Conan O’Brien!”
There are two things to note here. The first is that we didn’t capitalize Conan in the name of the function. In Haskell, functions can’t begin with capital letters. (We’ll see why a bit later.) The second thing to note is that conanO’Brien doesn’t take any parameters. This means that it’s not a func- tion but a definition or a name. Because we cannot change what names (or functions) mean once we have defined them, conanO’Brien and the string “It’s a-me, Conan O’Brien!” can be used interchangeably.
An Intro to Lists
Lists in Haskell are homogeneous data structures, which means they store several elements of the same type. We can have a list of integers or a list of charac- ters, for example, but we can’t have a list made up of both integers and characters.
Lists are surrounded by square brackets, and the list values are separated by commas:
ghci> let lostNumbers = [4,8,15,16,23,42]
ghci> lostNumbers
[4,8,15,16,23,42]
Starting Out 7

NOTE Use the let keyword to define a name in GHCi. Entering let a = 1 in GHCi is equiv- alent to writing a = 1 in a script, then loading it with :l.
Concatenation
One of the most common operations when working with lists is concatena- tion. In Haskell, this is done using the ++ operator:
ghci> [1,2,3,4] ++ [9,10,11,12]
[1,2,3,4,9,10,11,12]
ghci> “hello” ++ ” ” ++ “world”
“hello world”
ghci> [‘w’,’o’] ++ [‘o’,’t’]
“woot”
NOTE In Haskell, strings are really just lists of characters. For example, the string “hello” is actually the same as the list [‘h’,’e’,’l’,’l’,’o’]. Because of this, we can use list functions on strings, which is really handy.
Be careful when repeatedly using the ++ operator on long strings. When you put together two lists, Haskell has to walk through the entire first list (the one on the left side of ++). That’s not a problem when dealing with smaller lists, but appending something to the end of a list with fifty million entries is going to take a while.
However, adding something to the beginning of a list is a nearly in- stantaneous operation. We do this with the : operator (also called the cons operator):
ghci> ‘A’:” SMALL CAT”
“A SMALL CAT”
ghci> 5:[1,2,3,4,5]
[5,1,2,3,4,5]