You are previewing Real World Haskell.

Real World Haskell

Cover of Real World Haskell by John Goerzen... Published by O'Reilly Media, Inc.
  1. Real World Haskell
    1. SPECIAL OFFER: Upgrade this ebook with O’Reilly
    2. A Note Regarding Supplemental Files
    3. Preface
      1. Have We Got a Deal for You!
      2. What to Expect from This Book
      3. What to Expect from Haskell
      4. A Brief Sketch of Haskell’s History
      5. Helpful Resources
      6. Conventions Used in This Book
      7. Using Code Examples
      8. Safari® Books Online
      9. How to Contact Us
      10. Acknowledgments
    4. 1. Getting Started
      1. Your Haskell Environment
      2. Getting Started with ghci, the Interpreter
      3. Basic Interaction: Using ghci as a Calculator
      4. Command-Line Editing in ghci
      5. Lists
      6. Strings and Characters
      7. First Steps with Types
      8. A Simple Program
    5. 2. Types and Functions
      1. Why Care About Types?
      2. Haskell’s Type System
      3. What to Expect from the Type System
      4. Some Common Basic Types
      5. Function Application
      6. Useful Composite Data Types: Lists and Tuples
      7. Functions over Lists and Tuples
      8. Function Types and Purity
      9. Haskell Source Files, and Writing Simple Functions
      10. Understanding Evaluation by Example
      11. Polymorphism in Haskell
      12. The Type of a Function of More Than One Argument
      13. Why the Fuss over Purity?
      14. Conclusion
    6. 3. Defining Types, Streamlining Functions
      1. Defining a New Data Type
      2. Type Synonyms
      3. Algebraic Data Types
      4. Pattern Matching
      5. Record Syntax
      6. Parameterized Types
      7. Recursive Types
      8. Reporting Errors
      9. Introducing Local Variables
      10. The Offside Rule and Whitespace in an Expression
      11. The case Expression
      12. Common Beginner Mistakes with Patterns
      13. Conditional Evaluation with Guards
    7. 4. Functional Programming
      1. Thinking in Haskell
      2. A Simple Command-Line Framework
      3. Warming Up: Portably Splitting Lines of Text
      4. Infix Functions
      5. Working with Lists
      6. How to Think About Loops
      7. Anonymous (lambda) Functions
      8. Partial Function Application and Currying
      9. As-patterns
      10. Code Reuse Through Composition
      11. Tips for Writing Readable Code
      12. Space Leaks and Strict Evaluation
    8. 5. Writing a Library: Working with JSON Data
      1. A Whirlwind Tour of JSON
      2. Representing JSON Data in Haskell
      3. The Anatomy of a Haskell Module
      4. Compiling Haskell Source
      5. Generating a Haskell Program and Importing Modules
      6. Printing JSON Data
      7. Type Inference Is a Double-Edged Sword
      8. A More General Look at Rendering
      9. Developing Haskell Code Without Going Nuts
      10. Pretty Printing a String
      11. Arrays and Objects, and the Module Header
      12. Writing a Module Header
      13. Fleshing Out the Pretty-Printing Library
      14. Creating a Package
      15. Practical Pointers and Further Reading
    9. 6. Using Typeclasses
      1. The Need for Typeclasses
      2. What Are Typeclasses?
      3. Declaring Typeclass Instances
      4. Important Built-in Typeclasses
      5. Automatic Derivation
      6. Typeclasses at Work: Making JSON Easier to Use
      7. Living in an Open World
      8. How to Give a Type a New Identity
      9. JSON Typeclasses Without Overlapping Instances
      10. The Dreaded Monomorphism Restriction
      11. Conclusion
    10. 7. I/O
      1. Classic I/O in Haskell
      2. Working with Files and Handles
      3. Extended Example: Functional I/O and Temporary Files
      4. Lazy I/O
      5. The IO Monad
      6. Is Haskell Really Imperative?
      7. Side Effects with Lazy I/O
      8. Buffering
      9. Reading Command-Line Arguments
      10. Environment Variables
    11. 8. Efficient File Processing, Regular Expressions, and Filename Matching
      1. Efficient File Processing
      2. Filename Matching
      3. Regular Expressions in Haskell
      4. More About Regular Expressions
      5. Translating a glob Pattern into a Regular Expression
      6. An important Aside: Writing Lazy Functions
      7. Making Use of Our Pattern Matcher
      8. Handling Errors Through API Design
      9. Putting Our Code to Work
    12. 9. I/O Case Study: A Library for Searching the Filesystem
      1. The find Command
      2. Starting Simple: Recursively Listing a Directory
      3. A Naive Finding Function
      4. Predicates: From Poverty to Riches, While Remaining Pure
      5. Sizing a File Safely
      6. A Domain-Specific Language for Predicates
      7. Controlling Traversal
      8. Density, Readability, and the Learning Process
      9. Another Way of Looking at Traversal
      10. Useful Coding Guidelines
    13. 10. Code Case Study: Parsing a Binary Data Format
      1. Grayscale Files
      2. Parsing a Raw PGM File
      3. Getting Rid of Boilerplate Code
      4. Implicit State
      5. Introducing Functors
      6. Writing a Functor Instance for Parse
      7. Using Functors for Parsing
      8. Rewriting Our PGM Parser
      9. Future Directions
    14. 11. Testing and Quality Assurance
      1. QuickCheck: Type-Based Testing
      2. Testing Case Study: Specifying a Pretty Printer
      3. Measuring Test Coverage with HPC
    15. 12. Barcode Recognition
      1. A Little Bit About Barcodes
      2. Introducing Arrays
      3. Encoding an EAN-13 Barcode
      4. Constraints on Our Decoder
      5. Divide and Conquer
      6. Turning a Color Image into Something Tractable
      7. What Have We Done to Our Image?
      8. Finding Matching Digits
      9. Life Without Arrays or Hash Tables
      10. Turning Digit Soup into an Answer
      11. Working with Row Data
      12. Pulling It All Together
      13. A Few Comments on Development Style
    16. 13. Data Structures
      1. Association Lists
      2. Maps
      3. Functions Are Data, Too
      4. Extended Example: /etc/passwd
      5. Extended Example: Numeric Types
      6. Taking Advantage of Functions as Data
      7. General-Purpose Sequences
    17. 14. Monads
      1. Revisiting Earlier Code Examples
      2. Looking for Shared Patterns
      3. The Monad Typeclass
      4. And Now, a Jargon Moment
      5. Using a New Monad: Show Your Work!
      6. Mixing Pure and Monadic Code
      7. Putting a Few Misconceptions to Rest
      8. Building the Logger Monad
      9. The Maybe Monad
      10. The List Monad
      11. Desugaring of do Blocks
      12. The State Monad
      13. Monads and Functors
      14. The Monad Laws and Good Coding Style
    18. 15. Programming with Monads
      1. Golfing Practice: Association Lists
      2. Generalized Lifting
      3. Looking for Alternatives
      4. Adventures in Hiding the Plumbing
      5. Separating Interface from Implementation
      6. The Reader Monad
      7. A Return to Automated Deriving
      8. Hiding the IO Monad
    19. 16. Using Parsec
      1. First Steps with Parsec: Simple CSV Parsing
      2. The sepBy and endBy Combinators
      3. Choices and Errors
      4. Extended Example: Full CSV Parser
      5. Parsec and MonadPlus
      6. Parsing a URL-Encoded Query String
      7. Supplanting Regular Expressions for Casual Parsing
      8. Parsing Without Variables
      9. Applicative Functors for Parsing
      10. Applicative Parsing by Example
      11. Parsing JSON Data
      12. Parsing a HTTP Request
    20. 17. Interfacing with C: The FFI
      1. Foreign Language Bindings: The Basics
      2. Regular Expressions for Haskell: A Binding for PCRE
      3. Passing String Data Between Haskell and C
      4. Matching on Strings
    21. 18. Monad Transformers
      1. Motivation: Boilerplate Avoidance
      2. A Simple Monad Transformer Example
      3. Common Patterns in Monads and Monad Transformers
      4. Stacking Multiple Monad Transformers
      5. Moving Down the Stack
      6. Understanding Monad Transformers by Building One
      7. Transformer Stacking Order Is Important
      8. Putting Monads and Monad Transformers into Perspective
    22. 19. Error Handling
      1. Error Handling with Data Types
      2. Exceptions
      3. Error Handling in Monads
    23. 20. Systems Programming in Haskell
      1. Running External Programs
      2. Directory and File Information
      3. Program Termination
      4. Dates and Times
      5. Extended Example: Piping
    24. 21. Using Databases
      1. Overview of HDBC
      2. Installing HDBC and Drivers
      3. Connecting to Databases
      4. Transactions
      5. Simple Queries
      6. SqlValue
      7. Query Parameters
      8. Prepared Statements
      9. Reading Results
      10. Database Metadata
      11. Error Handling
    25. 22. Extended Example: Web Client Programming
      1. Basic Types
      2. The Database
      3. The Parser
      4. Downloading
      5. Main Program
    26. 23. GUI Programming with gtk2hs
      1. Installing gtk2hs
      2. Overview of the GTK+ Stack
      3. User Interface Design with Glade
      4. Event-Driven Programming
      5. Initializing the GUI
      6. The Add Podcast Window
      7. Long-Running Tasks
      8. Using Cabal
    27. 24. Concurrent and Multicore Programming
      1. Defining Concurrency and Parallelism
      2. Concurrent Programming with Threads
      3. Simple Communication Between Threads
      4. The Main Thread and Waiting for Other Threads
      5. Communicating over Channels
      6. Useful Things to Know About
      7. Shared-State Concurrency Is Still Hard
      8. Using Multiple Cores with GHC
      9. Parallel Programming in Haskell
      10. Parallel Strategies and MapReduce
    28. 25. Profiling and Optimization
      1. Profiling Haskell Programs
      2. Controlling Evaluation
      3. Understanding Core
      4. Advanced Techniques: Fusion
    29. 26. Advanced Library Design: Building a Bloom Filter
      1. Introducing the Bloom Filter
      2. Use Cases and Package Layout
      3. Basic Design
      4. The ST Monad
      5. Designing an API for Qualified Import
      6. Creating a Mutable Bloom Filter
      7. The Immutable API
      8. Creating a Friendly Interface
      9. Creating a Cabal Package
      10. Testing with QuickCheck
      11. Performance Analysis and Tuning
    30. 27. Sockets and Syslog
      1. Basic Networking
      2. Communicating with UDP
      3. Communicating with TCP
    31. 28. Software Transactional Memory
      1. The Basics
      2. Some Simple Examples
      3. STM and Safety
      4. Retrying a Transaction
      5. Choosing Between Alternatives
      6. I/O and STM
      7. Communication Between Threads
      8. A Concurrent Web Link Checker
      9. Practical Aspects of STM
    32. A. Installing GHC and Haskell Libraries
      1. Installing GHC
      2. Installing Haskell Software
    33. B. Characters, Strings, and Escaping Rules
      1. Writing Character and String Literals
      2. International Language Support
      3. Escaping Text
    34. Index
    35. About the Authors
    36. Colophon
    37. SPECIAL OFFER: Upgrade this ebook with O’Reilly
