hpfp

Notes on “Haskell Programming from First Principles” by Julie Moronuki and Chris Allen, revision RC2.

Contents

• Readme
• Chapter 1: All You Need is Lambda
  • 1.1 All you need is lambda
    • What is a calculus?
    • What is the lambda calculus?
    • How does this apply to Haskell?
  • 1.2 What is functional programming?
    • functional vs imperative
  • 1.3 What is a function?
  • 1.4 The structure of lambda terms
    • Abstractions
    • Alpha equivalence
  • 1.5 Beta reduction
    • Free variables
  • 1.6 Multiple arguments
    • 1.6.1 Intermission: Equivalence Exercises
  • 1.7 Evaluation is simplification
  • 1.8 Combinators
  • 1.9 Divergence
  • 1.11 Chapter Exercises
    • 1.11.1 Combinators
    • 1.11.2 Normal form or diverge?
    • 1.11.3 Beta reduce
• Chapter 1 Overkill
  • 1.1 All you need is lambda
    • Subjects
    • Claims
    • Remarks
  • 1.2 What is functional programming?
    • Subjects
    • Claims
    • Remarks
  • 1.3 What is a function?
    • Subjects
    • General questions and comments
  • 1.4 The structure of lambda expressions
    • Subjects
  • 1.5 Beta reduction
    • Subjects
  • 1.6 Multiple arguments
    • Subjects
  • 1.7 Evaluation is simplification
    • Subjects
    • Questions
  • 1.8 combinators
    • Subjects
    • Questions
  • 1.9 Divergence
    • Subjects
• Chapter 2 Outline
• Chapter 2: Hello, Haskell!
  • 2.1 Hello, Haskell
  • 2.2 Interacting with Haskell code
    • 2.2.2 What is Prelude?
  • 2.3 Understanding expressions
    • 2.3.1 Normal form
  • 2.4 Functions
    • 2.4.2 Capitalization matters!
  • 2.5 Evaluation
  • 2.6 Infix operators
    • 2.6.1 Associativity and precedence
    • 2.6.2 Exercises: Parentheses and Association
  • 2.7 Declaring values
    • 2.7.1 Troubleshooting
    • 2.7.2 Heal the sick
  • 2.8 Arithmetic functions in Haskell
    • 2.8.1 Laws for quotients and remainders
    • 2.8.2 Using mod
    • 2.8.3 Negative numbers
  • 2.9 Parenthesization
    • 2.9.1 Parenthesizing infix operators
  • 2.10 Let and where
    • 2.10.1 Exercises: A Head Code
  • 2.11 Chapter Exercises
    • 2.11.1 Parenthesization
    • 2.11.2 Equivalent expressions
    • 2.11.3 More fun with functions
• Chapter 3: Strings
  • 3.1 Printing strings
  • 3.2 A first look at types
    • Functions related to strings:
  • 3.4 Top-level versus local definitions
    • 3.4.1 Exercises: Scope
  • 3.5 Types of concatenation functions
  • 3.7 More list functions
  • 3.8 Chapter Exercises
    • 3.8.1 Reading syntax
  • 3.8.2 Building functions
• Chapter 3 Questions
• Chapter 4: Basic datatypes
  • 4.1 Basic datatype
  • 4.2 What are types?
  • 4.3 Anatomy of a data declaration
    • 4.3.1 Exercises: Mood Swing
  • 4.4 Numeric types
    • Integral numbers
    • Fractional
  • 4.5 Comparing values
  • 4.6 Go on and Bool me
    • 4.6.1 Exercises: Find the Mistakes
  • 4.7 Tuples
  • 4.8 Lists
  • 4.9 Chapter Exercises
    • 4.9.1 Untitled
    • 4.9.2 Correcting syntax
    • 4.9.3 Match the function names to their types
• Chapter 4 Questions
• Chapter 5: Types
  • 5.1 Types
  • 5.2 What are types for?
  • 5.3 How to read type signatures
    • 5.3.1 Understanding the function type
    • 5.3.2 Type class constrained type variables
    • 5.3.3 Exercises: Type Matching
  • 5.4 Currying
    • 5.4.1 Partial application
    • 5.4.2 Manual currying and uncurrying
    • 5.4.3 Sectioning
    • 5.4.5 Exercises: Type Arguments
  • 5.5 Polymorphism
    • 5.5.1 Exercises: Parametricity
    • 5.5.2 Polymorphic constants
    • 5.5.3 Working around constraints
  • 5.6 Type inference
    • 5.6.1 Exercises: Apply Yourself
  • 5.7 Asserting types for declarations
  • 5.8 Chapter Exercises
    • 5.8.1 Multiple choice
    • 5.8.2 Determine the type
    • 5.8.3 Does it compile?
    • 5.8.4 Type variable or specific type constructor?
    • 5.8.5 Write a type signature
    • 5.8.6 Given a type, write the function
    • 5.8.7 Fix it
    • 5.8.8 Type-Kwon-Do
  • 5.10 Follow-up resources
