🔙 Quay lại trang tải sách pdf ebook Haskell Notes for Professionals Ebooks Nhóm Zalo Notes for Professionals Haskell Haskell Notes for Professionals 200+ pages of professional hints and tricks GoalKicker.com Free Programming Books Disclaimer This is an unocial free book created for educational purposes and is not aliated with ocial Haskell group(s) or company(s). All trademarks and registered trademarks are the property of their respective owners Contents About ................................................................................................................................................................................... 1 Chapter 1: Getting started with Haskell Language ..................................................................................... 2 Section 1.1: Getting started ............................................................................................................................................ 2 Section 1.2: Hello, World! ............................................................................................................................................... 4 Section 1.3: Factorial ...................................................................................................................................................... 6 Section 1.4: Fibonacci, Using Lazy Evaluation ............................................................................................................ 6 Section 1.5: Primes ......................................................................................................................................................... 7 Section 1.6: Declaring Values ........................................................................................................................................ 8 Chapter 2: Overloaded Literals ........................................................................................................................... 10 Section 2.1: Strings ....................................................................................................................................................... 10 Section 2.2: Floating Numeral .................................................................................................................................... 10 Section 2.3: Integer Numeral ...................................................................................................................................... 11 Section 2.4: List Literals .............................................................................................................................................. 11 Chapter 3: Foldable ................................................................................................................................................... 13 Section 3.1: Definition of Foldable .............................................................................................................................. 13 Section 3.2: An instance of Foldable for a binary tree ............................................................................................ 13 Section 3.3: Counting the elements of a Foldable structure ................................................................................... 14 Section 3.4: Folding a structure in reverse ............................................................................................................... 14 Section 3.5: Flattening a Foldable structure into a list ............................................................................................ 15 Section 3.6: Performing a side-eect for each element of a Foldable structure ................................................. 15 Section 3.7: Flattening a Foldable structure into a Monoid .................................................................................... 16 Section 3.8: Checking if a Foldable structure is empty ........................................................................................... 16 Chapter 4: Traversable ........................................................................................................................................... 18 Section 4.1: Definition of Traversable ........................................................................................................................ 18 Section 4.2: Traversing a structure in reverse ......................................................................................................... 18 Section 4.3: An instance of Traversable for a binary tree ...................................................................................... 19 Section 4.4: Traversable structures as shapes with contents ................................................................................ 20 Section 4.5: Instantiating Functor and Foldable for a Traversable structure ....................................................... 20 Section 4.6: Transforming a Traversable structure with the aid of an accumulating parameter ...................... 21 Section 4.7: Transposing a list of lists ....................................................................................................................... 22 Chapter 5: Lens ............................................................................................................................................................ 24 Section 5.1: Lenses for records ................................................................................................................................... 24 Section 5.2: Manipulating tuples with Lens ............................................................................................................... 24 Section 5.3: Lens and Prism ........................................................................................................................................ 25 Section 5.4: Stateful Lenses ........................................................................................................................................ 25 Section 5.5: Lenses compose ..................................................................................................................................... 26 Section 5.6: Writing a lens without Template Haskell ............................................................................................. 26 Section 5.7: Fields with makeFields ........................................................................................................................... 27 Section 5.8: Classy Lenses .......................................................................................................................................... 29 Section 5.9: Traversals ................................................................................................................................................ 29 Chapter 6: QuickCheck ............................................................................................................................................. 30 Section 6.1: Declaring a property ............................................................................................................................... 30 Section 6.2: Randomly generating data for custom types ..................................................................................... 30 Section 6.3: Using implication (==>) to check properties with preconditions ........................................................ 30 Section 6.4: Checking a single property ................................................................................................................... 30 Section 6.5: Checking all the properties in a file ...................................................................................................... 31 Section 6.6: Limiting the size of test data ................................................................................................................. 31 Chapter 7: Common GHC Language Extensions ......................................................................................... 33 Section 7.1: RankNTypes ............................................................................................................................................. 33 Section 7.2: OverloadedStrings .................................................................................................................................. 33 Section 7.3: BinaryLiterals .......................................................................................................................................... 34 Section 7.4: ExistentialQuantification ........................................................................................................................ 34 Section 7.5: LambdaCase ........................................................................................................................................... 35 Section 7.6: FunctionalDependencies ........................................................................................................................ 36 Section 7.7: FlexibleInstances ..................................................................................................................................... 36 Section 7.8: GADTs ...................................................................................................................................................... 37 Section 7.9: TupleSections .......................................................................................................................................... 37 Section 7.10: OverloadedLists ..................................................................................................................................... 38 Section 7.11: MultiParamTypeClasses ........................................................................................................................ 38 Section 7.12: UnicodeSyntax ....................................................................................................................................... 39 Section 7.13: PatternSynonyms .................................................................................................................................. 39 Section 7.14: ScopedTypeVariables ........................................................................................................................... 40 Section 7.15: RecordWildCards ................................................................................................................................... 41 Chapter 8: Free Monads .......................................................................................................................................... 42 Section 8.1: Free monads split monadic computations into data structures and interpreters ........................... 42 Section 8.2: The Freer monad .................................................................................................................................... 43 Section 8.3: How do foldFree and iterM work? ........................................................................................................ 44 Section 8.4: Free Monads are like fixed points ......................................................................................................... 45 Chapter 9: Type Classes .......................................................................................................................................... 46 Section 9.1: Eq .............................................................................................................................................................. 46 Section 9.2: Monoid ..................................................................................................................................................... 46 Section 9.3: Ord ........................................................................................................................................................... 47 Section 9.4: Num .......................................................................................................................................................... 47 Section 9.5: Maybe and the Functor Class ............................................................................................................... 49 Section 9.6: Type class inheritance: Ord type class ................................................................................................. 49 Chapter 10: IO ............................................................................................................................................................... 51 Section 10.1: Getting the 'a' "out of" 'IO a' .................................................................................................................. 51 Section 10.2: IO defines your program's `main` action ............................................................................................ 51 Section 10.3: Checking for end-of-file conditions ..................................................................................................... 52 Section 10.4: Reading all contents of standard input into a string ........................................................................ 52 Section 10.5: Role and Purpose of IO ........................................................................................................................ 53 Section 10.6: Writing to stdout .................................................................................................................................... 55 Section 10.7: Reading words from an entire file ....................................................................................................... 56 Section 10.8: Reading a line from standard input .................................................................................................... 56 Section 10.9: Reading from `stdin` .............................................................................................................................. 57 Section 10.10: Parsing and constructing an object from standard input ............................................................... 57 Section 10.11: Reading from file handles ................................................................................................................... 58 Chapter 11: Record Syntax ..................................................................................................................................... 59 Section 11.1: Basic Syntax ............................................................................................................................................ 59 Section 11.2: Defining a data type with field labels .................................................................................................. 60 Section 11.3: RecordWildCards ................................................................................................................................... 60 Section 11.4: Copying Records while Changing Field Values ................................................................................... 61 Section 11.5: Records with newtype ........................................................................................................................... 61 Chapter 12: Partial Application ............................................................................................................................ 63 Section 12.1: Sections ................................................................................................................................................... 63 Section 12.2: Partially Applied Adding Function ....................................................................................................... 63 Section 12.3: Returning a Partially Applied Function ............................................................................................... 64 Chapter 13: Monoid ..................................................................................................................................................... 65 Section 13.1: An instance of Monoid for lists .............................................................................................................. 65 Section 13.2: Collapsing a list of Monoids into a single value ................................................................................. 65 Section 13.3: Numeric Monoids ................................................................................................................................... 65 Section 13.4: An instance of Monoid for () ................................................................................................................ 66 Chapter 14: Category Theory .............................................................................................................................. 67 Section 14.1: Category theory as a system for organizing abstraction ................................................................. 67 Section 14.2: Haskell types as a category ................................................................................................................ 67 Section 14.3: Definition of a Category ....................................................................................................................... 69 Section 14.4: Coproduct of types in Hask ................................................................................................................. 70 Section 14.5: Product of types in Hask ...................................................................................................................... 71 Section 14.6: Haskell Applicative in terms of Category Theory .............................................................................. 72 Chapter 15: Lists .......................................................................................................................................................... 73 Section 15.1: List basics ................................................................................................................................................ 73 Section 15.2: Processing lists ...................................................................................................................................... 73 Section 15.3: Ranges .................................................................................................................................................... 74 Section 15.4: List Literals ............................................................................................................................................. 75 Section 15.5: List Concatenation ................................................................................................................................ 75 Section 15.6: Accessing elements in lists ................................................................................................................... 75 Section 15.7: Basic Functions on Lists ........................................................................................................................ 75 Section 15.8: Transforming with `map` ...................................................................................................................... 76 Section 15.9: Filtering with `filter` ................................................................................................................................ 76 Section 15.10: foldr ....................................................................................................................................................... 77 Section 15.11: Zipping and Unzipping Lists ................................................................................................................. 77 Section 15.12: foldl ........................................................................................................................................................ 78 Chapter 16: Sorting Algorithms ............................................................................................................................ 79 Section 16.1: Insertion Sort ........................................................................................................................................... 79 Section 16.2: Permutation Sort ................................................................................................................................... 79 Section 16.3: Merge Sort .............................................................................................................................................. 79 Section 16.4: Quicksort ................................................................................................................................................ 80 Section 16.5: Bubble sort ............................................................................................................................................. 80 Section 16.6: Selection sort ......................................................................................................................................... 80 Chapter 17: Type Families ...................................................................................................................................... 81 Section 17.1: Datatype Families .................................................................................................................................. 81 Section 17.2: Type Synonym Families ....................................................................................................................... 81 Section 17.3: Injectivity ................................................................................................................................................. 83 Chapter 18: Monads ................................................................................................................................................... 84 Section 18.1: Definition of Monad ............................................................................................................................... 84 Section 18.2: No general way to extract value from a monadic computation ..................................................... 84 Section 18.3: Monad as a Subclass of Applicative .................................................................................................... 85 Section 18.4: The Maybe monad ................................................................................................................................ 85 Section 18.5: IO monad ............................................................................................................................................... 87 Section 18.6: List Monad .............................................................................................................................................. 88 Section 18.7: do-notation ............................................................................................................................................ 88 Chapter 19: Stack ........................................................................................................................................................ 90 Section 19.1: Profiling with Stack ................................................................................................................................. 90 Section 19.2: Structure ................................................................................................................................................. 90 Section 19.3: Build and Run a Stack Project .............................................................................................................. 90 Section 19.4: Viewing dependencies .......................................................................................................................... 90 Section 19.5: Stack install ............................................................................................................................................ 91 Section 19.6: Installing Stack ....................................................................................................................................... 91 Section 19.7: Creating a simple project ..................................................................................................................... 91 Section 19.8: Stackage Packages and changing the LTS (resolver) version ........................................................ 91 Chapter 20: Generalized Algebraic Data Types ......................................................................................... 93 Section 20.1: Basic Usage ........................................................................................................................................... 93 Chapter 21: Recursion Schemes .......................................................................................................................... 94 Section 21.1: Fixed points ............................................................................................................................................. 94 Section 21.2: Primitive recursion ................................................................................................................................. 94 Section 21.3: Primitive corecursion ............................................................................................................................. 95 Section 21.4: Folding up a structure one layer at a time ......................................................................................... 95 Section 21.5: Unfolding a structure one layer at a time .......................................................................................... 95 Section 21.6: Unfolding and then folding, fused ....................................................................................................... 95 Chapter 22: Data.Text .............................................................................................................................................. 97 Section 22.1: Text Literals ............................................................................................................................................ 97 Section 22.2: Checking if a Text is a substring of another Text ............................................................................. 97 Section 22.3: Stripping whitespace ............................................................................................................................ 97 Section 22.4: Indexing Text ......................................................................................................................................... 98 Section 22.5: Splitting Text Values ............................................................................................................................. 98 Section 22.6: Encoding and Decoding Text .............................................................................................................. 99 Chapter 23: Using GHCi .......................................................................................................................................... 100 Section 23.1: Breakpoints with GHCi ........................................................................................................................ 100 Section 23.2: Quitting GHCi ...................................................................................................................................... 100 Section 23.3: Reloading a already loaded file ........................................................................................................ 101 Section 23.4: Starting GHCi ...................................................................................................................................... 101 Section 23.5: Changing the GHCi default prompt .................................................................................................. 101 Section 23.6: The GHCi configuration file ............................................................................................................... 101 Section 23.7: Loading a file ...................................................................................................................................... 102 Section 23.8: Multi-line statements .......................................................................................................................... 102 Chapter 24: Strictness ........................................................................................................................................... 103 Section 24.1: Bang Patterns ...................................................................................................................................... 103 Section 24.2: Lazy patterns ...................................................................................................................................... 103 Section 24.3: Normal forms ...................................................................................................................................... 104 Section 24.4: Strict fields ........................................................................................................................................... 105 Chapter 25: Syntax in Functions ....................................................................................................................... 106 Section 25.1: Pattern Matching ................................................................................................................................. 106 Section 25.2: Using where and guards ................................................................................................................... 106 Section 25.3: Guards ................................................................................................................................................. 107 Chapter 26: Functor ................................................................................................................................................. 108 Section 26.1: Class Definition of Functor and Laws ............................................................................................... 108 Section 26.2: Replacing all elements of a Functor with a single value ................................................................ 108 Section 26.3: Common instances of Functor .......................................................................................................... 108 Section 26.4: Deriving Functor ................................................................................................................................. 110 Section 26.5: Polynomial functors ........................................................................................................................... 111 Section 26.6: Functors in Category Theory ............................................................................................................ 112 Chapter 27: Testing with Tasty ......................................................................................................................... 114 Section 27.1: SmallCheck, QuickCheck and HUnit .................................................................................................. 114 Chapter 28: Creating Custom Data Types .................................................................................................. 115 Section 28.1: Creating a data type with value constructor parameters .............................................................. 115 Section 28.2: Creating a data type with type parameters ................................................................................... 115 Section 28.3: Creating a simple data type ............................................................................................................. 115 Section 28.4: Custom data type with record parameters ..................................................................................... 116 Chapter 29: Reactive-banana ............................................................................................................................ 117 Section 29.1: Injecting external events into the library .......................................................................................... 117 Section 29.2: Event type ........................................................................................................................................... 117 Section 29.3: Actuating EventNetworks .................................................................................................................. 117 Section 29.4: Behavior type ..................................................................................................................................... 118 Chapter 30: Optimization ..................................................................................................................................... 119 Section 30.1: Compiling your Program for Profiling .............................................................................................. 119 Section 30.2: Cost Centers ........................................................................................................................................ 119 Chapter 31: Concurrency ....................................................................................................................................... 121 Section 31.1: Spawning Threads with `forkIO` .......................................................................................................... 121 Section 31.2: Communicating between Threads with `MVar` ................................................................................ 121 Section 31.3: Atomic Blocks with Software Transactional Memory ..................................................................... 122 Chapter 32: Function composition ................................................................................................................... 124 Section 32.1: Right-to-left composition ................................................................................................................... 124 Section 32.2: Composition with binary function ..................................................................................................... 124 Section 32.3: Left-to-right composition ................................................................................................................... 124 Chapter 33: Databases .......................................................................................................................................... 125 Section 33.1: Postgres ................................................................................................................................................ 125 Chapter 34: Data.Aeson - JSON in Haskell ................................................................................................. 126 Section 34.1: Smart Encoding and Decoding using Generics ................................................................................ 126 Section 34.2: A quick way to generate a Data.Aeson.Value ................................................................................. 126 Section 34.3: Optional Fields .................................................................................................................................... 127 Chapter 35: Higher-order functions ................................................................................................................ 128 Section 35.1: Basics of Higher Order Functions ...................................................................................................... 128 Section 35.2: Lambda Expressions .......................................................................................................................... 128 Section 35.3: Currying ............................................................................................................................................... 129 Chapter 36: Containers - Data.Map ................................................................................................................ 130 Section 36.1: Importing the Module .......................................................................................................................... 130 Section 36.2: Monoid instance ................................................................................................................................. 130 Section 36.3: Constructing ........................................................................................................................................ 130 Section 36.4: Checking If Empty .............................................................................................................................. 130 Section 36.5: Finding Values ..................................................................................................................................... 130 Section 36.6: Inserting Elements .............................................................................................................................. 131 Section 36.7: Deleting Elements ............................................................................................................................... 131 Chapter 37: Fixity declarations .......................................................................................................................... 132 Section 37.1: Associativity ......................................................................................................................................... 132 Section 37.2: Binding precedence ........................................................................................................................... 132 Section 37.3: Example declarations ......................................................................................................................... 133 Chapter 38: Web Development ......................................................................................................................... 134 Section 38.1: Servant ................................................................................................................................................. 134 Section 38.2: Yesod ................................................................................................................................................... 135 Chapter 39: Vectors ................................................................................................................................................. 136 Section 39.1: The Data.Vector Module ..................................................................................................................... 136 Section 39.2: Filtering a Vector ................................................................................................................................ 136 Section 39.3: Mapping (`map`) and Reducing (`fold`) a Vector ............................................................................ 136 Section 39.4: Working on Multiple Vectors ............................................................................................................. 136 Chapter 40: Cabal .................................................................................................................................................... 137 Section 40.1: Working with sandboxes .................................................................................................................... 137 Section 40.2: Install packages ................................................................................................................................. 137 Chapter 41: Type algebra .................................................................................................................................... 138 Section 41.1: Addition and multiplication ................................................................................................................. 138 Section 41.2: Functions .............................................................................................................................................. 139 Section 41.3: Natural numbers in type algebra ...................................................................................................... 139 Section 41.4: Recursive types ................................................................................................................................... 140 Section 41.5: Derivatives ........................................................................................................................................... 141 Chapter 42: Arrows ................................................................................................................................................. 142 Section 42.1: Function compositions with multiple channels ................................................................................ 142 Chapter 43: Typed holes ...................................................................................................................................... 143 Section 43.1: Syntax of typed holes ......................................................................................................................... 143 Section 43.2: Semantics of typed holes .................................................................................................................. 143 Section 43.3: Using typed holes to define a class instance .................................................................................. 143 Chapter 44: Rewrite rules (GHC) ...................................................................................................................... 146 Section 44.1: Using rewrite rules on overloaded functions ................................................................................... 146 Chapter 45: Date and Time ................................................................................................................................ 147 Section 45.1: Finding Today's Date .......................................................................................................................... 147 Section 45.2: Adding, Subtracting and Comparing Days ...................................................................................... 147 Chapter 46: List Comprehensions .................................................................................................................... 148 Section 46.1: Basic List Comprehensions ................................................................................................................ 148 Section 46.2: Do Notation ......................................................................................................................................... 148 Section 46.3: Patterns in Generator Expressions ................................................................................................... 148 Section 46.4: Guards ................................................................................................................................................. 149 Section 46.5: Parallel Comprehensions ................................................................................................................... 149 Section 46.6: Local Bindings ..................................................................................................................................... 149 Section 46.7: Nested Generators ............................................................................................................................. 150 Chapter 47: Streaming IO .................................................................................................................................... 151 Section 47.1: Streaming IO ........................................................................................................................................ 151 Chapter 48: Google Protocol Buers ............................................................................................................ 152 Section 48.1: Creating, building and using a simple .proto file ............................................................................. 152 Chapter 49: Template Haskell & QuasiQuotes ......................................................................................... 154 Section 49.1: Syntax of Template Haskell and Quasiquotes ................................................................................. 154 Section 49.2: The Q type .......................................................................................................................................... 155 Section 49.3: An n-arity curry .................................................................................................................................. 156 Chapter 50: Phantom types ................................................................................................................................ 158 Section 50.1: Use Case for Phantom Types: Currencies ........................................................................................ 158 Chapter 51: Modules ................................................................................................................................................ 159 Section 51.1: Defining Your Own Module ................................................................................................................. 159 Section 51.2: Exporting Constructors ....................................................................................................................... 159 Section 51.3: Importing Specific Members of a Module ......................................................................................... 159 Section 51.4: Hiding Imports ..................................................................................................................................... 160 Section 51.5: Qualifying Imports .............................................................................................................................. 160 Section 51.6: Hierarchical module names ............................................................................................................... 160 Chapter 52: Tuples (Pairs, Triples, ...) ............................................................................................................. 162 Section 52.1: Extract tuple components .................................................................................................................. 162 Section 52.2: Strictness of matching a tuple .......................................................................................................... 162 Section 52.3: Construct tuple values ....................................................................................................................... 162 Section 52.4: Write tuple types ................................................................................................................................ 163 Section 52.5: Pattern Match on Tuples ................................................................................................................... 163 Section 52.6: Apply a binary function to a tuple (uncurrying) ............................................................................. 164 Section 52.7: Apply a tuple function to two arguments (currying) ...................................................................... 164 Section 52.8: Swap pair components ...................................................................................................................... 164 Chapter 53: Graphics with Gloss ....................................................................................................................... 165 Section 53.1: Installing Gloss ..................................................................................................................................... 165 Section 53.2: Getting something on the screen ..................................................................................................... 165 Chapter 54: State Monad ..................................................................................................................................... 167 Section 54.1: Numbering the nodes of a tree with a counter ................................................................................ 167 Chapter 55: Pipes ...................................................................................................................................................... 169 Section 55.1: Producers ............................................................................................................................................. 169 Section 55.2: Connecting Pipes ................................................................................................................................ 169 Section 55.3: Pipes ..................................................................................................................................................... 169 Section 55.4: Running Pipes with runEect ............................................................................................................ 169 Section 55.5: Consumers .......................................................................................................................................... 170 Section 55.6: The Proxy monad transformer ......................................................................................................... 170 Section 55.7: Combining Pipes and Network communication .............................................................................. 170 Chapter 56: Infix operators ................................................................................................................................. 173 Section 56.1: Prelude ................................................................................................................................................. 173 Section 56.2: Finding information about infix operators ....................................................................................... 174 Section 56.3: Custom operators ............................................................................................................................... 174 Chapter 57: Parallelism ......................................................................................................................................... 176 Section 57.1: The Eval Monad ................................................................................................................................... 176 Section 57.2: rpar ...................................................................................................................................................... 176 Section 57.3: rseq ...................................................................................................................................................... 177 Chapter 58: Parsing HTML with taggy-lens and lens ............................................................................. 178 Section 58.1: Filtering elements from the tree ........................................................................................................ 178 Section 58.2: Extract the text contents from a div with a particular id ............................................................... 178 Chapter 59: Foreign Function Interface ........................................................................................................ 180 Section 59.1: Calling C from Haskell ........................................................................................................................ 180 Section 59.2: Passing Haskell functions as callbacks to C code .......................................................................... 180 Chapter 60: Gtk3 ....................................................................................................................................................... 182 Section 60.1: Hello World in Gtk ............................................................................................................................... 182 Chapter 61: Monad Transformers .................................................................................................................... 183 Section 61.1: A monadic counter ............................................................................................................................... 183 Chapter 62: Bifunctor ............................................................................................................................................. 186 Section 62.1: Definition of Bifunctor ......................................................................................................................... 186 Section 62.2: Common instances of Bifunctor ....................................................................................................... 186 Section 62.3: first and second .................................................................................................................................. 186 Chapter 63: Proxies .................................................................................................................................................. 188 Section 63.1: Using Proxy .......................................................................................................................................... 188 Section 63.2: The "polymorphic proxy" idiom ........................................................................................................ 188 Section 63.3: Proxy is like () ...................................................................................................................................... 188 Chapter 64: Applicative Functor ....................................................................................................................... 190 Section 64.1: Alternative definition ........................................................................................................................... 190 Section 64.2: Common instances of Applicative .................................................................................................... 190 Chapter 65: Common monads as free monads ........................................................................................ 193 Section 65.1: Free Empty ~~ Identity ........................................................................................................................ 193 Section 65.2: Free Identity ~~ (Nat,) ~~ Writer Nat ................................................................................................. 193 Section 65.3: Free Maybe ~~ MaybeT (Writer Nat) ................................................................................................ 193 Section 65.4: Free (Writer w) ~~ Writer [w] ............................................................................................................. 194 Section 65.5: Free (Const c) ~~ Either c ................................................................................................................... 194 Section 65.6: Free (Reader x) ~~ Reader (Stream x) ............................................................................................. 195 Chapter 66: Common functors as the base of cofree comonads ................................................... 196 Section 66.1: Cofree Empty ~~ Empty ...................................................................................................................... 196 Section 66.2: Cofree (Const c) ~~ Writer c .............................................................................................................. 196 Section 66.3: Cofree Identity ~~ Stream .................................................................................................................. 196 Section 66.4: Cofree Maybe ~~ NonEmpty ............................................................................................................. 196 Section 66.5: Cofree (Writer w) ~~ WriterT w Stream ............................................................................................ 197 Section 66.6: Cofree (Either e) ~~ NonEmptyT (Writer e) ...................................................................................... 197 Section 66.7: Cofree (Reader x) ~~ Moore x ........................................................................................................... 198 Chapter 67: Arithmetic ........................................................................................................................................... 199 Section 67.1: Basic examples .................................................................................................................................... 201 Section 67.2: `Could not deduce (Fractional Int) ...` ................................................................................................ 201 Section 67.3: Function examples .............................................................................................................................. 201 Chapter 68: Role ....................................................................................................................................................... 203 Section 68.1: Nominal Role ....................................................................................................................................... 203 Section 68.2: Representational Role ....................................................................................................................... 203 Section 68.3: Phantom Role ..................................................................................................................................... 203 Chapter 69: Arbitrary-rank polymorphism with RankNTypes .......................................................... 204 Section 69.1: RankNTypes ........................................................................................................................................ 204 Chapter 70: GHCJS .................................................................................................................................................. 205 Section 70.1: Running "Hello World!" with Node.js .................................................................................................. 205 Chapter 71: XML ......................................................................................................................................................... 206 Section 71.1: Encoding a record using the `xml` library .......................................................................................... 206 Chapter 72: Reader / ReaderT ......................................................................................................................... 207 Section 72.1: Simple demonstration ......................................................................................................................... 207 Chapter 73: Function call syntax ...................................................................................................................... 208 Section 73.1: Partial application - Part 1 .................................................................................................................. 208 Section 73.2: Partial application - Part 2 ................................................................................................................. 208 Section 73.3: Parentheses in a basic function call ................................................................................................. 208 Section 73.4: Parentheses in embedded function calls ......................................................................................... 209 Chapter 74: Logging ............................................................................................................................................... 210 Section 74.1: Logging with hslogger ........................................................................................................................ 210 Chapter 75: Attoparsec ......................................................................................................................................... 211 Section 75.1: Combinators ........................................................................................................................................ 211 Section 75.2: Bitmap - Parsing Binary Data ........................................................................................................... 211 Chapter 76: zipWithM .............................................................................................................................................. 213 Section 76.1: Calculatings sales prices .................................................................................................................... 213 Chapter 77: Profunctor .......................................................................................................................................... 214 Section 77.1: (->) Profunctor ..................................................................................................................................... 214 Chapter 78: Type Application ............................................................................................................................. 215 Section 78.1: Avoiding type annotations ................................................................................................................. 215 Section 78.2: Type applications in other languages .............................................................................................. 215 Section 78.3: Order of parameters .......................................................................................................................... 216 Section 78.4: Interaction with ambiguous types .................................................................................................... 216 Credits ............................................................................................................................................................................ 218 You may also like ...................................................................................................................................................... 220 About Please feel free to share this PDF with anyone for free, latest version of this book can be downloaded from: https://goalkicker.com/HaskellBook This Haskell Notes for Professionals book is compiled from Stack Overflow Documentation, the content is written by the beautiful people at Stack Overflow. Text content is released under Creative Commons BY-SA, see credits at the end of this book whom contributed to the various chapters. Images may be copyright of their respective owners unless otherwise specified This is an unofficial free book created for educational purposes and is not affiliated with official Haskell group(s) or company(s) nor Stack Overflow. All trademarks and registered trademarks are the property of their respective company owners The information presented in this book is not guaranteed to be correct nor accurate, use at your own risk Please send feedback and corrections to [email protected] GoalKicker.com – Haskell Notes for Professionals 1 Chapter 1: Getting started with Haskell Language Version Release Date Haskell 2010 2012-07-10 Haskell 98 2002-12-01 Section 1.1: Getting started Online REPL The easiest way to get started writing Haskell is probably by going to the Haskell website or Try Haskell and use the online REPL (read-eval-print-loop) on the home page. The online REPL supports most basic functionality and even some IO. There is also a basic tutorial available which can be started by typing the command help. An ideal tool to start learning the basics of Haskell and try out some stuff. GHC(i) For programmers that are ready to engage a little bit more, there is GHCi, an interactive environment that comes with the Glorious/Glasgow Haskell Compiler. The GHC can be installed separately, but that is only a compiler. In order to be able to install new libraries, tools like Cabal and Stack must be installed as well. If you are running a Unix-like operating system, the easiest installation is to install Stack using: curl -sSL https://get.haskellstack.org/ | sh This installs GHC isolated from the rest of your system, so it is easy to remove. All commands must be preceded by stack though. Another simple approach is to install a Haskell Platform. The platform exists in two flavours: 1. The minimal distribution contains only GHC (to compile) and Cabal/Stack (to install and build packages) 2. The full distribution additionally contains tools for project development, profiling and coverage analysis. Also an additional set of widely-used packages is included. These platforms can be installed by downloading an installer and following the instructions or by using your distribution's package manager (note that this version is not guaranteed to be up-to-date): Ubuntu, Debian, Mint: sudo apt-get install haskell-platform Fedora: sudo dnf install haskell-platform Redhat: sudo yum install haskell-platform Arch Linux: sudo pacman -S ghc cabal-install haskell-haddock-api \ haskell-haddock-library happy alex GoalKicker.com – Haskell Notes for Professionals 2 Gentoo: sudo layman -a haskell sudo emerge haskell-platform OSX with Homebrew: brew cask install haskell-platform OSX with MacPorts: sudo port install haskell-platform Once installed, it should be possible to start GHCi by invoking the ghci command anywhere in the terminal. If the installation went well, the console should look something like me@notebook:~$ ghci GHCi, version 6.12.1: http://www.haskell.org/ghc/ :? for help Prelude> possibly with some more information on what libraries have been loaded before the Prelude>. Now, the console has become a Haskell REPL and you can execute Haskell code as with the online REPL. In order to quit this interactive environment, one can type :qor :quit. For more information on what commands are available in GHCi, type :? as indicated in the starting screen. Because writing the same things again and again on a single line is not always that practically, it might be a good idea to write the Haskell code in files. These files normally have .hs for an extension and can be loaded into the REPL by using :l or :load. As mentioned earlier, GHCi is a part of the GHC, which is actually a compiler. This compiler can be used to transform a .hs file with Haskell code into a running program. Because a .hs file can contain a lot of functions, a main function must be defined in the file. This will be the starting point for the program. The file test.hs can be compiled with the command ghc test.hs this will create object files and an executable if there were no errors and the main function was defined correctly. More advanced tools 1. It has already been mentioned earlier as package manager, but stack can be a useful tool for Haskell development in completely different ways. Once installed, it is capable of installing (multiple versions of) GHC project creation and scaffolding dependency management building and testing projects benchmarking 2. IHaskell is a haskell kernel for IPython and allows to combine (runnable) code with markdown and mathematical notation. GoalKicker.com – Haskell Notes for Professionals 3 Section 1.2: Hello, World! A basic "Hello, World!" program in Haskell can be expressed concisely in just one or two lines: main :: IO () main = putStrLn "Hello, World!" The first line is an optional type annotation, indicating that main is a value of type IO (), representing an I/O action which "computes" a value of type () (read "unit"; the empty tuple conveying no information) besides performing some side effects on the outside world (here, printing a string at the terminal). This type annotation is usually omitted for main because it is its only possible type. Put this into a helloworld.hs file and compile it using a Haskell compiler, such as GHC: ghc helloworld.hs Executing the compiled file will result in the output "Hello, World!" being printed to the screen: ./helloworld Hello, World! Alternatively, runhaskell or runghc make it possible to run the program in interpreted mode without having to compile it: runhaskell helloworld.hs The interactive REPL can also be used instead of compiling. It comes shipped with most Haskell environments, such as ghci which comes with the GHC compiler: ghci> putStrLn "Hello World!" Hello, World! ghci> Alternatively, load scripts into ghci from a file using load (or :l): ghci> :load helloworld :reload (or :r) reloads everything in ghci: Prelude> :l helloworld.hs [1 of 1] Compiling Main ( helloworld.hs, interpreted ) *Main> :r Ok, modules loaded: Main. Explanation: This first line is a type signature, declaring the type of main: main :: IO () Values of type IO () describe actions which can interact with the outside world. GoalKicker.com – Haskell Notes for Professionals 4 Because Haskell has a fully-fledged Hindley-Milner type system which allows for automatic type inference, type signatures are technically optional: if you simply omit the main :: IO (), the compiler will be able to infer the type on its own by analyzing the definition of main. However, it is very much considered bad style not to write type signatures for top-level definitions. The reasons include: Type signatures in Haskell are a very helpful piece of documentation because the type system is so expressive that you often can see what sort of thing a function is good for simply by looking at its type. This “documentation” can be conveniently accessed with tools like GHCi. And unlike normal documentation, the compiler's type checker will make sure it actually matches the function definition! Type signatures keep bugs local. If you make a mistake in a definition without providing its type signature, the compiler may not immediately report an error but instead simply infer a nonsensical type for it, with which it actually typechecks. You may then get a cryptic error message when using that value. With a signature, the compiler is very good at spotting bugs right where they happen. This second line does the actual work: main = putStrLn "Hello, World!" If you come from an imperative language, it may be helpful to note that this definition can also be written as: main = do { putStrLn "Hello, World!" ; return () } Or equivalently (Haskell has layout-based parsing; but beware mixing tabs and spaces inconsistently which will confuse this mechanism): main = do putStrLn "Hello, World!" return () Each line in a do block represents some monadic (here, I/O) computation, so that the whole do block represents the overall action comprised of these sub-steps by combining them in a manner specific to the given monad (for I/O this means just executing them one after another). The do syntax is itself a syntactic sugar for monads, like IO here, and return is a no-op action producing its argument without performing any side effects or additional computations which might be part of a particular monad definition. The above is the same as defining main = putStrLn "Hello, World!", because the value putStrLn "Hello, World!" already has the type IO (). Viewed as a “statement”, putStrLn "Hello, World!" can be seen as a complete program, and you simply define main to refer to this program. You can look up the signature of putStrLn online: putStrLn :: String -> IO () -- thus, putStrLn (v :: String) :: IO () putStrLn is a function that takes a string as its argument and outputs an I/O-action (i.e. a value representing a program that the runtime can execute). The runtime always executes the action named main, so we simply need to define it as equal to putStrLn "Hello, World!". GoalKicker.com – Haskell Notes for Professionals 5 Section 1.3: Factorial The factorial function is a Haskell "Hello World!" (and for functional programming generally) in the sense that it succinctly demonstrates basic principles of the language. Variation 1 fac :: (Integral a) => a -> a fac n = product [1..n] Live demo Integral is the class of integral number types. Examples include Int and Integer. (Integral a) => places a constraint on the type a to be in said class fac :: a -> a says that fac is a function that takes an a and returns an a product is a function that accumulates all numbers in a list by multiplying them together. [1..n] is special notation which desugars to enumFromTo 1 n, and is the range of numbers 1 ≤ x ≤ n. Variation 2 fac :: (Integral a) => a -> a fac 0 = 1 fac n = n * fac (n - 1) Live demo This variation uses pattern matching to split the function definition into separate cases. The first definition is invoked if the argument is 0 (sometimes called the stop condition) and the second definition otherwise (the order of definitions is significant). It also exemplifies recursion as fac refers to itself. It is worth noting that, due to rewrite rules, both versions of fac will compile to identical machine code when using GHC with optimizations activated. So, in terms of efficiency, the two would be equivalent. Section 1.4: Fibonacci, Using Lazy Evaluation Lazy evaluation means Haskell will evaluate only list items whose values are needed. The basic recursive definition is: f (0) <- 0 f (1) <- 1 f (n) <- f (n-1) + f (n-2) If evaluated directly, it will be very slow. But, imagine we have a list that records all the results, fibs !! n <- f (n) Then ┌──────┐ ┌──────┐ ┌──────┐ │ f(0) │ │ f(1) │ │ f(2) │ fibs -> 0 : 1 : │ + │ : │ + │ : │ + │ : ..... │ f(1) │ │ f(2) │ │ f(3) │ └──────┘ └──────┘ └──────┘ ┌────────────────────────────────────────┐ GoalKicker.com – Haskell Notes for Professionals 6 │ f(0) : f(1) : f(2) : ..... │ └────────────────────────────────────────┘ -> 0 : 1 : + ┌────────────────────────────────────────┐ │ f(1) : f(2) : f(3) : ..... │ └────────────────────────────────────────┘ This is coded as: fibn n = fibs !! n where fibs = 0 : 1 : map f [2..] f n = fibs !! (n-1) + fibs !! (n-2) Or even as GHCi> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs) GHCi> take 10 fibs [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] zipWith makes a list by applying a given binary function to corresponding elements of the two lists given to it, so zipWith (+) [x1, x2, ...] [y1, y2, ...] is equal to [x1 + y1, x2 + y2, ...]. Another way of writing fibs is with the scanl function: GHCi> let fibs = 0 : scanl (+) 1 fibs GHCi> take 10 fibs [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] scanl builds the list of partial results that foldl would produce, working from left to right along the input list. That is, scanl f z0 [x1, x2, ...] is equal to [z0, z1, z2, ...] where z1 = f z0 x1; z2 = f z1 x2; .... Thanks to lazy evaluation, both functions define infinite lists without computing them out entirely. That is, we can write a fib function, retrieving the nth element of the unbounded Fibonacci sequence: GHCi> let fib n = fibs !! n -- (!!) being the list subscript operator -- or in point-free style: GHCi> let fib = (fibs !!) GHCi> fib 9 34 Section 1.5: Primes A few most salient variants: Below 100 import Data.List ( (\\) ) ps100 = ((([2..100] \\ [4,6..100]) \\ [6,9..100]) \\ [10,15..100]) \\ [14,21..100] -- = (((2:[3,5..100]) \\ [9,15..100]) \\ [25,35..100]) \\ [49,63..100] -- = (2:[3,5..100]) \\ ([9,15..100] ++ [25,35..100] ++ [49,63..100]) Unlimited Sieve of Eratosthenes, using data-ordlist package: GoalKicker.com – Haskell Notes for Professionals 7 import qualified Data.List.Ordered ps = 2 : _Y ((3:) . minus [5,7..] . unionAll . map (\p -> [p*p, p*p+2*p..])) _Y g = g (_Y g) -- = g (g (_Y g)) = g (g (g (g (...)))) = g . g . g . g . ... Traditional (a sub-optimal trial division sieve) ps = sieve [2..] where sieve (x:xs) = [x] ++ sieve [y | y <- xs, rem y x > 0] -- = map head ( iterate (\(x:xs) -> filter ((> 0).(`rem` x)) xs) [2..] ) Optimal trial division ps = 2 : [n | n <- [3..], all ((> 0).rem n) $ takeWhile ((<= n).(^2)) ps] -- = 2 : [n | n <- [3..], foldr (\p r-> p*p > n || (rem n p > 0 && r)) True ps] Transitional From trial division to sieve of Eratosthenes: [n | n <- [2..], []==[i | i <- [2..n-1], j <- [0,i..n], j==n]] The Shortest Code nubBy (((>1).).gcd) [2..] -- i.e., nubBy (\a b -> gcd a b > 1) [2..] nubBy is also from Data.List, like (\\). Section 1.6: Declaring Values We can declare a series of expressions in the REPL like this: Prelude> let x = 5 Prelude> let y = 2 * 5 + x Prelude> let result = y * 10 Prelude> x 5 Prelude> y 15 Prelude> result 150 To declare the same values in a file we write the following: -- demo.hs module Demo where -- We declare the name of our module so -- it can be imported by name in a project. x = 5 y = 2 * 5 + x result = y * 10 GoalKicker.com – Haskell Notes for Professionals 8 Module names are capitalized, unlike variable names. GoalKicker.com – Haskell Notes for Professionals 9 Chapter 2: Overloaded Literals Section 2.1: Strings The type of the literal Without any extensions, the type of a string literal – i.e., something between double quotes – is just a string, aka list of characters: Prelude> :t "foo" "foo" :: [Char] However, when the OverloadedStrings extension is enabled, string literals become polymorphic, similar to number literals: Prelude> :set -XOverloadedStrings Prelude> :t "foo" "foo" :: Data.String.IsString t => t This allows us to define values of string-like types without the need for any explicit conversions. In essence, the OverloadedStrings extension just wraps every string literal in the generic fromString conversion function, so if the context demands e.g. the more efficient Text instead of String, you don't need to worry about that yourself. Using string literals {-# LANGUAGE OverloadedStrings #-} import Data.Text (Text, pack) import Data.ByteString (ByteString, pack) withString :: String withString = "Hello String" -- The following two examples are only allowed with OverloadedStrings withText :: Text withText = "Hello Text" -- instead of: withText = Data.Text.pack "Hello Text" withBS :: ByteString withBS = "Hello ByteString" -- instead of: withBS = Data.ByteString.pack "Hello ByteString" Notice how we were able to construct values of Text and ByteString in the same way we construct ordinary String (or [Char]) Values, rather than using each types pack function to encode the string explicitly. For more information on the OverloadedStrings language extension, see the extension documentation. Section 2.2: Floating Numeral The type of the literal Prelude> :t 1.0 1.0 :: Fractional a => a Choosing a concrete type with annotations You can specify the type with a type annotation. The only requirement is that the type must have a Fractional GoalKicker.com – Haskell Notes for Professionals 10 instance. Prelude> 1.0 :: Double 1.0 it :: Double Prelude> 1.0 :: Data.Ratio.Ratio Int 1 % 1 it :: GHC.Real.Ratio Int if not the compiler will complain Prelude> 1.0 :: Int : No instance for (Fractional Int) arising from the literal `1.0' In the expression: 1.0 :: Int In an equation for `it': it = 1.0 :: Int Section 2.3: Integer Numeral The type of the literal Prelude> :t 1 1 :: Num a => a choosing a concrete type with annotations You can specify the type as long as the target type is Num with an annotation: Prelude> 1 :: Int 1 it :: Int Prelude> 1 :: Double 1.0 it :: Double Prelude> 1 :: Word 1 it :: Word if not the compiler will complain Prelude> 1 :: String : No instance for (Num String) arising from the literal `1' In the expression: 1 :: String In an equation for `it': it = 1 :: String Section 2.4: List Literals GHC's OverloadedLists extension allows you to construct list-like data structures with the list literal syntax. This allows you to Data.Map like this: > :set -XOverloadedLists > import qualified Data.Map as M > M.lookup "foo" [("foo", 1), ("bar", 2)] Just 1 GoalKicker.com – Haskell Notes for Professionals 11 Instead of this (note the use of the extra M.fromList): > import Data.Map as M > M.lookup "foo" (M.fromList [("foo", 1), ("bar", 2)]) Just 1 GoalKicker.com – Haskell Notes for Professionals 12 Chapter 3: Foldable Foldable is the class of types t :: * -> * which admit a folding operation. A fold aggregates the elements of a structure in a well-defined order, using a combining function. Section 3.1: Definition of Foldable class Foldable t where {-# MINIMAL foldMap | foldr #-} foldMap :: Monoid m => (a -> m) -> t a -> m foldMap f = foldr (mappend . f) mempty foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo #. f) t) z -- and a number of optional methods Intuitively (though not technically), Foldable structures are containers of elements a which allow access to their elements in a well-defined order. The foldMap operation maps each element of the container to a Monoid and collapses them using the Monoid structure. Section 3.2: An instance of Foldable for a binary tree To instantiate Foldable you need to provide a definition for at least foldMap or foldr. data Tree a = Leaf | Node (Tree a) a (Tree a) instance Foldable Tree where foldMap f Leaf = mempty foldMap f (Node l x r) = foldMap f l `mappend` f x `mappend` foldMap f r foldr f acc Leaf = acc foldr f acc (Node l x r) = foldr f (f x (foldr f acc r)) l This implementation performs an in-order traversal of the tree. ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf) -- +--'b'--+ -- | | -- +-'a'-+ +-'c'-+ -- | | | | -- * * * * ghci> toList myTree "abc" The DeriveFoldable extension allows GHC to generate Foldable instances based on the structure of the type. We can vary the order of the machine-written traversal by adjusting the layout of the Node constructor. data Inorder a = ILeaf | INode (Inorder a) a (Inorder a) -- as before deriving Foldable GoalKicker.com – Haskell Notes for Professionals 13 data Preorder a = PrLeaf | PrNode a (Preorder a) (Preorder a) deriving Foldable data Postorder a = PoLeaf | PoNode (Postorder a) (Postorder a) a deriving Foldable -- injections from the earlier Tree type inorder :: Tree a -> Inorder a inorder Leaf = ILeaf inorder (Node l x r) = INode (inorder l) x (inorder r) preorder :: Tree a -> Preorder a preorder Leaf = PrLeaf preorder (Node l x r) = PrNode x (preorder l) (preorder r) postorder :: Tree a -> Postorder a postorder Leaf = PoLeaf postorder (Node l x r) = PoNode (postorder l) (postorder r) x ghci> toList (inorder myTree) "abc" ghci> toList (preorder myTree) "bac" ghci> toList (postorder myTree) "acb" Section 3.3: Counting the elements of a Foldable structure length counts the occurrences of elements a in a foldable structure t a. ghci> length [7, 2, 9] -- t ~ [] 3 ghci> length (Right 'a') -- t ~ Either e 1 -- 'Either e a' may contain zero or one 'a' ghci> length (Left "foo") -- t ~ Either String 0 ghci> length (3, True) -- t ~ (,) Int 1 -- '(c, a)' always contains exactly one 'a' length is defined as being equivalent to: class Foldable t where -- ... length :: t a -> Int length = foldl' (\c _ -> c+1) 0 Note that this return type Int restricts the operations that can be performed on values obtained by calls to the length function. fromIntegralis a useful function that allows us to deal with this problem. Section 3.4: Folding a structure in reverse Any fold can be run in the opposite direction with the help of the Dual monoid, which flips an existing monoid so that aggregation goes backwards. newtype Dual a = Dual { getDual :: a } GoalKicker.com – Haskell Notes for Professionals 14 instance Monoid m => Monoid (Dual m) where mempty = Dual mempty (Dual x) `mappend` (Dual y) = Dual (y `mappend` x) When the underlying monoid of a foldMap call is flipped with Dual, the fold runs backwards; the following Reverse type is defined in Data.Functor.Reverse: newtype Reverse t a = Reverse { getReverse :: t a } instance Foldable t => Foldable (Reverse t) where foldMap f = getDual . foldMap (Dual . f) . getReverse We can use this machinery to write a terse reverse for lists: reverse :: [a] -> [a] reverse = toList . Reverse Section 3.5: Flattening a Foldable structure into a list toList flattens a Foldable structure t a into a list of as. ghci> toList [7, 2, 9] -- t ~ [] [7, 2, 9] ghci> toList (Right 'a') -- t ~ Either e "a" ghci> toList (Left "foo") -- t ~ Either String [] ghci> toList (3, True) -- t ~ (,) Int [True] toList is defined as being equivalent to: class Foldable t where -- ... toList :: t a -> [a] toList = foldr (:) [] Section 3.6: Performing a side-eect for each element of a Foldable structure traverse_ executes an Applicative action for every element in a Foldable structure. It ignores the action's result, keeping only the side-effects. (For a version which doesn't discard results, use Traversable.) -- using the Writer applicative functor (and the Sum monoid) ghci> runWriter $ traverse_ (\x -> tell (Sum x)) [1,2,3] ((),Sum {getSum = 6}) -- using the IO applicative functor ghci> traverse_ putStrLn (Right "traversing") traversing ghci> traverse_ putStrLn (Left False) -- nothing printed for_ is traverse_ with the arguments flipped. It resembles a foreach loop in an imperative language. ghci> let greetings = ["Hello", "Bonjour", "Hola"] ghci> :{ GoalKicker.com – Haskell Notes for Professionals 15 ghci| for_ greetings $ \greeting -> do ghci| print (greeting ++ " Stack Overflow!") ghci| :} "Hello Stack Overflow!" "Bonjour Stack Overflow!" "Hola Stack Overflow!" sequenceA_ collapses a Foldable full of Applicative actions into a single action, ignoring the result. ghci> let actions = [putStrLn "one", putStLn "two"] ghci> sequenceA_ actions one two traverse_ is defined as being equivalent to: traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f () traverse_ f = foldr (\x action -> f x *> action) (pure ()) sequenceA_ is defined as: sequenceA_ :: (Foldable t, Applicative f) -> t (f a) -> f () sequenceA_ = traverse_ id Moreover, when the Foldable is also a Functor, traverse_ and sequenceA_ have the following relationship: traverse_ f = sequenceA_ . fmap f Section 3.7: Flattening a Foldable structure into a Monoid foldMap maps each element of the Foldable structure to a Monoid, and then combines them into a single value. foldMap and foldr can be defined in terms of one another, which means that instances of Foldable need only give a definition for one of them. class Foldable t where foldMap :: Monoid m => (a -> m) -> t a -> m foldMap f = foldr (mappend . f) mempty Example usage with the Product monoid: product :: (Num n, Foldable t) => t n -> n product = getProduct . foldMap Product Section 3.8: Checking if a Foldable structure is empty null returns True if there are no elements a in a foldable structure t a, and False if there is one or more. Structures for which null is True have a length of 0. ghci> null [] True ghci> null [14, 29] False ghci> null Nothing True ghci> null (Right 'a') GoalKicker.com – Haskell Notes for Professionals 16 False ghci> null ('x', 3) False null is defined as being equivalent to: class Foldable t where -- ... null :: t a -> Bool null = foldr (\_ _ -> False) True GoalKicker.com – Haskell Notes for Professionals 17 Chapter 4: Traversable The Traversable class generalises the function formerly known as mapM :: Monad m => (a -> m b) -> [a] -> m [b] to work with Applicative effects over structures other than lists. Section 4.1: Definition of Traversable class (Functor t, Foldable t) => Traversable t where {-# MINIMAL traverse | sequenceA #-} traverse :: Applicative f => (a -> f b) -> t a -> f (t b) traverse f = sequenceA . fmap f sequenceA :: Applicative f => t (f a) -> f (t a) sequenceA = traverse id mapM :: Monad m => (a -> m b) -> t a -> m (t b) mapM = traverse sequence :: Monad m => t (m a) -> m (t a) sequence = sequenceA Traversable structures t are finitary containers of elements a which can be operated on with an effectful "visitor" operation. The visitor function f :: a -> f b performs a side-effect on each element of the structure and traverse composes those side-effects using Applicative. Another way of looking at it is that sequenceA says Traversable structures commute with Applicatives. Section 4.2: Traversing a structure in reverse A traversal can be run in the opposite direction with the help of the Backwards applicative functor, which flips an existing applicative so that composed effects take place in reversed order. newtype Backwards f a = Backwards { forwards :: f a } instance Applicative f => Applicative (Backwards f) where pure = Backwards . pure Backwards ff <*> Backwards fx = Backwards ((\x f -> f x) <$> fx <*> ff) Backwards can be put to use in a "reversed traverse". When the underlying applicative of a traverse call is flipped with Backwards, the resulting effect happens in reverse order. newtype Reverse t a = Reverse { getReverse :: t a } instance Traversable t => Traversable (Reverse t) where traverse f = fmap Reverse . forwards . traverse (Backwards . f) . getReverse ghci> traverse print (Reverse "abc") 'c' 'b' 'a' The Reverse newtype is found under Data.Functor.Reverse. GoalKicker.com – Haskell Notes for Professionals 18 Section 4.3: An instance of Traversable for a binary tree Implementations of traverse usually look like an implementation of fmap lifted into an Applicative context. data Tree a = Leaf | Node (Tree a) a (Tree a) instance Traversable Tree where traverse f Leaf = pure Leaf traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r This implementation performs an in-order traversal of the tree. ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf) -- +--'b'--+ -- | | -- +-'a'-+ +-'c'-+ -- | | | | -- * * * * ghci> traverse print myTree 'a' 'b' 'c' The DeriveTraversable extension allows GHC to generate Traversable instances based on the structure of the type. We can vary the order of the machine-written traversal by adjusting the layout of the Node constructor. data Inorder a = ILeaf | INode (Inorder a) a (Inorder a) -- as before deriving (Functor, Foldable, Traversable) -- also using DeriveFunctor and DeriveFoldable data Preorder a = PrLeaf | PrNode a (Preorder a) (Preorder a) deriving (Functor, Foldable, Traversable) data Postorder a = PoLeaf | PoNode (Postorder a) (Postorder a) a deriving (Functor, Foldable, Traversable) -- injections from the earlier Tree type inorder :: Tree a -> Inorder a inorder Leaf = ILeaf inorder (Node l x r) = INode (inorder l) x (inorder r) preorder :: Tree a -> Preorder a preorder Leaf = PrLeaf preorder (Node l x r) = PrNode x (preorder l) (preorder r) postorder :: Tree a -> Postorder a postorder Leaf = PoLeaf postorder (Node l x r) = PoNode (postorder l) (postorder r) x ghci> traverse print (inorder myTree) 'a' 'b' 'c' ghci> traverse print (preorder myTree) GoalKicker.com – Haskell Notes for Professionals 19 'b' 'a' 'c' ghci> traverse print (postorder myTree) 'a' 'c' 'b' Section 4.4: Traversable structures as shapes with contents If a type t is Traversable then values of t a can be split into two pieces: their "shape" and their "contents": data Traversed t a = Traversed { shape :: t (), contents :: [a] } where the "contents" are the same as what you'd "visit" using a Foldable instance. Going one direction, from t a to Traversed t a doesn't require anything but Functor and Foldable break :: (Functor t, Foldable t) => t a -> Traversed t a break ta = Traversed (fmap (const ()) ta) (toList ta) but going back uses the traverse function crucially import Control.Monad.State -- invariant: state is non-empty pop :: State [a] a pop = state $ \(a:as) -> (a, as) recombine :: Traversable t => Traversed t a -> t a recombine (Traversed s c) = evalState (traverse (const pop) s) c The Traversable laws require that break . recombine and recombine . break are both identity. Notably, this means that there are exactly the right number elements in contents to fill shape completely with no left-overs. Traversed t is Traversable itself. The implementation of traverse works by visiting the elements using the list's instance of Traversable and then reattaching the inert shape to the result. instance Traversable (Traversed t) where traverse f (Traversed s c) = fmap (Traversed s) (traverse f c) Section 4.5: Instantiating Functor and Foldable for a Traversable structure import Data.Traversable as Traversable data MyType a = -- ... instance Traversable MyType where traverse = -- ... Every Traversable structure can be made a Foldable Functor using the fmapDefault and foldMapDefault functions found in Data.Traversable. instance Functor MyType where fmap = Traversable.fmapDefault GoalKicker.com – Haskell Notes for Professionals 20 instance Foldable MyType where foldMap = Traversable.foldMapDefault fmapDefault is defined by running traverse in the Identity applicative functor. newtype Identity a = Identity { runIdentity :: a } instance Applicative Identity where pure = Identity Identity f <*> Identity x = Identity (f x) fmapDefault :: Traversable t => (a -> b) -> t a -> t b fmapDefault f = runIdentity . traverse (Identity . f) foldMapDefault is defined using the Const applicative functor, which ignores its parameter while accumulating a monoidal value. newtype Const c a = Const { getConst :: c } instance Monoid m => Applicative (Const m) where pure _ = Const mempty Const x <*> Const y = Const (x `mappend` y) foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m foldMapDefault f = getConst . traverse (Const . f) Section 4.6: Transforming a Traversable structure with the aid of an accumulating parameter The two mapAccum functions combine the operations of folding and mapping. -- A Traversable structure -- | -- A seed value | -- | | -- |-| |---| mapAccumL, mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) -- |------------------| |--------| -- | | -- A folding function which produces a new mapped | -- element 'c' and a new accumulator value 'a' | -- | -- Final accumulator value -- and mapped structure These functions generalise fmap in that they allow the mapped values to depend on what has happened earlier in the fold. They generalise foldl/foldr in that they map the structure in place as well as reducing it to a value. For example, tails can be implemented using mapAccumR and its sister inits can be implemented using mapAccumL. tails, inits :: [a] -> [[a]] tails = uncurry (:) . mapAccumR (\xs x -> (x:xs, xs)) [] inits = uncurry snoc . mapAccumL (\xs x -> (x `snoc` xs, xs)) [] where snoc x xs = xs ++ [x] ghci> tails "abc" ["abc", "bc", "c", ""] ghci> inits "abc" GoalKicker.com – Haskell Notes for Professionals 21 ["", "a", "ab", "abc"] mapAccumL is implemented by traversing in the State applicative functor. {-# LANGUAGE DeriveFunctor #-} newtype State s a = State { runState :: s -> (s, a) } deriving Functor instance Applicative (State s) where pure x = State $ \s -> (s, x) State ff <*> State fx = State $ \s -> let (t, f) = ff s (u, x) = fx t in (u, f x) mapAccumL f z t = runState (traverse (State . flip f) t) z mapAccumR works by running mapAccumL in reverse. mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse Section 4.7: Transposing a list of lists Noting that zip transposes a tuple of lists into a list of tuples, ghci> uncurry zip ([1,2],[3,4]) [(1,3), (2,4)] and the similarity between the types of transpose and sequenceA, -- transpose exchanges the inner list with the outer list -- +---+-->--+-+ -- | | | | transpose :: [[a]] -> [[a]] -- | | | | -- +-+-->--+---+ -- sequenceA exchanges the inner Applicative with the outer Traversable -- +------>------+ -- | | sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a) -- | | -- +--->---+ the idea is to use []'s Traversable and Applicative structure to deploy sequenceA as a sort of n-ary zip, zipping together all the inner lists together pointwise. []'s default "prioritised choice" Applicative instance is not appropriate for our use - we need a "zippy" Applicative. For this we use the ZipList newtype, found in Control.Applicative. newtype ZipList a = ZipList { getZipList :: [a] } instance Applicative ZipList where pure x = ZipList (repeat x) ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs) Now we get transpose for free, by traversing in the ZipList Applicative. transpose :: [[a]] -> [[a]] GoalKicker.com – Haskell Notes for Professionals 22 transpose = getZipList . traverse ZipList ghci> let myMatrix = [[1,2,3],[4,5,6],[7,8,9]] ghci> transpose myMatrix [[1,4,7],[2,5,8],[3,6,9]] GoalKicker.com – Haskell Notes for Professionals 23 Chapter 5: Lens Lens is a library for Haskell that provides lenses, isomorphisms, folds, traversals, getters and setters, which exposes a uniform interface for querying and manipulating arbitrary structures, not unlike Java's accessor and mutator concepts. Section 5.1: Lenses for records Simple record {-# LANGUAGE TemplateHaskell #-} import Control.Lens data Point = Point { _x :: Float, _y :: Float } makeLenses ''Point Lenses x and y are created. let p = Point 5.0 6.0 p ^. x -- returns 5.0 set x 10 p -- returns Point { _x = 10.0, _y = 6.0 } p & x +~ 1 -- returns Point { _x = 6.0, _y = 6.0 } Managing records with repeating fields names data Person = Person { _personName :: String } makeFields ''Person Creates a type class HasName, lens name for Person, and makes Person an instance of HasName. Subsequent records will be added to the class as well: data Entity = Entity { _entityName :: String } makeFields ''Entity The Template Haskell extension is required for makeFields to work. Technically, it's entirely possible to create the lenses made this way via other means, e.g. by hand. Section 5.2: Manipulating tuples with Lens Getting ("a", 1) ^. _1 -- returns "a" ("a", 1) ^. _2 -- returns 1 Setting ("a", 1) & _1 .~ "b" -- returns ("b", 1) Modifying ("a", 1) & _2 %~ (+1) -- returns ("a", 2) both Traversal GoalKicker.com – Haskell Notes for Professionals 24 (1, 2) & both *~ 2 -- returns (2, 4) Section 5.3: Lens and Prism A Lens' s a means that you can always find an a within any s. A Prism' s a means that you can sometimes find that s actually just is a but sometimes it's something else. To be more clear, we have _1 :: Lens' (a, b) a because any tuple always has a first element. We have _Just :: Prism' (Maybe a) a because sometimes Maybe a is actually an a value wrapped in Just but sometimes it's Nothing. With this intuition, some standard combinators can be interpreted parallel to one another view :: Lens' s a -> (s -> a) "gets" the a out of the s set :: Lens' s a -> (a -> s -> s) "sets" the a slot in s review :: Prism' s a -> (a -> s) "realizes" that an a could be an s preview :: Prism' s a -> (s -> Maybe a) "attempts" to turn an s into an a. Another way to think about it is that a value of type Lens' s a demonstrates that s has the same structure as (r, a) for some unknown r. On the other hand, Prism' s a demonstrates that s has the same structure as Either r a for some r. We can write those four functions above with this knowledge: -- `Lens' s a` is no longer supplied, instead we just *know* that `s ~ (r, a)` view :: (r, a) -> a view (r, a) = a set :: a -> (r, a) -> (r, a) set a (r, _) = (r, a) -- `Prism' s a` is no longer supplied, instead we just *know* that `s ~ Either r a` review :: a -> Either r a review a = Right a preview :: Either r a -> Maybe a preview (Left _) = Nothing preview (Right a) = Just a Section 5.4: Stateful Lenses Lens operators have useful variants that operate in stateful contexts. They are obtained by replacing ~ with = in the operator name. (+~) :: Num a => ASetter s t a a -> a -> s -> t (+=) :: (MonadState s m, Num a) => ASetter' s a -> a -> m () Note: The stateful variants aren't expected to change the type, so they have the Lens' or Simple Lens' signatures. Getting rid of & chains If lens-ful operations need to be chained, it often looks like this: change :: A -> A GoalKicker.com – Haskell Notes for Professionals 25 change a = a & lensA %~ operationA & lensB %~ operationB & lensC %~ operationC This works thanks to the associativity of &. The stateful version is clearer, though. change a = flip execState a $ do lensA %= operationA lensB %= operationB lensC %= operationC If lensX is actually id, the whole operation can of course be executed directly by just lifting it with modify. Imperative code with structured state Assuming this example state: data Point = Point { _x :: Float, _y :: Float } data Entity = Entity { _position :: Point, _direction :: Float } data World = World { _entities :: [Entity] } makeLenses ''Point makeLenses ''Entity makeLenses ''World We can write code that resembles classic imperative languages, while still allowing us to use benefits of Haskell: updateWorld :: MonadState World m => m () updateWorld = do -- move the first entity entities . ix 0 . position . x += 1 -- do some operation on all of them entities . traversed . position %= \p -> p `pointAdd` ... -- or only on a subset entities . traversed . filtered (\e -> e ^. position.x > 100) %= ... Section 5.5: Lenses compose If you have a f :: Lens' a b and a g :: Lens' b c then f . g is a Lens' a c gotten by following f first and then g. Notably: Lenses compose as functions (really they just are functions) If you think of the view functionality of Lens, it seems like data flows "left to right"—this might feel backwards to your normal intuition for function composition. On the other hand, it ought to feel natural if you think of .- notation like how it happens in OO languages. More than just composing Lens with Lens, (.) can be used to compose nearly any "Lens-like" type together. It's not always easy to see what the result is since the type becomes tougher to follow, but you can use the lens chart to figure it out. The composition x . y has the type of the least-upper-bound of the types of both x and y in that chart. Section 5.6: Writing a lens without Template Haskell To demystify Template Haskell, suppose you have GoalKicker.com – Haskell Notes for Professionals 26 data Example a = Example { _foo :: Int, _bar :: a } then makeLenses 'Example produces (more or less) foo :: Lens' (Example a) Int bar :: Lens (Example a) (Example b) a b There's nothing particularly magical going on, though. You can write these yourself: foo :: Lens' (Example a) Int -- :: Functor f => (Int -> f Int) -> (Example a -> f (Example a)) ;; expand the alias foo wrap (Example foo bar) = fmap (\newFoo -> Example newFoo bar) (wrap foo) bar :: Lens (Example a) (Example b) a b -- :: Functor f => (a -> f b) -> (Example a -> f (Example b)) ;; expand the alias bar wrap (Example foo bar) = fmap (\newBar -> Example foo newBar) (wrap bar) Essentially, you want to "visit" your lens' "focus" with the wrap function and then rebuild the "entire" type. Section 5.7: Fields with makeFields (This example copied from this StackOverflow answer) Let's say you have a number of different data types that all ought to have a lens with the same name, in this case capacity. The makeFields slice will create a class that accomplish this without namespace conflicts. {-# LANGUAGE FunctionalDependencies , MultiParamTypeClasses , TemplateHaskell #-} module Foo where import Control.Lens data Foo = Foo { fooCapacity :: Int } deriving (Eq, Show) $(makeFields ''Foo) data Bar = Bar { barCapacity :: Double } deriving (Eq, Show) $(makeFields ''Bar) Then in ghci: *Foo λ let f = Foo 3 | b = Bar 7 | b :: Bar GoalKicker.com – Haskell Notes for Professionals 27 f :: Foo *Foo λ fooCapacity f 3 it :: Int *Foo λ barCapacity b 7.0 it :: Double *Foo λ f ^. capacity 3 it :: Int *Foo λ b ^. capacity 7.0 it :: Double λ :info HasCapacity class HasCapacity s a | s -> a where capacity :: Lens' s a -- Defined at Foo.hs:14:3 instance HasCapacity Foo Int -- Defined at Foo.hs:14:3 instance HasCapacity Bar Double -- Defined at Foo.hs:19:3 So what it's actually done is declared a class HasCapacity s a, where capacity is a Lens' from s to a (a is fixed once s is known). It figured out the name "capacity" by stripping off the (lowercased) name of the data type from the field; I find it pleasant not to have to use an underscore on either the field name or the lens name, since sometimes record syntax is actually what you want. You can use makeFieldsWith and the various lensRules to have some different options for calculating the lens names. In case it helps, using ghci -ddump-splices Foo.hs: [1 of 1] Compiling Foo ( Foo.hs, interpreted ) Foo.hs:14:3-18: Splicing declarations makeFields ''Foo ======> class HasCapacity s a | s -> a where capacity :: Lens' s a instance HasCapacity Foo Int where {-# INLINE capacity #-} capacity = iso (\ (Foo x_a7fG) -> x_a7fG) Foo Foo.hs:19:3-18: Splicing declarations makeFields ''Bar ======> instance HasCapacity Bar Double where {-# INLINE capacity #-} capacity = iso (\ (Bar x_a7ne) -> x_a7ne) Bar Ok, modules loaded: Foo. So the first splice made the class HasCapcity and added an instance for Foo; the second used the existing class and made an instance for Bar. This also works if you import the HasCapcity class from another module; makeFields can add more instances to the existing class and spread your types out across multiple modules. But if you use it again in another module GoalKicker.com – Haskell Notes for Professionals 28 where you haven't imported the class, it'll make a new class (with the same name), and you'll have two separate overloaded capacity lenses that are not compatible. Section 5.8: Classy Lenses In addition to the standard makeLenses function for generating Lenses, Control.Lens.TH also offers the makeClassy function. makeClassy has the same type and works in essentially the same way as makeLenses, with one key difference. In addition to generating the standard lenses and traversals, if the type has no arguments, it will also create a class describing all the datatypes which possess the type as a field. For example data Foo = Foo { _fooX, _fooY :: Int } makeClassy ''Foo will create class HasFoo t where foo :: Simple Lens t Foo instance HasFoo Foo where foo = id fooX, fooY :: HasFoo t => Simple Lens t Int Section 5.9: Traversals A Traversal' s a shows that s has 0-to-many as inside of it. toListOf :: Traversal' s a -> (s -> [a]) Any type t which is Traversable automatically has that traverse :: Traversal (t a) a. We can use a Traversal to set or map over all of these a values > set traverse 1 [1..10] [1,1,1,1,1,1,1,1,1,1] > over traverse (+1) [1..10] [2,3,4,5,6,7,8,9,10,11] A f :: Lens' s a says there's exactly one a inside of s. A g :: Prism' a b says there are either 0 or 1 bs in a. Composing f . g gives us a Traversal' s b because following f and then g shows how there there are 0-to-1 bs in s. GoalKicker.com – Haskell Notes for Professionals 29 Chapter 6: QuickCheck Section 6.1: Declaring a property At its simplest, a property is a function which returns a Bool. prop_reverseDoesNotChangeLength xs = length (reverse xs) == length xs A property declares a high-level invariant of a program. The QuickCheck test runner will evaluate the function with 100 random inputs and check that the result is always True. By convention, functions that are properties have names which start with prop_. Section 6.2: Randomly generating data for custom types The Arbitrary class is for types that can be randomly generated by QuickCheck. The minimal implementation of Arbitrary is the arbitrary method, which runs in the Gen monad to produce a random value. Here is an instance of Arbitrary for the following datatype of non-empty lists. import Test.QuickCheck.Arbitrary (Arbitrary(..)) import Test.QuickCheck.Gen (oneof) import Control.Applicative ((<$>), (<*>)) data NonEmpty a = End a | Cons a (NonEmpty a) instance Arbitrary a => Arbitrary (NonEmpty a) where arbitrary = oneof [ -- randomly select one of the cases from the list End <$> arbitrary, -- call a's instance of Arbitrary Cons <$> arbitrary <*> -- call a's instance of Arbitrary arbitrary -- recursively call NonEmpty's instance of Arbitrary ] Section 6.3: Using implication (==>) to check properties with preconditions prop_evenNumberPlusOneIsOdd :: Integer -> Property prop_evenNumberPlusOneIsOdd x = even x ==> odd (x + 1) If you want to check that a property holds given that a precondition holds, you can use the ==> operator. Note that if it's very unlikely for arbitrary inputs to match the precondition, QuickCheck can give up early. prop_overlySpecific x y = x == 0 ==> x * y == 0 ghci> quickCheck prop_overlySpecific *** Gave up! Passed only 31 tests. Section 6.4: Checking a single property The quickCheck function tests a property on 100 random inputs. GoalKicker.com – Haskell Notes for Professionals 30 ghci> quickCheck prop_reverseDoesNotChangeLength +++ OK, passed 100 tests. If a property fails for some input, quickCheck prints out a counterexample. prop_reverseIsAlwaysEmpty xs = reverse xs == [] -- plainly not true for all xs ghci> quickCheck prop_reverseIsAlwaysEmpty *** Failed! Falsifiable (after 2 tests): [()] Section 6.5: Checking all the properties in a file quickCheckAll is a Template Haskell helper which finds all the definitions in the current file whose name begins with prop_ and tests them. {-# LANGUAGE TemplateHaskell #-} import Test.QuickCheck (quickCheckAll) import Data.List (sort) idempotent :: Eq a => (a -> a) -> a -> Bool idempotent f x = f (f x) == f x prop_sortIdempotent = idempotent sort -- does not begin with prop_, will not be picked up by the test runner sortDoesNotChangeLength xs = length (sort xs) == length xs return [] main = $quickCheckAll Note that the return [] line is required. It makes definitions textually above that line visible to Template Haskell. $ runhaskell QuickCheckAllExample.hs === prop_sortIdempotent from tree.hs:7 === +++ OK, passed 100 tests. Section 6.6: Limiting the size of test data It can be difficult to test functions with poor asymptotic complexity using quickcheck as the random inputs are not usually size bounded. By adding an upper bound on the size of the input we can still test these expensive functions. import Data.List(permutations) import Test.QuickCheck longRunningFunction :: [a] -> Int longRunningFunction xs = length (permutations xs) factorial :: Integral a => a -> a factorial n = product [1..n] prop_numberOfPermutations xs = longRunningFunction xs == factorial (length xs) ghci> quickCheckWith (stdArgs { maxSize = 10}) prop_numberOfPermutations GoalKicker.com – Haskell Notes for Professionals 31 By using quickCheckWith with a modified version of stdArgs we can limit the size of the inputs to be at most 10. In this case, as we are generating lists, this means we generate lists of up to size 10. Our permutations function doesn't take too long to run for these short lists but we can still be reasonably confident that our definition is correct. GoalKicker.com – Haskell Notes for Professionals 32 Chapter 7: Common GHC Language Extensions Section 7.1: RankNTypes Imagine the following situation: foo :: Show a => (a -> String) -> String -> Int -> IO () foo show' string int = do putStrLn (show' string) putStrLn (show' int) Here, we want to pass in a function that converts a value into a String, apply that function to both a string parameter and and int parameter and print them both. In my mind, there is no reason this should fail! We have a function that works on both types of the parameters we're passing in. Unfortunately, this won't type check! GHC infers the a type based off of its first occurrence in the function body. That is, as soon as we hit: putStrLn (show' string) GHC will infer that show' :: String -> String, since string is a String. It will proceed to blow up while trying to show' int. RankNTypes lets you instead write the type signature as follows, quantifying over all functions that satisfy the show' type: foo :: (forall a. Show a => (a -> String)) -> String -> Int -> IO () This is rank 2 polymorphism: We are asserting that the show' function must work for all as within our function, and the previous implementation now works. The RankNTypes extension allows arbitrary nesting of forall ... blocks in type signatures. In other words, it allows rank N polymorphism. Section 7.2: OverloadedStrings Normally, string literals in Haskell have a type of String (which is a type alias for [Char]). While this isn't a problem for smaller, educational programs, real-world applications often require more efficient storage such as Text or ByteString. OverloadedStrings simply changes the type of literals to "test" :: Data.String.IsString a => a Allowing them to be directly passed to functions expecting such a type. Many libraries implement this interface for their string-like types including Data.Text and Data.ByteString which both provide certain time and space advantages over [Char]. There are also some unique uses of OverloadedStrings like those from the Postgresql-simple library which allows SQL queries to be written in double quotes like a normal string, but provides protections against improper concatenation, a notorious source of SQL injection attacks. GoalKicker.com – Haskell Notes for Professionals 33 To create a instance of the IsString class you need to impliment the fromString function. Example†: data Foo = A | B | Other String deriving Show instance IsString Foo where fromString "A" = A fromString "B" = B fromString xs = Other xs tests :: [ Foo ] tests = [ "A", "B", "Testing" ] † This example courtesy of Lyndon Maydwell (sordina on GitHub) found here. Section 7.3: BinaryLiterals Standard Haskell allows you to write integer literals in decimal (without any prefix), hexadecimal (preceded by 0x or 0X), and octal (preceded by 0o or 0O). The BinaryLiterals extension adds the option of binary (preceded by 0b or 0B). 0b1111 == 15 -- evaluates to: True Section 7.4: ExistentialQuantification This is a type system extension that allows types that are existentially quantified, or, in other words, have type variables that only get instantiated at runtime†. A value of existential type is similar to an abstract-base-class reference in OO languages: you don't know the exact type in contains, but you can constrain the class of types. data S = forall a. Show a => S a or equivalently, with GADT syntax: {-# LANGUAGE GADTs #-} data S where S :: Show a => a -> S Existential types open the door to things like almost-heterogenous containers: as said above, there can actually be various types in an S value, but all of them can be shown, hence you can also do instance Show S where show (S a) = show a -- we rely on (Show a) from the above Now we can create a collection of such objects: ss = [S 5, S "test", S 3.0] Which also allows us to use the polymorphic behaviour: mapM_ print ss Existentials can be very powerful, but note that they are actually not necessary very often in Haskell. In the example GoalKicker.com – Haskell Notes for Professionals 34 above, all you can actually do with the Show instance is show (duh!) the values, i.e. create a string representation. The entire S type therefore contains exactly as much information as the string you get when showing it. Therefore, it is usually better to simply store that string right away, especially since Haskell is lazy and therefore the string will at first only be an unevaluated thunk anyway. On the other hand, existentials cause some unique problems. For instance, the way the type information is “hidden” in an existential. If you pattern-match on an S value, you will have the contained type in scope (more precisely, its Show instance), but this information can never escape its scope, which therefore becomes a bit of a “secret society”: the compiler doesn't let anything escape the scope except values whose type is already known from the outside. This can lead to strange errors like Couldn't match type ‘a0’ with ‘()’ ‘a0’ is untouchable. †Contrast this with ordinary parametric polymorphism, which is generally resolved at compile time (allowing full type erasure). Existential types are different from Rank-N types – these extensions are, roughly speaking, dual to each other: to actually use values of an existential type, you need a (possibly constrained-) polymorphic function, like show in the example. A polymorphic function is universally quantified, i.e. it works for any type in a given class, whereas existential quantification means it works for some particular type which is a priori unknown. If you have a polymorphic function, that's sufficient, however to pass polymorphic functions as such as arguments, you need {-# LANGUAGE Rank2Types #-}: genShowSs :: (∀ x . Show x => x -> String) -> [S] -> [String] genShowSs f = map (\(S a) -> f a) Section 7.5: LambdaCase A syntactic extension that lets you write \case in place of \arg -> case arg of. Consider the following function definition: dayOfTheWeek :: Int -> String dayOfTheWeek 0 = "Sunday" dayOfTheWeek 1 = "Monday" dayOfTheWeek 2 = "Tuesday" dayOfTheWeek 3 = "Wednesday" dayOfTheWeek 4 = "Thursday" dayOfTheWeek 5 = "Friday" dayOfTheWeek 6 = "Saturday" If you want to avoid repeating the function name, you might write something like: dayOfTheWeek :: Int -> String dayOfTheWeek i = case i of 0 -> "Sunday" 1 -> "Monday" 2 -> "Tuesday" 3 -> "Wednesday" 4 -> "Thursday" 5 -> "Friday" 6 -> "Saturday" GoalKicker.com – Haskell Notes for Professionals 35 Using the LambdaCase extension, you can write that as a function expression, without having to name the argument: {-# LANGUAGE LambdaCase #-} dayOfTheWeek :: Int -> String dayOfTheWeek = \case 0 -> "Sunday" 1 -> "Monday" 2 -> "Tuesday" 3 -> "Wednesday" 4 -> "Thursday" 5 -> "Friday" 6 -> "Saturday" Section 7.6: FunctionalDependencies If you have a multi-parameter type-class with arguments a, b, c, and x, this extension lets you express that the type x can be uniquely identified from a, b, and c: class SomeClass a b c x | a b c -> x where ... When declaring an instance of such class, it will be checked against all other instances to make sure that the functional dependency holds, that is, no other instance with same a b c but different x exists. You can specify multiple dependencies in a comma-separated list: class OtherClass a b c d | a b -> c d, a d -> b where ... For example in MTL we can see: class MonadReader r m| m -> r where ... instance MonadReader r ((->) r) where ... Now, if you have a value of type MonadReader a ((->) Foo) => a, the compiler can infer that a ~ Foo, since the second argument completely determines the first, and will simplify the type accordingly. The SomeClass class can be thought of as a function of the arguments a b c that results in x. Such classes can be used to do computations in the typesystem. Section 7.7: FlexibleInstances Regular instances require: All instance types must be of the form (T a1 ... an) where a1 ... an are *distinct type variables*, and each type variable appears at most once in the instance head. That means that, for example, while you can create an instance for [a] you can't create an instance for specifically [Int].; FlexibleInstances relaxes that: class C a where -- works out of the box instance C [a] where GoalKicker.com – Haskell Notes for Professionals 36 -- requires FlexibleInstances instance C [Int] where Section 7.8: GADTs Conventional algebraic datatypes are parametric in their type variables. For example, if we define an ADT like data Expr a = IntLit Int | BoolLit Bool | If (Expr Bool) (Expr a) (Expr a) with the hope that this will statically rule out non-well-typed conditionals, this will not behave as expected since the type of IntLit :: Int -> Expr a is universially quantified: for any choice of a, it produces a value of type Expr a. In particular, for a ~ Bool, we have IntLit :: Int -> Expr Bool, allowing us to construct something like If (IntLit 1) e1 e2 which is what the type of the If constructor was trying to rule out. Generalised Algebraic Data Types allows us to control the resulting type of a data constructor so that they are not merely parametric. We can rewrite our Expr type as a GADT like this: data Expr a where IntLit :: Int -> Expr Int BoolLit :: Bool -> Expr Bool If :: Expr Bool -> Expr a -> Expr a -> Expr a Here, the type of the constructor IntLit is Int -> Expr Int, and so IntLit 1 :: Expr Bool will not typecheck. Pattern matching on a GADT value causes refinement of the type of the term returned. For example, it is possible to write an evaluator for Expr a like this: crazyEval :: Expr a -> a crazyEval (IntLit x) = -- Here we can use `(+)` because x :: Int x + 1 crazyEval (BoolLit b) = -- Here we can use `not` because b :: Bool not b crazyEval (If b thn els) = -- Because b :: Expr Bool, we can use `crazyEval b :: Bool`. -- Also, because thn :: Expr a and els :: Expr a, we can pass either to -- the recursive call to `crazyEval` and get an a back crazyEval $ if crazyEval b then thn else els Note that we are able to use (+) in the above definitions because when e.g. IntLit x is pattern matched, we also learn that a ~ Int (and likewise for not and if_then_else_ when a ~ Bool). Section 7.9: TupleSections A syntactic extension that allows applying the tuple constructor (which is an operator) in a section way: (a,b) == (,) a b -- With TupleSections (a,b) == (,) a b == (a,) b == (,b) a N-tuples It also works for tuples with arity greater than two GoalKicker.com – Haskell Notes for Professionals 37 (,2,) 1 3 == (1,2,3) Mapping This can be useful in other places where sections are used: map (,"tag") [1,2,3] == [(1,"tag"), (2, "tag"), (3, "tag")] The above example without this extension would look like this: map (\a -> (a, "tag")) [1,2,3] Section 7.10: OverloadedLists added in GHC 7.8. OverloadedLists, similar to OverloadedStrings, allows list literals to be desugared as follows: [] -- fromListN 0 [] [x] -- fromListN 1 (x : []) [x .. ] -- fromList (enumFrom x) This comes handy when dealing with types such as Set, Vector and Maps. ['0' .. '9'] :: Set Char [1 .. 10] :: Vector Int [("default",0), (k1,v1)] :: Map String Int ['a' .. 'z'] :: Text IsList class in GHC.Exts is intended to be used with this extension. IsList is equipped with one type function, Item, and three functions, fromList :: [Item l] -> l, toList :: l -> [Item l] and fromListN :: Int -> [Item l] -> l where fromListN is optional. Typical implementations are: instance IsList [a] where type Item [a] = a fromList = id toList = id instance (Ord a) => IsList (Set a) where type Item (Set a) = a fromList = Set.fromList toList = Set.toList Examples taken from OverloadedLists – GHC. Section 7.11: MultiParamTypeClasses It's a very common extension that allows type classes with multiple type parameters. You can think of MPTC as a relation between types. {-# LANGUAGE MultiParamTypeClasses #-} class Convertable a b where convert :: a -> b instance Convertable Int Float where GoalKicker.com – Haskell Notes for Professionals 38 convert i = fromIntegral i The order of parameters matters. MPTCs can sometimes be replaced with type families. Section 7.12: UnicodeSyntax An extension that allows you to use Unicode characters in lieu of certain built-in operators and names. ASCII Unicode Use(s) :: ∷ has type -> → function types, lambdas, case branches, etc. => ⇒ class constraints forall ∀ explicit polymorphism <- ← do notation * ★ the type (or kind) of types (e.g., Int :: ★) >- proc notation for Arrows -< proc notation for Arrows >>- proc notation for Arrows -<< proc notation for Arrows For example: runST :: (forall s. ST s a) -> a would become runST ∷ (∀ s. ST s a) → a Note that the * vs. ★ example is slightly different: since * isn't reserved, ★ also works the same way as * for multiplication, or any other function named (*), and vice-versa. For example: ghci> 2 ★ 3 6 ghci> let (*) = (+) in 2 ★ 3 5 ghci> let (★) = (-) in 2 * 3 -1 Section 7.13: PatternSynonyms Pattern synonyms are abstractions of patterns similar to how functions are abstractions of expressions. For this example, let's look at the interface Data.Sequence exposes, and let's see how it can be improved with pattern synonyms. The Seq type is a data type that, internally, uses a complicated representation to achieve good asymptotic complexity for various operations, most notably both O(1) (un)consing and (un)snocing. But this representation is unwieldy and some of its invariants cannot be expressed in Haskell's type system. Because of this, the Seq type is exposed to users as an abstract type, along with invariant-preserving accessor and constructor functions, among them: GoalKicker.com – Haskell Notes for Professionals 39 empty :: Seq a (<|) :: a -> Seq a -> Seq a data ViewL a = EmptyL | a :< (Seq a) viewl :: Seq a -> ViewL a (|>) :: Seq a -> a -> Seq a data ViewR a = EmptyR | (Seq a) :> a viewr :: Seq a -> ViewR a But using this interface can be a bit cumbersome: uncons :: Seq a -> Maybe (a, Seq a) uncons xs = case viewl xs of x :< xs' -> Just (x, xs') EmptyL -> Nothing We can use view patterns to clean it up somewhat: {-# LANGUAGE ViewPatterns #-} uncons :: Seq a -> Maybe (a, Seq a) uncons (viewl -> x :< xs) = Just (x, xs) uncons _ = Nothing Using the PatternSynonyms language extension, we can give an even nicer interface by allowing pattern matching to pretend that we have a cons- or a snoc-list: {-# LANGUAGE PatternSynonyms #-} import Data.Sequence (Seq) import qualified Data.Sequence as Seq pattern Empty :: Seq a pattern Empty <- (Seq.viewl -> Seq.EmptyL) pattern (:<) :: a -> Seq a -> Seq a pattern x :< xs <- (Seq.viewl -> x Seq.:< xs) pattern (:>) :: Seq a -> a -> Seq a pattern xs :> x <- (Seq.viewr -> xs Seq.:> x) This allows us to write uncons in a very natural style: uncons :: Seq a -> Maybe (a, Seq a) uncons (x :< xs) = Just (x, xs) uncons _ = Nothing Section 7.14: ScopedTypeVariables ScopedTypeVariables let you refer to universally quantified types inside of a declaration. To be more explicit: import Data.Monoid foo :: forall a b c. (Monoid b, Monoid c) => (a, b, c) -> (b, c) -> (a, b, c) foo (a, b, c) (b', c') = (a :: a, b'', c'') where (b'', c'') = (b <> b', c <> c') :: (b, c) GoalKicker.com – Haskell Notes for Professionals 40 The important thing is that we can use a, b and c to instruct the compiler in subexpressions of the declaration (the tuple in the where clause and the first a in the final result). In practice, ScopedTypeVariables assist in writing complex functions as a sum of parts, allowing the programmer to add type signatures to intermediate values that don't have concrete types. Section 7.15: RecordWildCards See RecordWildCards GoalKicker.com – Haskell Notes for Professionals 41 Chapter 8: Free Monads Section 8.1: Free monads split monadic computations into data structures and interpreters For instance, a computation involving commands to read and write from the prompt: First we describe the "commands" of our computation as a Functor data type {-# LANGUAGE DeriveFunctor #-} data TeletypeF next = PrintLine String next | ReadLine (String -> next) deriving Functor Then we use Free to create the "Free Monad over TeletypeF" and build some basic operations. import Control.Monad.Free (Free, liftF, iterM) type Teletype = Free TeletypeF printLine :: String -> Teletype () printLine str = liftF (PrintLine str ()) readLine :: Teletype String readLine = liftF (ReadLine id) Since Free f is a Monad whenever f is a Functor, we can use the standard Monad combinators (including do notation) to build Teletype computations. import Control.Monad -- we can use the standard combinators echo :: Teletype () echo = readLine >>= printLine mockingbird :: Teletype a mockingbird = forever echo Finally, we write an "interpreter" turning Teletype a values into something we know how to work with like IO a interpretTeletype :: Teletype a -> IO a interpretTeletype = foldFree run where run :: TeletypeF a -> IO a run (PrintLine str x) = putStrLn *> return x run (ReadLine f) = fmap f getLine Which we can use to "run" the Teletype a computation in IO > interpretTeletype mockingbird hello hello goodbye goodbye this will go on forever this will go on forever GoalKicker.com – Haskell Notes for Professionals 42 Section 8.2: The Freer monad There's an alternative formulation of the free monad called the Freer (or Prompt, or Operational) monad. The Freer monad doesn't require a Functor instance for its underlying instruction set, and it has a more recognisably list-like structure than the standard free monad. The Freer monad represents programs as a sequence of atomic instructions belonging to the instruction set i :: * -> *. Each instruction uses its parameter to declare its return type. For example, the set of base instructions for the State monad are as follows: data StateI s a where Get :: StateI s s -- the Get instruction returns a value of type 's' Put :: s -> StateI s () -- the Put instruction contains an 's' as an argument and returns () Sequencing these instructions takes place with the :>>= constructor. :>>= takes a single instruction returning an a and prepends it to the rest of the program, piping its return value into the continuation. In other words, given an instruction returning an a, and a function to turn an a into a program returning a b, :>>= will produce a program returning a b. data Freer i a where Return :: a -> Freer i a (:>>=) :: i a -> (a -> Freer i b) -> Freer i b Note that a is existentially quantified in the :>>= constructor. The only way for an interpreter to learn what a is is by pattern matching on the GADT i. Aside: The co-Yoneda lemma tells us that Freer is isomorphic to Free. Recall the definition of the CoYoneda functor: data CoYoneda i b where CoYoneda :: i a -> (a -> b) -> CoYoneda i b Freer i is equivalent to Free (CoYoneda i). If you take Free's constructors and set f ~ CoYoneda i, you get: Pure :: a -> Free (CoYoneda i) a Free :: CoYoneda i (Free (CoYoneda i) b) -> Free (CoYonda i) b ~ i a -> (a -> Free (CoYoneda i) b) -> Free (CoYoneda i) b from which we can recover Freer i's constructors by just setting Freer i ~ Free (CoYoneda i). Because CoYoneda i is a Functor for any i, Freer is a Monad for any i, even if i isn't a Functor. instance Monad (Freer i) where return = Return Return x >>= f = f x (i :>>= g) >>= f = i :>>= fmap (>>= f) g -- using `(->) r`'s instance of Functor, so fmap = (.) Interpreters can be built for Freer by mapping instructions to some handler monad. foldFreer :: Monad m => (forall x. i x -> m x) -> Freer i a -> m a foldFreer eta (Return x) = return x foldFreer eta (i :>>= f) = eta i >>= (foldFreer eta . f) GoalKicker.com – Haskell Notes for Professionals 43 For example, we can interpret the Freer (StateI s) monad using the regular State s monad as a handler: runFreerState :: Freer (StateI s) a -> s -> (a, s) runFreerState = State.runState . foldFreer toState where toState :: StateI s a -> State s a toState Get = State.get toState (Put x) = State.put x Section 8.3: How do foldFree and iterM work? There are some functions to help tear down Free computations by interpreting them into another monad m: iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> (Free f a -> m a) and foldFree :: Monad m => (forall x. f x -> m x) -> (Free f a -> m a). What are they doing? First let's see what it would take to tear down an interpret a Teletype a function into IO manually. We can see Free f a as being defined data Free f a = Pure a | Free (f (Free f a)) The Pure case is easy: interpretTeletype :: Teletype a -> IO a interpretTeletype (Pure x) = return x interpretTeletype (Free teletypeF) = _ Now, how to interpret a Teletype computation that was built with the Free constructor? We'd like to arrive at a value of type IO a by examining teletypeF :: TeletypeF (Teletype a). To start with, we'll write a function runIO :: TeletypeF a -> IO a which maps a single layer of the free monad to an IO action: runIO :: TeletypeF a -> IO a runIO (PrintLine msg x) = putStrLn msg *> return x runIO (ReadLine k) = fmap k getLine Now we can use runIO to fill in the rest of interpretTeletype. Recall that teletypeF :: TeletypeF (Teletype a) is a layer of the TeletypeF functor which contains the rest of the Free computation. We'll use runIO to interpret the outermost layer (so we have runIO teletypeF :: IO (Teletype a)) and then use the IO monad's >>= combinator to interpret the returned Teletype a. interpretTeletype :: Teletype a -> IO a interpretTeletype (Pure x) = return x interpretTeletype (Free teletypeF) = runIO teletypeF >>= interpretTeletype The definition of foldFree is just that of interpretTeletype, except that the runIO function has been factored out. As a result, foldFree works independently of any particular base functor and of any target monad. foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a foldFree eta (Pure x) = return x foldFree eta (Free fa) = eta fa >>= foldFree eta foldFree has a rank-2 type: eta is a natural transformation. We could have given foldFree a type of Monad m => (f (Free f a) -> m (Free f a)) -> Free f a -> m a, but that gives eta the liberty of inspecting the Free computation inside the f layer. Giving foldFree this more restrictive type ensures that eta can only process a single layer at a time. GoalKicker.com – Haskell Notes for Professionals 44 iterM does give the folding function the ability to examine the subcomputation. The (monadic) result of the previous iteration is available to the next, inside f's parameter. iterM is analogous to a paramorphism whereas foldFree is like a catamorphism. iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a iterM phi (Pure x) = return x iterM phi (Free fa) = phi (fmap (iterM phi) fa) Section 8.4: Free Monads are like fixed points Compare the definition of Free to that of Fix: data Free f a = Return a | Free (f (Free f a)) newtype Fix f = Fix { unFix :: f (Fix f) } In particular, compare the type of the Free constructor with the type of the Fix constructor. Free layers up a functor just like Fix, except that Free has an additional Return a case. GoalKicker.com – Haskell Notes for Professionals 45 Chapter 9: Type Classes Typeclasses in Haskell are a means of defining the behaviour associated with a type separately from that type's definition. Whereas, say, in Java, you'd define the behaviour as part of the type's definition -- i.e. in an interface, abstract class or concrete class -- Haskell keeps these two things separate. There are a number of typeclasses already defined in Haskell's base package. The relationship between these is illustrated in the Remarks section below. Section 9.1: Eq All basic datatypes (like Int, String, Eq a => [a]) from Prelude except for functions and IO have instances of Eq. If a type instantiates Eq it means that we know how to compare two values for value or structural equality. > 3 == 2 False > 3 == 3 True Required methods (==) :: Eq a => a -> a -> Boolean or (/=) :: Eq a => a -> a -> Boolean (if only one is implemented, the other defaults to the negation of the defined one) Defines (==) :: Eq a => a -> a -> Boolean (/=) :: Eq a => a -> a -> Boolean Direct superclasses None Notable subclasses Ord Section 9.2: Monoid Types instantiating Monoid include lists, numbers, and functions with Monoid return values, among others. To instantiate Monoid a type must support an associative binary operation (mappend or (<>)) which combines its values, and have a special "zero" value (mempty) such that combining a value with it does not change that value: mempty <> x == x x <> mempty == x x <> (y <> z) == (x <> y) <> z Intuitively, Monoid types are "list-like" in that they support appending values together. Alternatively, Monoid types can be thought of as sequences of values for which we care about the order but not the grouping. For instance, a binary tree is a Monoid, but using the Monoid operations we cannot witness its branching structure, only a traversal of its values (see Foldable and Traversable). Required methods mempty :: Monoid m => m GoalKicker.com – Haskell Notes for Professionals 46 mappend :: Monoid m => m -> m -> m Direct superclasses None Section 9.3: Ord Types instantiating Ord include, e.g., Int, String, and [a] (for types a where there's an Ord a instance). If a type instantiates Ord it means that we know a “natural” ordering of values of that type. Note, there are often many possible choices of the “natural” ordering of a type and Ord forces us to favor one. Ord provides the standard (<=), (<), (>), (>=) operators but interestingly defines them all using a custom algebraic data type data Ordering = LT | EQ | GT compare :: Ord a => a -> a -> Ordering Required methods compare :: Ord a => a -> a -> Ordering or (<=) :: Ord a => a -> a -> Boolean (the standard’s default compare method uses (<=) in its implementation) Defines compare :: Ord a => a -> a -> Ordering (<=) :: Ord a => a -> a -> Boolean (<) :: Ord a => a -> a -> Boolean (>=) :: Ord a => a -> a -> Boolean (>) :: Ord a => a -> a -> Boolean min :: Ord a => a -> a -> a max :: Ord a => a -> a -> a Direct superclasses Eq Section 9.4: Num The most general class for number types, more precisely for rings, i.e. numbers that can be added and subtracted and multiplied in the usual sense, but not necessarily divided. This class contains both integral types (Int, Integer, Word32 etc.) and fractional types (Double, Rational, also complex numbers etc.). In case of finite types, the semantics are generally understood as modular arithmetic, i.e. with over- and underflow†. Note that the rules for the numerical classes are much less strictly obeyed than the monad or monoid laws, or those for equality comparison. In particular, floating-point numbers generally obey laws only in a approximate sense. The methods fromInteger :: Num a => Integer -> a. convert an integer to the general number type (wrapping around the range, if necessary). Haskell number literals can be understood as a monomorphic Integer literal with the general conversion around it, so you can use the literal 5 in both an Int context and a Complex Double GoalKicker.com – Haskell Notes for Professionals 47 setting. (+) :: Num a => a -> a -> a. Standard addition, generally understood as associative and commutative, i.e., a + (b + c) ≡ (a + b) + c a + b ≡ b + a (-) :: Num a => a -> a -> a. Subtraction, which is the inverse of addition: (a - b) + b ≡ (a + b) - b ≡ a (*) :: Num a => a -> a -> a. Multiplication, an associative operation that's distributive over addition: a * (b * c) ≡ (a * b) * c a * (b + c) ≡ a * b + a * c for the most common instances, multiplication is also commutative, but this is definitely not a requirement. negate :: Num a => a -> a. The full name of the unary negation operator. -1 is syntactic sugar for negate 1. -a ≡ negate a ≡ 0 - a abs :: Num a => a -> a. The absolute-value function always gives a non-negative result of the same magnitude abs (-a) ≡ abs a abs (abs a) ≡ abs a abs a ≡ 0 should only happen if a ≡ 0. For real types it's clear what non-negative means: you always have abs a >= 0. Complex etc. types don't have a well-defined ordering, however the result of abs should always lie in the real subset‡ (i.e. give a number that could also be written as a single number literal without negation). signum :: Num a => a -> a. The sign function, according to the name, yields only -1 or 1, depending on the sign of the argument. Actually, that's only true for nonzero real numbers; in general signum is better understood as the normalising function: abs (signum a) ≡ 1 -- unless a≡0 signum a * abs a ≡ a -- This is required to be true for all Num instances Note that section 6.4.4 of the Haskell 2010 Report explicitly requires this last equality to hold for any valid Num instance. Some libraries, notably linear and hmatrix, have a much laxer understanding of what the Num class is for: they treat it just as a way to overload the arithmetic operators. While this is pretty straightforward for + and -, it already becomes troublesome with * and more so with the other methods. For instance, should * mean matrix multiplication or element-wise multiplication? GoalKicker.com – Haskell Notes for Professionals 48 It is arguably a bad idea to define such non-number instances; please consider dedicated classes such as VectorSpace. † In particular, the “negatives” of unsigned types are wrapped around to large positive, e.g. (-4 :: Word32) == 4294967292. ‡ This is widely not fulfilled: vector types do not have a real subset. The controversial Num-instances for such types generally define abs and signum element-wise, which mathematically speaking doesn't really make sense. Section 9.5: Maybe and the Functor Class In Haskell, data types can have arguments just like functions. Take the Maybe type for example. Maybe is a very useful type which allows us to represent the idea of failure, or the possiblity thereof. In other words, if there is a possibility that a computation will fail, we use the Maybe type there. Maybe acts kind of like a wrapper for other types, giving them additional functionality. Its actual declaration is fairly simple. Maybe a = Just a | Nothing What this tells is that a Maybe comes in two forms, a Just, which represents success, and a Nothing, which represents failure. Just takes one argument which determines the type of the Maybe, and Nothing takes none. For example, the value Just "foo" will have type Maybe String, which is a string type wrapped with the additional Maybe functionality. The value Nothing has type Maybe a where a can be any type. This idea of wrapping types to give them additional functionality is a very useful one, and is applicable to more than just Maybe. Other examples include the Either, IO and list types, each providing different functionality. However, there are some actions and abilities which are common to all of these wrapper types. The most notable of these is the ability to modify the encapsulated value. It is common to think of these kinds of types as boxes which can have values placed in them. Different boxes hold different values and do different things, but none are useful without being able to access the contents within. To encapsulate this idea, Haskell comes with a standard typeclass, named Functor. It is defined as follows. class Functor f where fmap :: (a -> b) -> f a -> f b As can be seen, the class has a single function, fmap, of two arguments. The first argument is a function from one type, a, to another, b. The second argument is a functor (wrapper type) containing a value of type a. It returns a functor (wrapper type) containing a value of type b. In simple terms, fmap takes a function and applies to the value inside of a functor. It is the only function necessary for a type to be a member of the Functor class, but it is extremely useful. Functions operating on functors that have more specific applications can be found in the Applicative and Monad typeclasses. Section 9.6: Type class inheritance: Ord type class Haskell supports a notion of class extension. For example, the class Ord inherits all of the operations in Eq, but in addition has a compare function that returns an Ordering between values. Ord may also contain the common order comparison operators, as well as a min method and a max method. The => notation has the same meaning as it does in a function signature and requires type a to implement Eq, in GoalKicker.com – Haskell Notes for Professionals 49 order to implement Ord. data Ordering = EQ | LT | GT class Eq a => Ord a where compare :: Ord a => a -> a -> Ordering (<) :: Ord a => a -> a -> Bool (<=) :: Ord a => a -> a -> Bool (>) :: Ord a => a -> a -> Bool (>=) :: Ord a => a -> a -> Bool min :: Ord a => a -> a -> a max :: Ord a => a -> a -> a All of the methods following compare can be derived from it in a number of ways: x < y = compare x y == LT x <= y = x < y || x == y -- Note the use of (==) inherited from Eq x > y = not (x <= y) x >= y = not (x < y) min x y = case compare x y of EQ -> x LT -> x GT -> y max x y = case compare x y of EQ -> x LT -> y GT -> x Type classes that themselves extend Ord must implement at least either the compare method or the (<=) method themselves, which builds up the directed inheritance lattice. GoalKicker.com – Haskell Notes for Professionals 50 Chapter 10: IO Section 10.1: Getting the 'a' "out of" 'IO a' A common question is "I have a value of IO a, but I want to do something to that a value: how do I get access to it?" How can one operate on data that comes from the outside world (for example, incrementing a number typed by the user)? The point is that if you use a pure function on data obtained impurely, then the result is still impure. It depends on what the user did! A value of type IO a stands for a "side-effecting computation resulting in a value of type a" which can only be run by (a) composing it into main and (b) compiling and executing your program. For that reason, there is no way within pure Haskell world to "get the a out". Instead, we want to build a new computation, a new IO value, which makes use of the a value at runtime. This is another way of composing IO values and so again we can use do-notation: -- assuming myComputation :: IO Int getMessage :: Int -> String getMessage int = "My computation resulted in: " ++ show int newComputation :: IO () newComputation = do int <- myComputation -- we "bind" the result of myComputation to a name, 'int' putStrLn $ getMessage int -- 'int' holds a value of type Int Here we're using a pure function (getMessage) to turn an Int into a String, but we're using do notation to make it be applied to the result of an IO computation myComputation when (after) that computation runs. The result is a bigger IO computation, newComputation. This technique of using pure functions in an impure context is called lifting. Section 10.2: IO defines your program's `main` action To make a Haskell program executable you must provide a file with a main function of type IO () main :: IO () main = putStrLn "Hello world!" When Haskell is compiled it examines the IO data here and turns it into a executable. When we run this program it will print Hello world!. If you have values of type IO a other than main they won't do anything. other :: IO () other = putStrLn "I won't get printed" main :: IO () main = putStrLn "Hello world!" Compiling this program and running it will have the same effect as the last example. The code in other is ignored. In order to make the code in other have runtime effects you have to compose it into main. No IO values not eventually composed into main will have any runtime effect. To compose two IO values sequentially you can use do notation: GoalKicker.com – Haskell Notes for Professionals 51 other :: IO () other = putStrLn "I will get printed... but only at the point where I'm composed into main" main :: IO () main = do putStrLn "Hello world!" other When you compile and run this program it outputs Hello world! I will get printed... but only at the point where I'm composed into main Note that the order of operations is described by how other was composed into main and not the definition order. Section 10.3: Checking for end-of-file conditions A bit counter-intuitive to the way most other languages' standard I/O libraries do it, Haskell's isEOF does not require you to perform a read operation before checking for an EOF condition; the runtime will do it for you. import System.IO( isEOF ) eofTest :: Int -> IO () eofTest line = do end <- isEOF if end then putStrLn $ "End-of-file reached at line " ++ show line ++ "." else do getLine eofTest $ line + 1 main :: IO () main = eofTest 1 Input: Line #1. Line #2. Line #3. Output: End-of-file reached at line 4. Section 10.4: Reading all contents of standard input into a string main = do input <- getContents putStr input Input: GoalKicker.com – Haskell Notes for Professionals 52 This is an example sentence. And this one is, too! Output: This is an example sentence. And this one is, too! Note: This program will actually print parts of the output before all of the input has been fully read in. This means that, if, for example, you use getContents over a 50MiB file, Haskell's lazy evaluation and garbage collector will ensure that only the parts of the file that are currently needed (read: indispensable for further execution) will be loaded into memory. Thus, the 50MiB file won't be loaded into memory at once. Section 10.5: Role and Purpose of IO Haskell is a pure language, meaning that expressions cannot have side effects. A side effect is anything that the expression or function does other than produce a value, for example, modify a global counter or print to standard output. In Haskell, side-effectful computations (specifically, those which can have an effect on the real world) are modelled using IO. Strictly speaking, IO is a type constructor, taking a type and producing a type. For example, IO Int is the type of an I/O computation producing an Int value. The IO type is abstract, and the interface provided for IO ensures that certain illegal values (that is, functions with non-sensical types) cannot exist, by ensuring that all built in functions which perform IO have a return type enclosed in IO. When a Haskell program is run, the computation represented by the Haskell value named main, whose type can be IO x for any type x, is executed. Manipulating IO values There are many functions in the standard library providing typical IO actions that a general purpose programming language should perform, such as reading and writing to file handles. General IO actions are created and combined primarily with two functions: (>>=) :: IO a -> (a -> IO b) -> IO b This function (typically called bind) takes an IO action and a function which returns an IO action, and produces the IO action which is the result of applying the function to the value produced by the first IO action. return :: a -> IO a This function takes any value (i.e., a pure value) and returns the IO computation which does no IO and produces the given value. In other words, it is a no-op I/O action. There are additional general functions which are often used, but all can be written in terms of the two above. For example, (>>) :: IO a -> IO b -> IO b is similar to (>>=) but the result of the first action is ignored. A simple program greeting the user using these functions: main :: IO () main = putStrLn "What is your name?" >> GoalKicker.com – Haskell Notes for Professionals 53 getLine >>= \name -> putStrLn ("Hello " ++ name ++ "!") This program also uses putStrLn :: String -> IO () and getLine :: IO String. Note: the types of certain functions above are actually more general than those types given (namely >>=, >> and return). IO semantics The IO type in Haskell has very similar semantics to that of imperative programming languages. For example, when one writes s1 ; s2 in an imperative language to indicate executing statement s1, then statement s2, one can write s1 >> s2 to model the same thing in Haskell. However, the semantics of IO diverge slightly of what would be expected coming from an imperative background. The return function does not interrupt control flow - it has no effect on the program if another IO action is run in sequence. For example, return () >> putStrLn "boom" correctly prints "boom" to standard output. The formal semantics of IO can given in terms of simple equalities involving the functions in the previous section: return x >>= f ≡ f x, ∀ f x y >>= return ≡ return y, ∀ y (m >>= f) >>= g ≡ m >>= (\x -> (f x >>= g)), ∀ m f g These laws are typically referred to as left identity, right identity, and composition, respectively. They can be stated more naturally in terms of the function (>=>) :: (a -> IO b) -> (b -> IO c) -> a -> IO c (f >=> g) x = (f x) >>= g as follows: return >=> f ≡ f, ∀ f f >=> return ≡ f, ∀ f (f >=> g) >=> h ≡ f >=> (g >=> h), ∀ f g h Lazy IO Functions performing I/O computations are typically strict, meaning that all preceding actions in a sequence of actions must be completed before the next action is begun. Typically this is useful and expected behaviour - putStrLn "X" >> putStrLn "Y" should print "XY". However, certain library functions perform I/O lazily, meaning that the I/O actions required to produce the value are only performed when the value is actually consumed. Examples of such functions are getContents and readFile. Lazy I/O can drastically reduce the performance of a Haskell program, so when using library functions, care should be taken to note which functions are lazy. IO and do notation Haskell provides a simpler method of combining different IO values into larger IO values. This special syntax is known as do notation* and is simply syntactic sugar for usages of the >>=, >> and return functions. The program in the previous section can be written in two different ways using do notation, the first being layout sensitive and the second being layout insensitive: main = do GoalKicker.com – Haskell Notes for Professionals 54 putStrLn "What is your name?" name <- getLine putStrLn ("Hello " ++ name ++ "!") main = do { putStrLn "What is your name?" ; name <- getLine ; putStrLn ("Hello " ++ name ++ "!") } All three programs are exactly equivalent. *Note that do notation is also applicable to a broader class of type constructors called monads. Section 10.6: Writing to stdout Per the Haskell 2010 Language Specification the following are standard IO functions available in Prelude, so no imports are required to use them. putChar :: Char -> IO () - writes a char to stdout Prelude> putChar 'a' aPrelude> -- Note, no new line putStr :: String -> IO () - writes a String to stdout Prelude> putStr "This is a string!" This is a string!Prelude> -- Note, no new line putStrLn :: String -> IO () - writes a String to stdout and adds a new line Prelude> putStrLn "Hi there, this is another String!" Hi there, this is another String! print :: Show a => a -> IO () - writes a an instance of Show to stdout Prelude> print "hi" "hi" Prelude> print 1 1 Prelude> print 'a' 'a' Prelude> print (Just 'a') -- Maybe is an instance of the `Show` type class Just 'a' Prelude> print Nothing Nothing Recall that you can instantiate Show for your own types using deriving: -- In ex.hs data Person = Person { name :: String } deriving Show main = print (Person "Alex") -- Person is an instance of `Show`, thanks to `deriving` Loading & running in GHCi: Prelude> :load ex.hs [1 of 1] Compiling ex ( ex.hs, interpreted ) Ok, modules loaded: ex. *Main> main -- from ex.hs Person {name = "Alex"} *Main> GoalKicker.com – Haskell Notes for Professionals 55 Section 10.7: Reading words from an entire file In Haskell, it often makes sense not to bother with file handles at all, but simply read or write an entire file straight from disk to memory†, and do all the partitioning/processing of the text with the pure string data structure. This avoids mixing IO and program logic, which can greatly help avoiding bugs. -- | The interesting part of the program, which actually processes data -- but doesn't do any IO! reverseWords :: String -> [String] reverseWords = reverse . words -- | A simple wrapper that only fetches the data from disk, lets -- 'reverseWords' do its job, and puts the result to stdout. main :: IO () main = do content <- readFile "loremipsum.txt" mapM_ putStrLn $ reverseWords content If loremipsum.txt contains Lorem ipsum dolor sit amet, consectetur adipiscing elit then the program will output elit adipiscing consectetur amet, sit dolor ipsum Lorem Here, mapM_ went through the list of all words in the file, and printed each of them to a separate line with putStrLn. †If you think this is wasteful on memory, you have a point. Actually, Haskell's laziness can often avoid that the entire file needs to reside in memory simultaneously... but beware, this kind of lazy IO causes its own set of problems. For performance-critical applications, it often makes sense to enforce the entire file to be read at once, strictly; you can do this with the Data.Text version of readFile. Section 10.8: Reading a line from standard input main = do line <- getLine putStrLn line Input: This is an example. Output: This is an example. GoalKicker.com – Haskell Notes for Professionals 56 Section 10.9: Reading from `stdin` As-per the Haskell 2010 Language Specification, the following are standard IO functions available in Prelude, so no imports are required to use them. getChar :: IO Char - read a Char from stdin -- MyChar.hs main = do myChar <- getChar print myChar -- In your shell runhaskell MyChar.hs a -- you enter a and press enter 'a' -- the program prints 'a' getLine :: IO String - read a String from stdin, sans new line character Prelude> getLine Hello there! -- user enters some text and presses enter "Hello there!" read :: Read a => String -> a - convert a String to a value Prelude> read "1" :: Int 1 Prelude> read "1" :: Float 1.0 Prelude> read "True" :: Bool True Other, less common functions are: getContents :: IO String - returns all user input as a single string, which is read lazily as it is needed interact :: (String -> String) -> IO () - takes a function of type String->String as its argument. The entire input from the standard input device is passed to this function as its argument Section 10.10: Parsing and constructing an object from standard input readFloat :: IO Float readFloat = fmap read getLine main :: IO () main = do putStr "Type the first number: " first <- readFloat putStr "Type the second number: " second <- readFloat putStrLn $ show first ++ " + " ++ show second ++ " = " ++ show ( first + second ) Input: Type the first number: 9.5 Type the second number: -2.02 GoalKicker.com – Haskell Notes for Professionals 57 Output: 9.5 + -2.02 = 7.48 Section 10.11: Reading from file handles Like in several other parts of the I/O library, functions that implicitly use a standard stream have a counterpart in System.IO that performs the same job, but with an extra parameter at the left, of type Handle, that represents the stream being handled. For instance, getLine :: IO String has a counterpart hGetLine :: Handle -> IO String. import System.IO( Handle, FilePath, IOMode( ReadMode ), openFile, hGetLine, hPutStr, hClose, hIsEOF, stderr ) import Control.Monad( when ) dumpFile :: Handle -> FilePath -> Integer -> IO () dumpFile handle filename lineNumber = do -- show file contents line by line end <- hIsEOF handle when ( not end ) $ do line <- hGetLine handle putStrLn $ filename ++ ":" ++ show lineNumber ++ ": " ++ line dumpFile handle filename $ lineNumber + 1 main :: IO () main = do hPutStr stderr "Type a filename: " filename <- getLine handle <- openFile filename ReadMode dumpFile handle filename 1 hClose handle Contents of file example.txt: This is an example. Hello, world! This is another example. Input: Type a filename: example.txt Output: example.txt:1: This is an example. example.txt:2: Hello, world! example.txt:3: This is another example GoalKicker.com – Haskell Notes for Professionals 58 Chapter 11: Record Syntax Section 11.1: Basic Syntax Records are an extension of sum algebraic data type that allow fields to be named: data StandardType = StandardType String Int Bool --standard way to create a sum type data RecordType = RecordType { -- the same sum type with record syntax aString :: String , aNumber :: Int , isTrue :: Bool } The field names can then be used to get the named field out of the record > let r = RecordType {aString = "Foobar", aNumber= 42, isTrue = True} > :t r r :: RecordType > :t aString aString :: RecordType -> String > aString r "Foobar" Records can be pattern matched against case r of RecordType{aNumber = x, aString=str} -> ... -- x = 42, str = "Foobar" Notice that not all fields need be named Records are created by naming their fields, but can also be created as ordinary sum types (often useful when the number of fields is small and not likely to change) r = RecordType {aString = "Foobar", aNumber= 42, isTrue = True} r' = RecordType "Foobar" 42 True If a record is created without a named field, the compiler will issue a warning, and the resulting value will be undefined. > let r = RecordType {aString = "Foobar", aNumber= 42} :1:9: Warning: Fields of RecordType not initialized: isTrue > isTrue r Error 'undefined' A field of a record can be updated by setting its value. Unmentioned fields do not change. > let r = RecordType {aString = "Foobar", aNumber= 42, isTrue = True} > let r' = r{aNumber=117} -- r'{aString = "Foobar", aNumber= 117, isTrue = True} It is often useful to create lenses for complicated record types. GoalKicker.com – Haskell Notes for Professionals 59 Section 11.2: Defining a data type with field labels It is possible to define a data type with field labels. data Person = Person { age :: Int, name :: String } This definition differs from a normal record definition as it also defines *record accessors which can be used to access parts of a data type. In this example, two record accessors are defined, age and name, which allow us to access the age and name fields respectively. age :: Person -> Int name :: Person -> String Record accessors are just Haskell functions which are automatically generated by the compiler. As such, they are used like ordinary Haskell functions. By naming fields, we can also use the field labels in a number of other contexts in order to make our code more readable. Pattern Matching lowerCaseName :: Person -> String lowerCaseName (Person { name = x }) = map toLower x We can bind the value located at the position of the relevant field label whilst pattern matching to a new value (in this case x) which can be used on the RHS of a definition. Pattern Matching with NamedFieldPuns lowerCaseName :: Person -> String lowerCaseName (Person { name }) = map toLower name The NamedFieldPuns extension instead allows us to just specify the field label we want to match upon, this name is then shadowed on the RHS of a definition so referring to name refers to the value rather than the record accessor. Pattern Matching with RecordWildcards lowerCaseName :: Person -> String lowerCaseName (Person { .. }) = map toLower name When matching using RecordWildCards, all field labels are brought into scope. (In this specific example, name and age) This extension is slightly controversial as it is not clear how values are brought into scope if you are not sure of the definition of Person. Record Updates setName :: String -> Person -> Person setName newName person = person { name = newName } There is also special syntax for updating data types with field labels. Section 11.3: RecordWildCards {-# LANGUAGE RecordWildCards #-} GoalKicker.com – Haskell Notes for Professionals 60 data Client = Client { firstName :: String , lastName :: String , clientID :: String } deriving (Show) printClientName :: Client -> IO () printClientName Client{..} = do putStrLn firstName putStrLn lastName putStrLn clientID The pattern Client{..} brings in scope all the fields of the constructor Client, and is equivalent to the pattern Client{ firstName = firstName, lastName = lastName, clientID = clientID } It can also be combined with other field matchers like so: Client { firstName = "Joe", .. } This is equivalent to Client{ firstName = "Joe", lastName = lastName, clientID = clientID } Section 11.4: Copying Records while Changing Field Values Suppose you have this type: data Person = Person { name :: String, age:: Int } deriving (Show, Eq) and two values: alex = Person { name = "Alex", age = 21 } jenny = Person { name = "Jenny", age = 36 } a new value of type Person can be created by copying from alex, specifying which values to change: anotherAlex = alex { age = 31 } The values of alex and anotherAlex will now be: Person {name = "Alex", age = 21} Person {name = "Alex", age = 31} Section 11.5: Records with newtype Record syntax can be used with newtype with the restriction that there is exactly one constructor with exactly one field. The benefit here is the automatic creation of a function to unwrap the newtype. These fields are often named starting with run for monads, get for monoids, and un for other types. newtype State s a = State { runState :: s -> (s, a) } newtype Product a = Product { getProduct :: a } newtype Fancy = Fancy { unfancy :: String } GoalKicker.com – Haskell Notes for Professionals 61 -- a fancy string that wants to avoid concatenation with ordinary strings It is important to note that the record syntax is typically never used to form values and the field name is used strictly for unwrapping getProduct $ mconcat [Product 7, Product 9, Product 12] -- > 756 GoalKicker.com – Haskell Notes for Professionals 62 Chapter 12: Partial Application Section 12.1: Sections Sectioning is a concise way to partially apply arguments to infix operators. For example, if we want to write a function which adds "ing" to the end of a word we can use a section to succinctly define a function. > (++ "ing") "laugh" "laughing" Notice how we have partially applied the second argument. Normally, we can only partially apply the arguments in the specified order. We can also use left sectioning to partially apply the first argument. > ("re" ++) "do" "redo" We could equivalently write this using normal prefix partial application: > ((++) "re") "do" "redo" A Note on Subtraction Beginners often incorrectly section negation. > map (-1) [1,2,3] ***error: Could not deduce... This does not work as -1 is parsed as the literal -1 rather than the sectioned operator - applied to 1. The subtract function exists to circumvent this issue. > map (subtract 1) [1,2,3] [0,1,2] Section 12.2: Partially Applied Adding Function We can use partial application to "lock" the first argument. After applying one argument we are left with a function which expects one more argument before returning the result. (+) :: Int -> Int -> Int addOne :: Int -> Int addOne = (+) 1 We can then use addOne in order to add one to an Int. > addOne 5 6 > map addOne [1,2,3] [2,3,4] GoalKicker.com – Haskell Notes for Professionals 63 Section 12.3: Returning a Partially Applied Function Returning partially applied functions is one technique to write concise code. add :: Int -> Int -> Int add x = (+x) add 5 2 In this example (+x) is a partially applied function. Notice that the second parameter to the add function does not need to be specified in the function definition. The result of calling add 5 2 is seven. GoalKicker.com – Haskell Notes for Professionals 64 Chapter 13: Monoid Section 13.1: An instance of Monoid for lists instance Monoid [a] where mempty = [] mappend = (++) Checking the Monoid laws for this instance: mempty `mappend` x = x <-> [] ++ xs = xs -- prepending an empty list is a no-op x `mappend` mempty = x <-> xs ++ [] = xs -- appending an empty list is a no-op x `mappend` (y `mappend` z) = (x `mappend` y) `mappend` z <-> xs ++ (ys ++ zs) = (xs ++ ys) ++ zs -- appending lists is associative Section 13.2: Collapsing a list of Monoids into a single value mconcat :: [a] -> a is another method of the Monoid typeclass: ghci> mconcat [Sum 1, Sum 2, Sum 3] Sum {getSum = 6} ghci> mconcat ["concat", "enate"] "concatenate" Its default definition is mconcat = foldr mappend mempty. Section 13.3: Numeric Monoids Numbers are monoidal in two ways: addition with 0 as the unit, and multiplication with 1 as the unit. Both are equally valid and useful in different circumstances. So rather than choose a preferred instance for numbers, there are two newtypes, Sum and Product to tag them for the different functionality. newtype Sum n = Sum { getSum :: n } instance Num n => Monoid (Sum n) where mempty = Sum 0 Sum x `mappend` Sum y = Sum (x + y) newtype Product n = Product { getProduct :: n } instance Num n => Monoid (Product n) where mempty = Product 1 Product x `mappend` Product y = Product (x * y) This effectively allows for the developer to choose which functionality to use by wrapping the value in the appropriate newtype. Sum 3 <> Sum 5 == Sum 8 Product 3 <> Product 5 == Product 15 GoalKicker.com – Haskell Notes for Professionals 65 Section 13.4: An instance of Monoid for () () is a Monoid. Since there is only one value of type (), there's only one thing mempty and mappend could do: instance Monoid () where mempty = () () `mappend` () = () GoalKicker.com – Haskell Notes for Professionals 66 Chapter 14: Category Theory Section 14.1: Category theory as a system for organizing abstraction Category theory is a modern mathematical theory and a branch of abstract algebra focused on the nature of connectedness and relation. It is useful for giving solid foundations and common language to many highly reusable programming abstractions. Haskell uses Category theory as inspiration for some of the core typeclasses available in both the standard library and several popular third-party libraries. An example The Functor typeclass says that if a type F instantiates Functor (for which we write Functor F) then we have a generic operation fmap :: (a -> b) -> (F a -> F b) which lets us "map" over F. The standard (but imperfect) intuition is that F a is a container full of values of type a and fmap lets us apply a transformation to each of these contained elements. An example is Maybe instance Functor Maybe where fmap f Nothing = Nothing -- if there are no values contained, do nothing fmap f (Just a) = Just (f a) -- else, apply our transformation Given this intuition, a common question is "why not call Functor something obvious like Mappable?". A hint of Category Theory The reason is that Functor fits into a set of common structures in Category theory and therefore by calling Functor "Functor" we can see how it connects to this deeper body of knowledge. In particular, Category Theory is highly concerned with the idea of arrows from one place to another. In Haskell, the most important set of arrows are the function arrows a -> b. A common thing to study in Category Theory is how one set of arrows relates to another set. In particular, for any type constructor F, the set of arrows of the shape F a -> F b are also interesting. So a Functor is any F such that there is a connection between normal Haskell arrows a -> b and the F-specific arrows F a -> F b. The connection is defined by fmap and we also recognize a few laws which must hold forall (x :: F a) . fmap id x == x forall (f :: a -> b) (g :: b -> c) . fmap g . fmap f = fmap (g . f) All of these laws arise naturally from the Category Theoretic interpretation of Functor and would not be as obviously necessary if we only thought of Functor as relating to "mapping over elements". Section 14.2: Haskell types as a category Definition of the category The Haskell types along with functions between types form (almost†) a category. We have an identity morphism (function) (id :: a -> a) for every object (type) a; and composition of morphisms ((.) :: (b -> c) -> (a -> b) -> a -> c), which obey category laws: GoalKicker.com – Haskell Notes for Professionals 67 f . id = f = id . f h . (g . f) = (h . g) . f We usually call this category Hask. Isomorphisms In category theory, we have an isomorphism when we have a morphism which has an inverse, in other words, there is a morphism which can be composed with it in order to create the identity. In Hask this amounts to have a pair of morphisms f,g such that: f . g == id == g . f If we find a pair of such morphisms between two types, we call them isomorphic to one another. An example of two isomorphic types would be ((),a) and a for some a. We can construct the two morphisms: f :: ((),a) -> a f ((),x) = x g :: a -> ((),a) g x = ((),x) And we can check that f . g == id == g . f. Functors A functor, in category theory, goes from a category to another, mapping objects and morphisms. We are working only on one category, the category Hask of Haskell types, so we are going to see only functors from Hask to Hask, those functors, whose origin and destination category are the same, are called endofunctors. Our endofunctors will be the polymorphic types taking a type and returning another: F :: * -> * To obey the categorical functor laws (preserve identities and composition) is equivalent to obey the Haskell functor laws: fmap (f . g) = (fmap f) . (fmap g) fmap id = id So, we have, for example, that [], Maybe or (-> r) are functors in Hask. Monads A monad in category theory is a monoid on the category of endofunctors. This category has endofunctors as objects F :: * -> * and natural transformations (transformations between them forall a . F a -> G a) as morphisms. A monoid object can be defined on a monoidal category, and is a type having two morphisms: zero :: () -> M mappend :: (M,M) -> M We can translate this roughly to the category of Hask endofunctors as: GoalKicker.com – Haskell Notes for Professionals 68 return :: a -> m a join :: m (m a) -> m a And, to obey the monad laws is equivalent to obey the categorical monoid object laws. †In fact, the class of all types along with the class of functions between types do not strictly form a category in Haskell, due to the existance of undefined. Typically this is remedied by simply defining the objects of the Hask category as types without bottom values, which excludes non-terminating functions and infinite values (codata). For a detailed discussion of this topic, see here. Section 14.3: Definition of a Category A category C consists of: A collection of objects called Obj(C) ; A collection (called Hom(C)) of morphisms between those objects. If a and b are in Obj(C), then a morphism f in Hom(C) is typically denoted f : a -> b, and the collection of all morphism between a and b is denoted hom(a,b) ; A special morphism called the identity morphism - for every a : Obj(C) there exists a morphism id : a -> a ; A composition operator (.), taking two morphisms f : a -> b, g : b -> c and producing a morphism a -> c which obey the following laws: For all f : a -> x, g : x -> b, then id . f = f and g . id = g For all f : a -> b, g : b -> c and h : c -> d, then h . (g . f) = (h . g) . f In other words, composition with the identity morphism (on either the left or right) does not change the other morphism, and composition is associative. In Haskell, the Category is defined as a typeclass in Control.Category: -- | A class for categories. -- id and (.) must form a monoid. class Category cat where -- | the identity morphism id :: cat a a -- | morphism composition (.) :: cat b c -> cat a b -> cat a c In this case, cat :: k -> k -> * objectifies the morphism relation - there exists a morphism cat a b if and only if cat a b is inhabited (i.e. has a value). a, b and c are all in Obj(C). Obj(C) itself is represented by the kind k - for example, when k ~ *, as is typically the case, objects are types. The canonical example of a Category in Haskell is the function category: instance Category (->) where id = Prelude.id (.) = Prelude.. GoalKicker.com – Haskell Notes for Professionals 69 Another common example is the Category of Kleisli arrows for a Monad: newtype Kleisli m a b = Kleisli (a -> m b) class Monad m => Category (Kleisli m) where id = Kleisli return Kleisli f . Kleisli g = Kleisli (f >=> g) Section 14.4: Coproduct of types in Hask Intuition The categorical product of two types A and B should contain the minimal information necessary to contain inside an instance of type A or type B. We can see now that the intuitive coproduct of two types should be Either a b. Other candidates, such as Either a (b,Bool), would contain a part of unnecessary information, and they wouldn't be minimal. The formal definition is derived from the categorical definition of coproduct. Categorical coproducts A categorical coproduct is the dual notion of a categorical product. It is obtained directly by reversing all the arrows in the definition of the product. The coproduct of two objects X,Y is another object Z with two inclusions: i_1: X → Z and i_2: Y → Z; such that any other two morphisms from X and Y to another object decompose uniquely through those inclusions. In other words, if there are two morphisms f₁ : X → W and f₂ : Y → W, exists a unique morphism g : Z → W such that g ○ i₁ = f₁ and g ○ i₂ = f₂ Coproducts in Hask The translation into the Hask category is similar to the translation of the product: -- if there are two functions f1 :: A -> W f2 :: B -> W -- and we have a coproduct with two inclusions i1 :: A -> Z i2 :: B -> Z -- we can construct a unique function g :: Z -> W -- such that the other two functions decompose using g g . i1 == f1 g . i2 == f2 The coproduct type of two types A and B in Hask is Either a b or any other type isomorphic to it: -- Coproduct -- The two inclusions are Left and Right data Either a b = Left a | Right b -- If we have those functions, we can decompose them through the coproduct decompose :: (A -> W) -> (B -> W) -> (Either A B -> W) decompose f1 f2 (Left x) = f1 x decompose f1 f2 (Right y) = f2 y GoalKicker.com – Haskell Notes for Professionals 70