O'Reilly logo

Working with Lists

As the bread and butter of functional programming, lists deserve some serious attention. The standard Prelude defines dozens of functions for dealing with lists. Many of these will be indispensable tools, so it’s important that we learn them early on.

For better or worse, this section is going to read a bit like a laundry list of functions. Why present so many functions at once? Because they are both easy to learn and absolutely ubiquitous. If we don’t have this toolbox at our fingertips, we’ll end up wasting time by reinventing simple functions that are already present in the standard libraries. So bear with us as we go through the list; the effort you’ll save will be huge.

The Data.List module is the real logical home of all standard list functions. The Prelude merely re-exports a large subset of the functions exported by Data.List. Several useful functions in Data.List are not re-exported by the standard Prelude. As we walk through list functions in the sections that follow, we will explicitly mention those that are only in Data.List:

ghci> :module +Data.List

Because none of these functions is complex or takes more than about three lines of Haskell to write, we’ll be brief in our descriptions of each. In fact, a quick and useful learning exercise is to write a definition of each function after you’ve read about it.

Basic List Manipulation

The length function tells us how many elements are in a list:

ghci> :type length
length :: [a] -> Int
ghci> length []
ghci> length [1,2,3]
ghci> length "strings are lists, too"

If you need to determine whether a list is empty, use the null function:

ghci> :type null
null :: [a] -> Bool
ghci> null []
ghci> null "plugh"

To access the first element of a list, use the head function:

ghci> :type head
head :: [a] -> a
ghci> head [1,2,3]

The converse, tail, returns all but the head of a list:

ghci> :type tail
tail :: [a] -> [a]
ghci> tail "foo"

Another function, last, returns the very last element of a list:

ghci> :type last
last :: [a] -> a
ghci> last "bar"

The converse of last is init, which returns a list of all but the last element of its input:

ghci> :type init
init :: [a] -> [a]
ghci> init "bar"

Several of the preceding functions behave poorly on empty lists, so be careful if you don’t know whether or not a list is empty. What form does their misbehavior take?

ghci> head []
*** Exception: Prelude.head: empty list

Try each of the previous functions in ghci. Which ones crash when given an empty list?

Safely and Sanely Working with Crashy Functions

When we want to use a function such as head, where we know that it might blow up on us if we pass in an empty list, there initially might be a strong temptation to check the length of the list before we call head. Let’s construct an artificial example to illustrate our point:

-- file: ch04/EfficientList.hs
myDumbExample xs = if length xs > 0
                   then head xs
                   else 'Z'

If we’re coming from a language such as Perl or Python, this might seem like a perfectly natural way to write this test. Behind the scenes, Python lists are arrays, and Perl arrays are, well, arrays. So we necessarily know how long they are, and calling len(foo) or scalar(@foo) is a perfectly natural thing to do. But as with many other things, it’s not a good idea to blindly transplant such an assumption into Haskell.