• Chapter 5 Questions
• Chapter 6: Typeclasses
  • 6.1 Typeclasses
  • 6.2 What are typeclasses?
    • Class declarations
    • Instance declarations
    • Type membership
    • Minimally required methods
    • Syntax for specifying minimally required class methods
    • Default class methods
    • Derivable type classes
    • Common type classes
  • 6.3 Back to Bool
  • 6.4 Eq
  • 6.5 Writing type class instances
    • 6.5.2 Partial functions
    • 6.5.3 Sometimes we need to ask for more
    • 6.5.4 Exercises: Eq Instances
  • 6.6 Num
    • 6.6.1 Integral
    • 6.6.2 Exercises: Tuple Experiment
    • 6.6.3 Fractional
  • 6.7 Type-defaulting type classes?
  • 6.8 Ord
    • 6.8.1 Ord instances
    • 6.8.3 Exercises: Will They Work?
  • 6.9 Enum
  • 6.10 Show
  • 6.14 Chapter Exercises
    • 6.14.1 Multiple choice
    • 6.14.2 Does it typecheck?
    • 6.14.3 Given a datatype declaration, what can we do?
    • 6.14.4 Match the types
    • 6.14.5 Type-Kwon-Do Two: Electric Typealoo
• Chapter 7: More Functional Patterns
  • 7.1 Make it func-y
  • 7.2 Arguments and parameters
    • 7.2.1 Setting parameters
    • 7.2.2 Binding variables to values
  • 7.3 Anonymous functions
    • 7.3.1 Grab Bag
    • 7.3.2 The utility of lambda syntax
  • 7.4 Patten matching
    • Value only patterns
      • Destructuring value only patterns
    • Patterns that introduce names
      • Name binding and destructuring
    • Mechanics of pattern matching
    • Lazy patterns, refutable vs irrefutable patterns
    • Where else can you use patterns?
    • 7.4.1 Handling all the cases
    • 7.4.4 Exercises: Variety Pack
  • 7.5 Case expressions
    • 7.5.1 Exercises: Case Practice
  • 7.6 Higher-order functions
    • 7.6.1 Exercises: Artful Dodgy
  • 7.7 Guards
    • 7.7.2 Writing guard blocks
    • 7.7.3 Guard Duty
  • 7.8 Function composition
  • 7.9 Pointfree style
  • 7.11 Chapter Exercises
    • 7.11.1 Multiple choice
    • 7.11.2 Let’s write code
• Chapter 8 Outline
• Chapter 8: Recursion
  • 8.1 Recursion
  • 8.2 Factorial!
    • 8.2.1 Another way to look at recursion
    • 8.2.2 Intermission: Exercise
  • 8.3 Bottom
    • Non-termination
    • Partial functions
    • Undefined values
    • Intentionally thrown errors
  • 8.4 Fibonacci numbers
    • 8.4.1 Consider the types
  • 8.5 Integral division from scratch
  • 8.6 Chapter Exercises
    • 8.6.1 Review of types
    • 8.6.2 Reviewing currying
    • 8.6.3 Recursion
    • 8.6.4 Fixing dividedBy
    • 8.6.5 McCarthy 91 function
• How to design recursive functions
• Chapter 8: Overkill
  • 8.1 Recursion
    • Questions
    • Thoughts about this section
  • 8.2 Factorial!
• Chapter 9 Outline
• Chapter 9 Summary
  • 9.2 The list datatype
  • 9.8 Spines and non-strict evaluation
    • 9.8.2 Spines are evaluated independently of values
• Chapter 9: Lists
  • 9.1 Lists
  • 9.2 The list datatype
  • 9.3 Pattern matching on lists
    • 9.3.1 Using Maybe
  • 9.4 List’s syntactic sugar
  • 9.5 Using ranges to construct lists
    • 9.5.1 Exercise: EnumFromTo
  • 9.6 Extracting portions of lists
    • 9.6.1 Exercises: Thy Fearful Symmetry
  • 9.7 List comprehensions
    • 9.7.1 Adding predicates
    • 9.7.2 Exercises: Comprehend thy lists
    • 9.7.3 List comprehensions with strings
    • 9.7.4 Exercises: Square Cube
  • 9.8 Spines and nonstrict evaluation
    • 9.8.1 Using GHCi’s :sprint command
    • 9.8.2 Spines are evaluated independently of values
    • 9.8.3 Exercise: Bottom Madness
      • 9.8.3.1 Will it blow up?
      • 9.8.3.2 Intermission: Is it in normal form?
  • 9.9 Transforming lists of values
    • Exercises: More Bottoms
  • 9.10 Filtering lists of values
    • 9.10.1 Exercises: Filtering
  • 9.11 Zipping lists
    • 9.11.1 Zipping exercises
  • 9.12 Chapter Exercises
    • 9.12.1 Data.Char
    • 9.12.2 Ciphers
    • 9.12.3 Writing your own standard functions
• Chapter 10 Contents
• Chapter 10: Folding Lists
  • 10.1 Folds
  • 10.2 Bringing you into the fold
  • 10.4 Fold right
    • 10.4.1 How foldr evaluates
  • 10.5 Fold left
    • 10.5.2 Exercises: Understanding folds
    • 10.6.1 Exercises: Database processing
  • 10.7 Folding and evaluation
  • 10.9 Scans
    • 10.9.2 Scans exercises
  • 10.10 Chapter exercises
    • 10.10.1 Warm-up and review
    • 10.10.2 Rewriting functions using folds
• Chapter 10 Questions
• Chapter 11: Algebraic Datatypes
  • 11.1 Algebraic datatypes
  • 11.2 Data declarations review
  • 11.3 Data and type constructors
  • 11.4 Type constructors and kinds
  • 11.5 Data constructors and values
  • 11.6 What’s a type and what’s data?
  • 11.7 Data constructor arities
  • 11.8 What makes these datatypes algebraic?
  • 11.9 newtype
  • 11.10 Sum types
  • 11.11 Product types
  • 11.12 Normal form
  • 11.3 Constructing and deconstructing values
  • 11.14 Function type is exponential
  • 11.15 Higher-kinded datatypes
  • 11.16 Lists are polymorphic
  • 11.17 Binary tree
  • 11.18 Chapter exercises
• Chapter 12: Signaling adversity
  • 12.1 Signaling adversity
  • 12.2 How I learned to stop worrying and love Nothing
    • 12.2.1 Smart constructors for datatypes
  • 12.3 Bleating Either
  • 12.4 Kinds, a thousand stars in your types
  • 12.5 Chapter Exercises
    • 12.5.1 Determine the kinds
    • 12.5.2 String processing
    • 12.5.3 Validate the word
    • 12.5.4 It’s only Natural
    • 12.5.5 Small library for Maybe
    • 12.5.6 Small library for Either
    • 12.5.7 Unfolds
    • 12.5.8 Why bother?
    • 12.5.9 Write your own iterate and unfoldr
    • 12.5.10 Finally something other than a list!
  • 12.6 Follow-up resources
• Chapter 13: Building Projects
  • 13.1 Modules
  • 13.2 Making packages with Stack
  • 13.3 to 13.8
  • 13.6 More on importing modules
  • 13.9 to 13.13
  • 13.14 Chapter exercises
    • 13.14.1 Hangman game logic
    • 13.14.2 Modifying code
  • 13.15 Follow-up resources
• Chapter 14: Testing
  • 14.1 Testing
  • 14.2 A quick tour of testing for the uninitiated
  • 14.3 Conventional testing
    • 14.3.1 Truth according to Hspec
    • 14.3.2 Our first Hspec test
    • 14.3.3 Intermission: Short Exercise
  • 14.4 Enter QuickCheck
    • 14.4.1 Arbitrary instances
  • 14.5 Morse code
  • 14.6 Arbitrary instances
    • 14.6.1 Babby’s First Arbitrary
    • 14.6.2 Identity Crisis
  • 14.7 Chapter Exercises
    • 14.7.2 Using QuickCheck
• Chapter 14 Questions
  • Hspec functions list
    • Basic functions
    • Hooks
    • Placeholders
  • QuickCheck Questions
    • How can I run a particular Hspec test with stack?
    • Is there some special reason that QuickCheck property tests begin with prop_, such as automated test discovery?