We’ve already seen the definition of the list algebraic data type many times, and we know that a list doesn’t store its own length explicitly. Thus, the only way that length can operate is to walk the entire list.

Therefore, when we care only whether or not a list is empty, calling length isn’t a good strategy. It can potentially do a lot more work than we want, if the list we’re working with is finite. Since Haskell lets us easily create infinite lists, a careless use of length may even result in an infinite loop.

A more appropriate function to call here instead is null, which runs in constant time. Better yet, using null makes our code indicate what property of the list we really care about. Here are two improved ways of expressing myDumbExample:

-- file: ch04/EfficientList.hs
mySmartExample xs = if not (null xs)
                    then head xs
                    else 'Z'

myOtherExample (x:_) = x
myOtherExample [] = 'Z'

Partial and Total Functions

Functions that have only return values defined for a subset of valid inputs are called partial functions (calling error doesn’t qualify as returning a value!). We call functions that return valid results over their entire input domains total functions.

It’s always a good idea to know whether a function you’re using is partial or total. Calling a partial function with an input that it can’t handle is probably the single biggest source of straightforward, avoidable bugs in Haskell programs.

Some Haskell programmers go so far as to give partial functions names that begin with a prefix such as unsafe so that they can’t shoot themselves in the foot accidentally.

It’s arguably a deficiency of the standard Prelude that it defines quite a few unsafe partial functions, such as head, without also providing safe total equivalents.

More Simple List Manipulations

Haskell’s name for the append function is (++):

ghci> :type (++)
(++) :: [a] -> [a] -> [a]
ghci> "foo" ++ "bar"
ghci> [] ++ [1,2,3]
ghci> [True] ++ []

The concat function takes a list of lists, all of the same type, and concatenates them into a single list:

ghci> :type concat
concat :: [[a]] -> [a]
ghci> concat [[1,2,3], [4,5,6]]

It removes one level of nesting:

ghci> concat [[[1,2],[3]], [[4],[5],[6]]]
ghci> concat (concat [[[1,2],[3]], [[4],[5],[6]]])

The reverse function returns the elements of a list in reverse order:

ghci> :type reverse
reverse :: [a] -> [a]
ghci> reverse "foo"

For lists of Bool, the and and or functions generalize their two-argument cousins, (&&) and (||), over lists:

ghci> :type and
and :: [Bool] -> Bool
ghci> and [True,False,True]
ghci> and []
ghci> :type or
or :: [Bool] -> Bool
ghci> or [False,False,False,True,False]
ghci> or []

They have more useful cousins, all and any, which operate on lists of any type. Each one takes a predicate as its first argument; all returns True if that predicate succeeds on every element of the list, while any returns True if the predicate succeeds on at least one element of the list:

ghci> :type all
all :: (a -> Bool) -> [a] -> Bool
ghci> all odd [1,3,5]
ghci> all odd [3,1,4,1,5,9,2,6,5]
ghci> all odd []
ghci> :type any
any :: (a -> Bool) -> [a] -> Bool
ghci> any even [3,1,4,1,5,9,2,6,5]
ghci> any even []

Working with Sublists