• Chapter 15: Monoid, Semigroup
  • 15.1 Monoids and semigroups
  • 15.2 What we talk about when we talk about algebras
  • 15.3 Monoid
  • 15.4 How Monoid is defined in Haskell
  • 15.6 What Integer doesn’t have a Monoid
  • 15.7 Why bother?
  • 15.8 Laws
  • 15.9 Different instances, same representation
  • 15.10 Reusing algebras by asking for algebras
    • 15.10.1 Exercise: Optional Monoid
    • 15.10.4 The problem of orphan instances
  • 15.11 Madness
  • 15.12 Better living through QuickCheck
  • 15.13 Semigroup
    • 15.13.2 NonEmpty, a useful datatype
  • 15.14 Strength can be weakness
  • 15.15 Chapter exercises
    • 15.15.1 Semigroup exercises
• Chapter 16 Outline
• Chapter 16: Functor
  • 16.1 Functor
  • 16.2 What’s a functor?
  • 16.4 Let’s talk about f baby
    • 16.4.1 Shining star come into view
    • 16.4.5 A shining star for you to see what your f can truly be
  • 16.17 Chapter Exercises
    • 16.17.1 Valid Functor
    • 16.17.2 Constructor shuffle
    • 16.17.3 Write the instance
• Chapter 17: Applicative
  • 17.1 Applicative
  • 17.2 Defining Applicative
  • 17.3 Functor vs. Applicative
  • 17.4 Applicative functors are monoidal functors
    • 17.4.1 Show me the monoids
    • 17.4.2 Tuple Monoid and Applicative side by side
    • 17.4.3 Maybe Monoid and Applicative
  • 17.5 Applicative in use
    • 17.5.1 List Applicative
    • 17.5.2 What’s the List applicative do?
    • 17.5.3 Exercises: Lookups
    • 17.5.4 Identity
      • Specializing the types
  • 17.6 Applicative laws
    • Identity
    • Composition
    • Homomorphism
    • Interchange
  • 17.7 You knew this was coming
  • 17.9 Chapter Exercises
    • 17.9.1 Specialize the types
    • 17.9.2 Write Applicative instances
    • 17.9.3 Combinations
• Chapter 18 Outline
• Chapter 18: Monad
  • 18.1 Monad
  • 18.2 Sorry – a monad is not a burrito
    • 18.2.1 Applicative m
    • 18.2.2 Core operations
    • 18.2.3 The novel part of Monad
    • 18.2.4 What Monad is not
    • 18.2.5 Monad also lifts!
  • 18.3 Do syntax and monads
    • 18.3.1 When fmap alone isn’t enough
  • 18.4 Examples of Monad use
    • 18.4.1 List
      • 18.4.1.1 Specializing the types
      • 18.4.1.2 Example of the List Monad in use
    • 18.4.2 Maybe Monad
      • 18.4.2.1 Specializing the types
      • 18.4.2.2 Using the Maybe Monad
    • 18.4.3 Either
      • 18.4.3.1 Specializing the types
      • 18.4.3.2 Using the Either Monad
      • 18.4.3.3 Short Exercises: Either Monad
  • 18.5 Monad laws
    • 18.5.1 Identity laws
    • 18.5.2 Associativity
• Chapter 20 Outline
• Chapter 20: Foldable
  • 20.1 Foldable
  • 20.2 The Foldable class
  • 20.3 Revenge of the monoids
    • 20.3.1 And now for something different
  • 20.4 Demonstrating Foldable instances
    • 20.4.1 Identity
    • 20.4.2 Maybe
  • 20.5 Some basic derived operations
    • toList
    • null
    • length
    • elem
    • maximum and minimum
    • sum and product
  • 20.5.7 Exercises: Library Functions
• Chapter 21 Outline
• Chapter 21 Questions
• Chapter 21: Traversable
  • 21.1 Traversable
  • 21.2 The Traversable type class definition
  • 21.3 sequenceA
  • 21.4 traverse
  • 21.5 So, what’s Traversable for?
  • 21.6 Morse code revisited
  • 21.7 Axing tedious code
  • 21.8 Do all the things
  • 21.10 Traversable Laws
    • 21.10.1 traverse
    • 21.10.2 sequenceA
  • 21.12 Chapter Exercises
    • 21.12.1 Traversable instances
      • Identity
      • Constant
      • Maybe
      • List
      • Three
      • Pair
      • Big
      • Bigger
      • S
    • 21.12.2 Instances for Tree
      • Hints
• Chapter 22 Outline
• Chapter 22: Reader
  • 22.1 Reader
  • 22.2 A new beginning
    • The Functor instance for functions
    • The Applicative instance for functions
    • The Monad instance for functions
    • 22.2.1 Short Exercise: Warming up
  • 22.3 This is Reader
  • 22.4 Breaking down the Functor of functions
  • 22.5 But uh, Reader?

Indices and tables

• Index

• Module Index

• Search Page