The take function, which we already discussed in Function Application, returns a sublist consisting of the first k elements from a list. Its converse, drop, drops k elements from the start of the list:

ghci> :type take
take :: Int -> [a] -> [a]
ghci> take 3 "foobar"
ghci> take 2 [1]
ghci> :type drop
drop :: Int -> [a] -> [a]
ghci> drop 3 "xyzzy"
ghci> drop 1 []

The splitAt function combines the functions take and drop, returning a pair of the input lists, split at the given index:

ghci> :type splitAt
splitAt :: Int -> [a] -> ([a], [a])
ghci> splitAt 3 "foobar"

The takeWhile and dropWhile functions take predicates. takeWhile takes elements from the beginning of a list as long as the predicate returns True, while dropWhile drops elements from the list as long as the predicate returns True:

ghci> :type takeWhile
takeWhile :: (a -> Bool) -> [a] -> [a]
ghci> takeWhile odd [1,3,5,6,8,9,11]
ghci> :type dropWhile
dropWhile :: (a -> Bool) -> [a] -> [a]
ghci> dropWhile even [2,4,6,7,9,10,12]

Just as splitAt tuples up the results of take and drop, the functions break (which we already saw in Warming Up: Portably Splitting Lines of Text) and span tuple up the results of takeWhile and dropWhile.

Each function takes a predicate; break consumes its input while its predicate fails, and span consumes while its predicate succeeds:

ghci> :type span
span :: (a -> Bool) -> [a] -> ([a], [a])
ghci> span even [2,4,6,7,9,10,11]
ghci> :type break
break :: (a -> Bool) -> [a] -> ([a], [a])
ghci> break even [1,3,5,6,8,9,10]

Searching Lists

As we’ve already seen, the elem function indicates whether a value is present in a list. It has a companion function, notElem:

ghci> :type elem
elem :: (Eq a) => a -> [a] -> Bool
ghci> 2 `elem` [5,3,2,1,1]
ghci> 2 `notElem` [5,3,2,1,1]

For a more general search, filter takes a predicate and returns every element of the list on which the predicate succeeds:

ghci> :type filter
filter :: (a -> Bool) -> [a] -> [a]
ghci> filter odd [2,4,1,3,6,8,5,7]

In Data.List, three predicates—isPrefixOf, isInfixOf, and isSuffixOf—let us test for the presence of sublists within a bigger list. The easiest way to use them is with infix notation.

The isPrefixOf function tells us whether its left argument matches the beginning of its right argument:

ghci> :module +Data.List
ghci> :type isPrefixOf
isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
ghci> "foo" `isPrefixOf` "foobar"
ghci> [1,2] `isPrefixOf` []

The isInfixOf function indicates whether its left argument is a sublist of its right:

ghci> :module +Data.List
ghci> [2,6] `isInfixOf` [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]
ghci> "funk" `isInfixOf` "sonic youth"

The operation of isSuffixOf shouldn’t need any explanation:

ghci> :module +Data.List
ghci> ".c" `isSuffixOf` "crashme.c"

Working with Several Lists at Once

The zip function takes two lists and zips them into a single list of pairs. The resulting list is the same length as the shorter of the two inputs:

ghci> :type zip
zip :: [a] -> [b] -> [(a, b)]
ghci> zip [12,72,93] "zippity"

More useful is zipWith, which takes two lists and applies a function to each pair of elements, generating a list that is the same length as the shorter of the two:

ghci> :type zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
ghci> zipWith (+) [1,2,3] [4,5,6]

Haskell’s type system makes it an interesting challenge to write functions that take variable numbers of arguments.[8] So if we want to zip three lists together, we call zip3 or zipWith3, and so on, up to zip7 and zipWith7.

Special String-Handling Functions

We’ve already encountered the standard lines function and its standard counterpart unlines in the sectionWarming Up: Portably Splitting Lines of Text. Notice that unlines always places a newline on the end of its result:

ghci> lines "foo\nbar"
ghci> unlines ["foo", "bar"]

The words function splits an input string on any whitespace. Its counterpart, unwords, uses a single space to join a list of words:

ghci> words "the  \r  quick \t  brown\n\n\nfox"
ghci> unwords ["jumps", "over", "the", "lazy", "dog"]
"jumps over the lazy dog"

[8] Unfortunately, we do not have room to address that challenge in this book.

The best content for your career. Discover unlimited learning on demand for around $1/day.