What I Wish I Knew When Learning Haskell

Version 2.3

% Stephen Diehl % March 2016

Stephen Diehl (@smdiehl )

This is the fourth draft of this document.

PDF Version

License

This code and text are dedicated to the public domain. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.

You may copy and paste any code here verbatim into your codebase, wiki, blog, book or Haskell musical production as you see fit. The Markdown and Haskell source is available on Github. Pull requests are always accepted for changes and additional content. This is a living document.

Changelog

2.4

2.3

• Stack
• Stackage
• ghcid
• Nix (Removed)
• Aeson (Updated)
• Language Extensions (Updated)
• Type Holes (Updated)
• Partial Type Signatures
• Pattern Synonyms (Updated)
• Unboxed Types ( Updated )
• Vim Integration ( Updated )
• Emacs Integration ( Updated )
• Strict Language Extension
• Injective Type Families
• Custom Type Errors
• Language Comparisons
• Recursive Do
• Applicative Do
• LiquidHaskell
• Cpp
• Minimal Pragma
• Typeclass Extensions
• ExtendedDefaultRules
• mmorph
• integer-gmp
• Static Pointers
• spoon
• monad-control
• monad-base
• postgresql-simple
• hedis
• happy/alex
• configurator
• string-conv
• resource-pool
• resourcet
• optparse-applicative
• hastache
• silently
• Mulitiline Strings
• git-embed
• Coercible
• -fdefer-type-errors

2.2

Sections that have had been added or seen large changes:

• Irrefutable Patterns
• Hackage
• Exhaustiveness
• Stacktraces
• Laziness
• Skolem Capture
• Foreign Function Pointers
• Attoparsec Parser
• Inline Cmm
• PrimMonad
• Specialization
• unbound-generics
• Editor Integration
• EKG
• Nix
• Haddock
• Corecursion
• Category
• Arrows
• Bifunctors
• ExceptT
• hint / mueval
• Roles
• Higher Kinds
• Kind Polymorphism
• Numeric Tower
• SAT Solvers
• Graph
• Sparks
• Threadscope
• Generic Parsers
• GHC Block Diagram
• GHC Debug Flags
• Core
• Inliner
• Unboxed Types
• Runtime Memory Representation
• ghc-heapview
• STG
• Worker/Wrapper
• Z-Encoding
• Cmm
• Runtime Optimizations
• RTS Profiling
• Algebraic Relations

Basics

Cabal

Cabal is the build system for Haskell.

For example, to install the parsec package to your system from Hackage, the upstream source of Haskell packages, invoke the install command:

$ cabal install parsec           # latest version
$ cabal install parsec==3.1.5    # exact version

The usual build invocation for Haskell packages is the following:

$ cabal get parsec    # fetch source
$ cd parsec-3.1.5

$ cabal configure
$ cabal build
$ cabal install

To update the package index from Hackage, run:

$ cabal update

To start a new Haskell project, run:

$ cabal init
$ cabal configure

A .cabal file will be created with the configuration options for our new project.

The latest feature of cabal is the addition of Sandboxes, ( in cabal > 1.18 ) which are self contained environments of Haskell packages separate from the global package index stored in the ./.cabal-sandbox of our project's root. To create a new sandbox for our cabal project, run:

$ cabal sandbox init

Additionally, the sandbox can be torn down:

$ cabal sandbox delete

When in the working directory of a project with a sandbox that has a configuration already set up, invoking cabal commands alters the behaviour of cabal itself. For instance, the cabal install command will alter only the install to the local package index, not the global configuration.

To install the dependencies from the .cabal file into the newly created sandbox, run:

$ cabal install --only-dependencies

Dependencies can also be built in parallel by passing -j<n> where n is the number of concurrent builds.

$ cabal install -j4 --only-dependencies

Let's look at an example .cabal file. There are two main entry points that any package may provide: a library and an executable. Multiple executables can be defined, but only one library. In addition, there is a special form of executable entry point Test-Suite, which defines an interface for invoking unit tests from cabal.

For a library, the exposed-modules field in the .cabal file indicates which modules within the package structure will be publicly visible when the package is installed. These modules are the user-facing APIs that we wish to expose to downstream consumers.

For an executable, the main-is field indicates the module that exports the main function running the executable logic of the application. Every module in the package must be listed in one of other-modules, exposed-modules or main-is fields.

name:               mylibrary
version:            0.1
cabal-version:      >= 1.10
author:             Paul Atreides
license:            MIT
license-file:       LICENSE
synopsis:           The code must flow.
category:           Math
tested-with:        GHC
build-type:         Simple

library
    exposed-modules:
      Library.ExampleModule1
      Library.ExampleModule2

    build-depends:
      base >= 4 && < 5

    default-language: Haskell2010

    ghc-options: -O2 -Wall -fwarn-tabs

executable "example"
    build-depends:
        base >= 4 && < 5,
        mylibrary == 0.1
    default-language: Haskell2010
    main-is: Main.hs

Test-Suite test
  type: exitcode-stdio-1.0
  main-is: Test.hs
  default-language: Haskell2010
  build-depends:
      base >= 4 && < 5,
      mylibrary == 0.1

To run an "executable" for a project under the cabal sandbox:

$ cabal run
$ cabal run <name> # when there are several executables in a project

To load the "library" into a GHCi shell under cabal sandbox:

$ cabal repl
$ cabal repl <name>

The <name> metavariable is either one of the executable or library declarations in the .cabal file and can optionally be disambiguated by the prefix exe:<name> or lib:<name> respectively.

To build the package locally into the ./dist/build folder, execute the build command:

$ cabal build

To run the tests, our package must itself be reconfigured with the --enable-tests and the build-depends options. The Test-Suite must be installed manually, if not already present.

$ cabal install --only-dependencies --enable-tests
$ cabal configure --enable-tests
$ cabal test
$ cabal test <name>

Moreover, arbitrary shell commands can be invoked with the GHC environmental variables set up for the sandbox. Quite common is to invoke a new shell with this command such that the ghc and ghci commands use the sandbox. ( They don't by default, which is a common source of frustration. ).

$ cabal exec
$ cabal exec sh # launch a shell with GHC sandbox path set.

The haddock documentation can be generated for the local project by executing the haddock command. The documentation will be built to the ./dist folder.

$ cabal haddock

When we're finally ready to upload to Hackage ( presuming we have a Hackage account set up ), then we can build the tarball and upload with the following commands:

$ cabal sdist
$ cabal upload dist/mylibrary-0.1.tar.gz

Sometimes you'd also like to add a library from a local project into a sandbox. In this case, run the add-source command to bring the library into the sandbox from a local directory:

$ cabal sandbox add-source /path/to/project

The current state of a sandbox can be frozen with all current package constraints enumerated:

$ cabal freeze

This will create a file cabal.config with the constraint set.

constraints: mtl ==2.2.1,
             text ==1.1.1.3,
             transformers ==0.4.1.0

Using the cabal repl and cabal run commands is preferable, but sometimes we'd like to manually perform their equivalents at the shell. Several useful aliases rely on shell directory expansion to find the package database in the current working directory and launch GHC with the appropriate flags:

alias ghc-sandbox="ghc -no-user-package-db -package-db .cabal-sandbox/*-packages.conf.d"
alias ghci-sandbox="ghci -no-user-package-db -package-db .cabal-sandbox/*-packages.conf.d"
alias runhaskell-sandbox="runhaskell -no-user-package-db -package-db .cabal-sandbox/*-packages.conf.d"

There is also a zsh script to show the sandbox status of the current working directory in our shell:

function cabal_sandbox_info() {
    cabal_files=(*.cabal(N))
    if [ $#cabal_files -gt 0 ]; then
        if [ -f cabal.sandbox.config ]; then
            echo "%{$fg[green]%}sandboxed%{$reset_color%}"
        else
            echo "%{$fg[red]%}not sandboxed%{$reset_color%}"
        fi
    fi
}

RPROMPT="\$(cabal_sandbox_info) $RPROMPT"

The cabal configuration is stored in $HOME/.cabal/config and contains various options including credential information for Hackage upload. One addition to configuration is to completely disallow the installation of packages outside of sandboxes to prevent accidental collisions.

-- Don't allow global install of packages.
require-sandbox: True

A library can also be compiled with runtime profiling information enabled. More on this is discussed in the section on Concurrency and Profiling.

library-profiling: True

Another common flag to enable is documentation which forces the local build of Haddock documentation, which can be useful for offline reference. On a Linux filesystem these are built to the /usr/share/doc/ghc-doc/html/libraries/ directory.

documentation: True

If GHC is currently installed, the documentation for the Prelude and Base libraries should be available at this local link:

/usr/share/doc/ghc-doc/html/libraries/index.html

See:

• An Introduction to Cabal Sandboxes
• Storage and Identification of Cabalized Packages

Stack

Stack is a new approach to Haskell package structure that emerged in 2015. Instead of using a rolling build like cabal-install, stack breaks up sets of packages into release blocks that guarantee internal compatibility between sets of packages. The package solver for stack uses a different, more robust strategy for resolving dependencies than cabal-install has historically used.

Install

To install stack on Ubuntu Linux, run:

sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 575159689BEFB442                             # get fp complete key
echo 'deb http://download.fpcomplete.com/ubuntu trusty main'|sudo tee /etc/apt/sources.list.d/fpco.list    # add appropriate source repo
sudo apt-get update && sudo apt-get install stack -y

For other operating systems, see the official install directions.

Usage

Once stack is installed, it is possible to setup a build environment on top of your existing project's cabal file by running:

stack init

An example stack.yaml file for GHC 7.10.3 would look like:

resolver: lts-6.4
flags: {}
extra-package-dbs: []
packages: []
extra-deps: []

Most of the common libraries used in everyday development are already in the Stackage repository. The extra-deps field can be used to add Hackage dependencies that are not in the Stackage repository. They are specified by the package and the version key. For instance, the zenc package could be added to the stack build:

extra-deps:
- zenc-0.1.1

The stack command can be used to install packages and executables into either the current build environment or the global environment. For example, the following command installs the executable for hlint, a popular linting tool for Haskell, and places it in the PATH:

$ stack install hlint

To check the set of dependencies, run:

$ stack list-dependencies

Just as with cabal, the build and debug process can be orchestrated using stack commands:

$ stack build                 # Build a cabal target
$ stack repl                  # Launch ghci
$ stack ghc                   # Invoke the standalone compiler in stack environment
$ stack exec bash             # Execute a shell command with the stack GHC environment variables
$ stack build --file-watch    # Build on every filesystem change

To visualize the dependency graph, use the dot command piped first into graphviz, then piped again into your favorite image viewer:

$ stack dot --external | dot -Tpng | feh -

Flags

Enabling GHC compiler flags grants the user more control in detecting common code errors. The most frequently used flags are:

Like most compilers, GHC takes the -Wall flag to enable all warnings. However, a few of the enabled warnings are highly verbose. For example, -fwarn-unused-do-bind and -fwarn-unused-matches typically would not correspond to errors or failures.

Any of these flags can be added to the ghc-options section of a project's .cabal file. For example:

library mylib

  ghc-options:
    -fwarn-tabs
    -fwarn-unused-imports
    -fwarn-missing-signatures
    -fwarn-name-shadowing
    -fwarn-incomplete-patterns

The flags described above are simply the most useful. See the official reference for the complete set of GHC's supported flags.

For information on debugging GHC internals, see the commentary on GHC internals.

Hackage

Hackage is the upstream source of Free and/or Open Source Haskell packages. With Haskell's continuing evolution, Hackage has become many things to developers, but there seem to be two dominant philosophies of uploaded libraries.

Reusable Code / Building Blocks

In the first philosophy, libraries exist as reliable, community-supported building blocks for constructing higher level functionality on top of a common, stable edifice. In development communities where this method is the dominant philosophy, the author(s) of libraries have written them as a means of packaging up their understanding of a problem domain so that others can build on their understanding and expertise.

A Staging Area / Request for Comments

In contrast to the previous method of packaging, a common philosophy in the Haskell community is that Hackage is a place to upload experimental libraries as a means of getting community feedback and making the code publicly available. Library author(s) often rationalize putting these kind of libraries up undocumented, often without indication of what the library actually does, by simply stating that they intend to tear the code down and rewrite it later. This approach unfortunately means a lot of Hackage namespace has become polluted with dead-end, bit-rotting code. Sometimes packages are also uploaded purely for internal use within an organisation, to accompany a paper, or just to integrate with the cabal build system. These packages are often left undocumented as well.

For developers coming to Haskell from other language ecosystems that favor the former philsophy (e.g., Python, Javascript, Ruby), seeing thousands of libraries without the slightest hint of documentation or description of purpose can be unnerving. It is an open question whether the current cultural state of Hackage is sustainable in light of these philsophical differences.

Needless to say, there is a lot of very low-quality Haskell code and documentation out there today, so being conservative in library assessment is a necessary skill. That said, there are also quite a few phenomenal libraries on Hackage that are highly curated by many people.

As a general rule, if the Haddock documentation for the library does not have a minimal worked example, it is usually safe to assume that it is an RFC-style library and probably should be avoided in production-grade code.

Similarly, if the library predates the text library (released circa 2007), it probably should be avoided in production code. The way we write Haskell has changed drastically since the early days.

GHCi

GHCi is the interactive shell for the GHC compiler. GHCi is where we will spend most of our time in every day development.

The introspection commands are an essential part of debugging and interacting with Haskell code:

λ: :type 3
3 :: Num a => a

λ: :kind Either
Either :: * -> * -> *

λ: :info Functor
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
        -- Defined in `GHC.Base'
  ...

λ: :i (:)
data [] a = ... | a : [a]       -- Defined in `GHC.Types'
infixr 5 :

Querying the current state of the global environment in the shell is also possible. For example, to view module-level bindings and types in GHCi, run:

λ: :browse
λ: :show bindings

Examining module-level imports, execute:

λ: :show imports
import Prelude -- implicit
import Data.Eq
import Control.Monad

To see compiler-level flags and pragmas, use:

λ: :set
options currently set: none.
base language is: Haskell2010
with the following modifiers:
  -XNoDatatypeContexts
  -XNondecreasingIndentation
GHCi-specific dynamic flag settings:
other dynamic, non-language, flag settings:
  -fimplicit-import-qualified
warning settings:

λ: :showi language
base language is: Haskell2010
with the following modifiers:
  -XNoDatatypeContexts
  -XNondecreasingIndentation
  -XExtendedDefaultRules

Language extensions and compiler pragmas can be set at the prompt. See the Flag Reference for the vast collection of compiler flag options.

Several commands for the interactive shell have shortcuts:

λ: :set +t
λ: []
[]
it :: [a]

λ: :set +s
λ: foldr (+) 0 [1..25]
325
it :: Prelude.Integer
(0.02 secs, 4900952 bytes)

λ: :{
λ:| let foo = do
λ:|           putStrLn "hello ghci"
λ:| :}
λ: foo
"hello ghci"

The configuration for the GHCi shell can be customized globally by defining a ghci.conf in $HOME/.ghc/ or in the current working directory as ./.ghci.conf.

For example, we can add a command to use the Hoogle type search from within GHCi. First, install hoogle:

cabal install hoogle

Then, we can enable the search functionality by adding a command to our ghci.conf:

:set prompt "λ: "

:def hlint const . return $ ":! hlint \"src\""
:def hoogle \s -> return $ ":! hoogle --count=15 \"" ++ s ++ "\""

λ: :hoogle (a -> b) -> f a -> f b
Data.Traversable fmapDefault :: Traversable t => (a -> b) -> t a -> t b
Prelude fmap :: Functor f => (a -> b) -> f a -> f b

For reasons of sexiness, it is desirable to set your GHC prompt to a λ or a λΠ. Only if you're into that lifestyle, though.

:set prompt "λ: "
:set prompt "ΠΣ: "

GHCi Performance

For large projects, GHCi with the default flags can use quite a bit of memory and take a long time to compile. To speed compilation by keeping artificats for compiled modules around, we can enable object code compilation instead of bytecode.

:set -fobject-code

Enabling object code compliation may complicate type inference, since type information provided to the shell can sometimes be less informative than source-loaded code. This under specificity can result in breakage with some langauge extensions. In that case, you can temporarily reenable bytecode compilation on a per module basis with the -fbyte-code flag.

:set -fbyte-code
:load MyModule.hs

If you all you need is to typecheck your code in the interactive shell, then disabling code generation entirely makes reloading code almost instantaneous:

:set -fno-code

Editor Integration

Haskell has a variety of editor tools that can be used to provide interactive development feedback and functionality such as querying types of subexpressions, linting, type checking, and code completion.

Several prepackaged setups exist to expedite the process of setting up many of the programmer editors for Haskell development. In particular, using ghc-mod can remarkably improve programmer efficiency and productivity because the project attempts to implement features common to modern IDEs.

Vim

• haskell-vim-now
• Vim and Haskell in 2016

Emacs

• Chris Done's Emacs Config
• Haskell Development From Emacs
• Structured Haskell Mode

Atom

• language-haskell plugin
• ide-haskell plugin

Bottoms

The bottom is a singular value that inhabits every type. When this value is evaluated, the semantics of Haskell no longer yield a meaningful value. In other words, further operations on the value cannot be defined in Haskell. A bottom value is usually written as the symbol ⊥, ( i.e. the compiler flipping you off ). Several ways exist to express bottoms in Haskell code.

For instance, undefined is an easily called example of a bottom value. This function has type a but lacks any type constraints in its type signature. Thus, undefined is able to stand in for any type in a function body, allowing type checking to succeed, even if the function is incomplete or lacking a definition entirely. The undefined function is extremely practical for debugging or to accommodate writing incomplete programs.

undefined :: a


mean :: Num a => Vector a -> a
mean nums = (total / count) where            -- Partially defined function
              total = undefined
              count = undefined

addThreeNums :: Num a => a -> a -> a -> a
addThreeNums n m j = undefined               -- No function body declared at all

f :: a -> Complicated Type
f = undefined                                -- Write tomorrow, typecheck today!
                                             -- Arbitrarily complicated types
                                             -- welcome!

Another example of a bottom value comes from the evaluation of the error function, which takes a String and returns something that can be of any type. This property is quite similar to undefined, which also can also stand in for any type.

Calling error in a function causes the compiler to throw an exception, halt the program, and print the specified error message. In the divByY function below, passing the function 0 as the divisor results in this function results in such an exception.

error :: String -> a                       -- Takes an error message of type
                                           -- String and returns whatever type
                                           -- is needed

-- Annotated code that features use of the error function.

divByY:: (Num a, Eq a, Fractional a) => a -> a -> a
divByY _ 0 = error "Divide by zero error"      -- Dividing by 0 causes an error
divByY dividend divisor = dividend / divisor   -- Handles defined division

A third type way to express a bottom is with an infinitely looping term:

f :: a
f = let x = x in x

Examples of actual Haskell code that use this looping syntax live in the source code of the GHC.Prim module. These bottoms exist because the operations cannot be defined in native Haskell. Such operations are baked into the compiler at a very low level. However, this module exists so that Haddock can generate documentation for these primitive operations, while the looping syntax serves as a placeholder for the actual implementation of the primops.

Perhaps the most common introduction to bottoms is writing a partial function that does not have exhaustive pattern matching defined. For example, the following code has non-exhaustive pattern matching because the case expression, lacks a definition of what to do with a B:

data F = A | B
case x of
  A -> ()

The code snippet above is translated into the following GHC Core output. The compiler inserts an exception to account for the non-exhaustive patterns:

case x of _ {
  A -> ();
  B -> patError "<interactive>:3:11-31|case"
}

GHC can be made more vocal about incomplete patterns using the -fwarn-incomplete-patterns and -fwarn-incomplete-uni-patterns flags.

A similar situation can arise with records. Although constructing a record with missing fields is rarely useful, it is still possible.

data Foo = Foo { example1 :: Int }
f = Foo {}     -- Record defined with a missing field

When the developer omits a field's definition, the compiler inserts an exception in the GHC Core representation:

Foo (recConError "<interactive>:4:9-12|a")

Fortunately, GHC will warn us by default about missing record fields.

Bottoms are used extensively throughout the Prelude, although this fact may not be immediately apparent. The reasons for including bottoms are either practical or historical.

The canonical example is the head function which has type [a] -> a. This function could not be well-typed without the bottom.

import GHC.Err
import Prelude hiding (head, (!!), undefined)

-- degenerate functions

undefined :: a
undefined =  error "Prelude.undefined"

head :: [a] -> a
head (x:_) =  x
head []    =  error "Prelude.head: empty list"

(!!) :: [a] -> Int -> a
xs     !! n | n < 0 =  error "Prelude.!!: negative index"
[]     !! _         =  error "Prelude.!!: index too large"
(x:_)  !! 0         =  x
(_:xs) !! n         =  xs !! (n-1)

It is rare to see these partial functions thrown around carelessly in production code because they cause the program to halt. The preferred method for handling exceptions is to combine the use of safe variants provided in Data.Maybe with the usual fold functions maybe and either.

Another method is to use pattern matching, as shown in listToMaybe, a safer version of head described below:

listToMaybe :: [a] -> Maybe a
listToMaybe []     =  Nothing    -- An empty list returns Nothing
listToMaybe (a:_)  =  Just a     -- A non-empty list returns the first element
                                 -- wrapped in the Just context.

Invoking a bottom defined in terms of error typically will not generate any position information. However, assert, which is used to provide assertions, can be short-circuited to generate position information in the place of either undefined or error calls.

import GHC.Base

foo :: a
foo = undefined
-- *** Exception: Prelude.undefined

bar :: a
bar = assert False undefined
-- *** Exception: src/fail.hs:8:7-12: Assertion failed

See: Avoiding Partial Functions

Exhaustiveness

Pattern matching in Haskell allows for the possibility of non-exhaustive patterns. For example, passing Nothing to unsafe will cause the program to crash at runtime. However, this function is an otherwise valid, type-checked program.

unsafe :: Num a => Maybe a -> Maybe a
unsafe (Just x) = Just $ x + 1

Since unsafe takes a Maybe a value as its argument, two possible values are valid input: Nothing and Just a. Since the case of a Nothing was not defined in unsafe, we say that the pattern matching within that function is non-exhaustive. In other words, the function does not implement appropriate handling of all valid inputs. Instead of yielding a value, such a function will halt from an incomplete match.

Partial functions from non-exhaustivity are a controversial subject, and frequent use of non-exhaustive patterns is considered a dangerous code smell. However, the complete removal of non-exhaustive patterns from the language would itself be too restrictive and forbid too many valid programs.

Several flags exist that we can pass to the compiler to warn us about such patterns or forbid them entirely either locally or globally.

$ ghc -c -Wall -Werror A.hs
A.hs:3:1:
    Warning: Pattern match(es) are non-exhaustive
             In an equation for `unsafe': Patterns not matched: Nothing

The -Wall or -fwarn-incomplete-patterns flag can also be added on a per-module basis by using the OPTIONS_GHC pragma.

{-# OPTIONS_GHC -Wall #-}
{-# OPTIONS_GHC -fwarn-incomplete-patterns #-}

A more subtle case of non-exhaustivity is the use of implicit pattern matching with a single uni-pattern in a lambda expression. In a manner similar to the unsafe function above, a uni-pattern cannot handle all types of valid input. For instance, the function boom will fail when given a Nothing, even though the type of the lambda expression's argument is a Maybe a.

boom = \(Just a) -> something

Non-exhaustivity arising from uni-patterns in lambda expressions occurs frequently in let or do-blocks after desugaring, because such code is translated into lambda expressions similar to boom.

boom2 = let
  Just a = something

boom3 = do
  Just a <- something

GHC can warn about these cases of non-exhaustivity with the -fwarn-incomplete-uni-patterns flag.

Grossly speaking, any non-trivial program will use some measure of partial functions. It is simply a fact. Thus, there exist obligations for the programmer than cannot be manifest in the Haskell type system.

Debugger

Since GHCi version 6.8.1, a built-in debugger has been available, although its use is somewhat rare. Debugging uncaught exceptions from bottoms or asynchronous exceptions is in similar style to debugging segfaults with gdb.

λ: :set -fbreak-on-exception       -- Sets option for evaluation to stop on exception
λ: :break 2 15                     -- Sets a break point at line 2, column 15
λ: :trace main                     -- Run a function to generate a sequence of evaluation steps
λ: :hist                           -- Step backwards from a breakpoint through previous steps of evaluation
λ: :back                           -- Step backwards a single step at a time through the history
λ: :forward                        -- Step forward a single step at a time through the history

Stack Traces

With runtime profiling enabled, GHC can also print a stack trace when a diverging bottom term (error, undefined) is hit. This action, though, requires a special flag and profiling to be enabled, both of which are disabled by default. So, for example:

import Control.Exception

f x = g x

g x = error (show x)

main = try (evaluate (f ())) :: IO (Either SomeException ())

$ ghc -O0 -rtsopts=all -prof -auto-all --make stacktrace.hs
./stacktrace +RTS -xc

And indeed, the runtime tells us that the exception occurred in the function g and enumerates the call stack.

*** Exception (reporting due to +RTS -xc): (THUNK_2_0), stack trace:
  Main.g,
  called from Main.f,
  called from Main.main,
  called from Main.CAF
  --> evaluated by: Main.main,
  called from Main.CAF

It is best to run this code without optimizations applied -O0 so as to preserve the original call stack as represented in the source. With optimizations applied, GHC will rearrange the program in rather drastic ways, resulting in what may be an entirely different call stack.

See:

• xc flag

Trace

Since Haskell is a pure language, it has the unique property that most code is introspectable on its own. As such, using printf to display the state of the program at critical times throughout execution is often unnecessary because we can simply open GHCi and test the function. Nevertheless, Haskell does come with an unsafe trace function which can be used to perform arbitrary print statements outside of the IO monad.

import Debug.Trace

example1 :: Int
example1 = trace "impure print" 1

example2 :: Int
example2 = traceShow "tracing" 2

example3 :: [Int]
example3 = [trace "will not be called" 3]

main :: IO ()
main = do
  print example1
  print example2
  print $ length example3
-- impure print
-- 1
-- "tracing"
-- 2
-- 1

In addition to the trace function, several monadic trace variants are quite common.

import Text.Printf
import Debug.Trace

traceM :: (Monad m) => String -> m ()
traceM string = trace string $ return ()

traceShowM :: (Show a, Monad m) => a -> m ()
traceShowM = traceM . show

tracePrintfM :: (Monad m, PrintfArg a) => String -> a -> m ()
tracePrintfM s = traceM . printf s

Type Holes

Since the release of GHC 7.8, typed holes allow for debugging incomplete programs. By placing an underscore on any value on the right hand-side of a declaration, GHC will throw an error during type-checking. Such an error reflects what type the value in the position of the type hole could be in order for the program to type-check successfully.

instance Functor [] where
  fmap f (x:xs) = f x : fmap f _

[1 of 1] Compiling Main             ( src/typedhole.hs, interpreted )

src/typedhole.hs:7:32:
    Found hole ‘_’ with type: [a]
    Where: ‘a’ is a rigid type variable bound by
               the type signature for fmap :: (a -> b) -> [a] -> [b]
               at src/typedhole.hs:7:3
    Relevant bindings include
      xs :: [a] (bound at src/typedhole.hs:7:13)
      x :: a (bound at src/typedhole.hs:7:11)
      f :: a -> b (bound at src/typedhole.hs:7:8)
      fmap :: (a -> b) -> [a] -> [b] (bound at src/typedhole.hs:7:3)
    In the second argument of ‘fmap’, namely ‘_’
    In the second argument of ‘(:)’, namely ‘fmap f _’
    In the expression: f x : fmap f _
Failed, modules loaded: none.

GHC has rightly suggested that the expression needed to finish the program is xs :: [a].

Deferred Type Errors

Since the release of version 7.8, GHC supports the option of treating type errors as runtime errors. With this option enabled, programs will run, but they will fail when a mistyped expression is evaluated. This feature is enabled with the -fdefer-type-errors flag in three ways: at the module level, when compiled from the command line, or inside of a GHCi interactive session.

For instance, the program below will compile:

{-# OPTIONS_GHC -fdefer-type-errors #-} -- Enable deferred type
                                        -- errors at module level

x :: ()
x = print 3

y :: Char
y = 0

z :: Int
z = 0 + "foo"

main :: IO ()
main = do
  print x

However, when a pathological term is evaluated at runtime, we'll see a message like:

defer: defer.hs:4:5:
    Couldn't match expected type ‘()’ with actual type ‘IO ()’
    In the expression: print 3
    In an equation for ‘x’: x = print 3
(deferred type error)

This error tells us that while x has a declared type of (), the body of the function print 3 has a type of IO (). However, if the term is never evaluated, GHC will not throw an exception.

ghcid

ghcid is a lightweight IDE hook that allows continuous feedback whenever code is updated. It can be run from the command line in the root of the cabal project directory by specifying a command to run (e.g. ghci, cabal repl, or stack repl).

ghcid --command="cabal repl"   # Run cabal repl under ghcid
ghcid --command="stack repl"   # Run stack repl under ghcid
ghcid --command="ghci baz.hs"  # Open baz.hs under ghcid

When a Haskell module is loaded into ghcid, the code is evaluated in order to provide the user with any errors or warnings that would happen at compile time. When the developer edits and saves code loaded into ghcid, the program automatically reloads and evaluates the code for errors and warnings.

Haddock

Haddock is the automatic documentation generation tool for Haskell source code. It integrates with the usual cabal toolchain. In this section, we will explore how to document code so that Haddock can generate documentation successfully.

Several frequent comment patterns are used to document code for Haddock. The first of these methods uses -- | to delineate the beginning of a comment:

-- | Documentation for f
f :: a -> a
f = ...

Multiline comments are also possible:

-- | Multiline documentation for the function
-- f with multiple arguments.
fmap :: Functor f =>
     => (a -> b)  -- ^ function
     -> f a       -- ^ input
     -> f b       -- ^ output

-- ^ is also used to comment Constructors or Record fields:

data T a b
  = A a -- ^ Documentation for A
  | B b -- ^ Documentation for B

data R a b = R
  { f1 :: a -- ^ Documentation for the field f1
  , f2 :: b -- ^ Documentation for the field f2
  }

Elements within a module (i.e. value, types, classes) can be hyperlinked by enclosing the identifier in single quotes:

data T a b
  = A a -- ^ Documentation for 'A'
  | B b -- ^ Documentation for 'B'

Modules themselves can be referenced by enclosing them in double quotes:

-- | Here we use the "Data.Text" library and import
-- the 'Data.Text.pack' function.

haddock also allows the user to include blocks of code within the generated documentation. Two methods of demarcating the code blocks exist in haddock. For example, enclosing a code snippet in @ symbols marks it as a code block:

-- | An example of a code block.
--
-- @
--    f x = f (f x)
-- @

Similarly, it's possible to use bird tracks (>) in a comment line to set off a code block. This usage is very similar to Bird style Literate Haskell.

-- | A similar code block example that uses bird tracks (i.e. '>')
-- > f x = f (f x)

Snippets of interactive shell sessions can also be included in haddock documentation. In order to denote the beginning of code intended to be run in a REPL, the >>> symbol is used:

-- | Example of an interactive shell session embedded within documentation
--
-- >>> factorial 5
-- 120

Headers for specific blocks can be added by prefacing the comment in the module block with a *:

module Foo (
  -- * My Header
  example1,
  example2
)

Sections can also be delineated by $ blocks that pertain to references in the body of the module:

module Foo (
  -- $section1
  example1,
  example2
)

-- $section1
-- Here is the documentation section that describes the symbols
-- 'example1' and 'example2'.

Links can be added with the following syntax:

<url text>

Images can also be included, so long as the path is either absolute or relative to the directory in which haddock is run.

<<diagram.png title>>

haddock options can also be specified with pragmas in the source, either at the module or project level.

{-# OPTIONS_HADDOCK show-extensions, ignore-exports #-}

Monads

Eightfold Path to Monad Satori

Much ink has been spilled waxing lyrical about the supposed mystique of monads. Instead, I suggest a path to enlightenment:

1. Don't read the monad tutorials.
2. No really, don't read the monad tutorials.
3. Learn about Haskell types.
4. Learn what a typeclass is.
5. Read the Typeclassopedia.
6. Read the monad definitions.
7. Use monads in real code.
8. Don't write monad-analogy tutorials.

In other words, the only path to understanding monads is to read the fine source, fire up GHC, and write some code. Analogies and metaphors will not lead to understanding.

Monadic Myths

The following are all false:

• Monads are impure.
• Monads are about effects.
• Monads are about state.
• Monads are about imperative sequencing.
• Monads are about IO.
• Monads are dependent on laziness.
• Monads are a "back-door" in the language to perform side-effects.
• Monads are an embedded imperative language inside Haskell.
• Monads require knowing abstract mathematics.
• Monads are unique to Haskell.

See: What a Monad Is Not

Monadic Methods

Monads are not complicated. They are implemented as a typeclass with two methods, return and (>>=) (pronounced "bind"). In order to implement a Monad instance, these two functions must be defined in accordance with the arity described in the typeclass definition:

class Monad m where
  return :: a -> m a                    -- N.B. 'm' refers to a type constructor
                                        -- (e.g., Maybe, Either, etc.) that
                                        -- implements the Monad typeclass

  (>>=)  :: m a -> (a -> m b) -> m b

The first type signature in the Monad class definition is for return. Any preconceptions one might have for the word "return" should be discarded: It has an entirely different meaning in the context of Haskell and acts very differently than in languages like C, Python, or Java. Instead of being the final arbiter of what value a function produces, return in Haskell injects a value of type a into a monadic context (e.g., Maybe, Either, etc.), which is denoted as m a.

The other function essential to implementing a Monad instance is (>>=). This infix takes two arguments. On its left side is a value with type m a, while on the right side is a function with type (a -> m b). The bind operation results in a final value of type m b.

A third, auxiliary function ((>>)) is defined in terms of the bind operation that discards its argument.

(>>) :: Monad m => m a -> m b -> m b
m >> k = m >>= \_ -> k

This definition says that (>>) has a left and right argument which are monadic with types m a and m b respectively, while the infix returns a value of type m b. The actual implementation of (>>) says that when m is passed to (>>) with k on the right, the value k will always be returned.

Laws

In addition to specific implementations of (>>=) and return, all monad instances must satisfy three laws.

Law 1

The first law says that when return a is passed through a (>>=) into a function f, this expression is exactly equivalent to f a.

return a >>= f ≡ f a    -- N.B. 'a' refers to a value, not a type

In discussing the next two laws, we'll refer to a value m. This notation is shorthand for value wrapped in a monadic context. Such a value has type m a, and could be represented more concretely by values like Nothing, Just x, or Right x. It is important to note that some of these concrete instantiations of the value m have multiple components. In discussing the second and third monad laws, we'll see some examples of how this plays out.

Law 2

The second law states that a monadic value m passed through (>>=) into return is exactly equivalent to itself. In other words, using bind to pass a monadic value to return does not change the initial value.

m >>= return ≡ m        -- 'm' here refers to a value that has type 'm a'

A more explicit way to write the second Monad law exists. In this following example code, the first expression shows how the second law applies to values represented by non-nullary type constructors. The second snippet shows how a value represented by a nullary type constructor works within the context of the second law.

(SomeMonad val) >>= return ≡ SomeMonad val  -- 'SomeMonad val' has type 'm a' just
                                            -- like 'm' from the first example of the
                                            -- second law

NullaryMonadType >>= return ≡ NullaryMonadType

Law 3

While the first two laws are relatively clear, the third law may be more difficult to understand. This law states that when a monadic value m is passed through (>>=) to the function f and then the result of that expression is passed to >>= g, the entire expression is exactly equivalent to passing m to a lambda expression that takes one parameter x and outputs the function f applied to x. By the definition of bind, f x must return a value wrapped in the same Monad. Because of this property, the resultant value of that expression can be passed through (>>=) to the function g, which also returns a monadic value.

(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)  -- Like in the last law, 'm' has
                                           -- has type 'm a'. The functions 'f'
                                           -- and 'g' have types '(a -> m b)'
                                           -- and '(b -> m c)' respectively

Again, it is possible to write this law with more explicit code. Like in the explicit examples for law 2, m has been replaced by SomeMonad val in order to be very clear that there can be multiple components to a monadic value. Although little has changed in the code, it is easier to see what value--namely, val--corresponds to the x in the lambda expression. After SomeMonad val is passed through (>>=) to f, the function f operates on val and returns a result still wrapped in the SomeMonad type constructor. We can call this new value SomeMonad newVal. Since it is still wrapped in the monadic context, SomeMonad newVal can thus be passed through the bind operation into the function g.

((SomeMonad val) >>= f) >>= g ≡ (SomeMonad val) >>= (\x -> f x >>= g)

See: Monad Laws

Do Notation

Monadic syntax in Haskell is written in a sugared form, known as do notation. The advantages of this special syntax are that it is easier to write and is entirely equivalent to just applications of the monad operations. The desugaring is defined recursively by the rules:

do { a <- f ; m } ≡ f >>= \a -> do { m }  -- bind 'f' to a, proceed to desugar
                                          -- 'm'

do { f ; m } ≡ f >> do { m }              -- evaluate 'f', then proceed to
                                          -- desugar  m

do { m } ≡ m

Thus, through the application of the desugaring rules, the following expressions are equivalent:

do
  a <- f                               -- f, g, and h are bound to the names a,
  b <- g                               -- b, and c. These names are then passed
  c <- h                               -- to 'return' to ensure that all values
  return (a, b, c)                     -- are wrapped in the appropriate monadic
                                       -- context

do {                                   -- N.B. '{}'  and ';' characters are
  a <- f;                              --  rarely used in do-notation
  b <- g;
  c <- h;
  return (a, b, c)
  }

f >>= \a ->
  g >>= \b ->
    h >>= \c ->
      return (a, b, c)

If one were to write the bind operator as an uncurried function ( this is not how Haskell uses it ) the same desugaring might look something like the following chain of nested binds with lambdas.

bindMonad(f, lambda a:
  bindMonad(g, lambda b:
    bindMonad(h, lambda c:
      returnMonad (a,b,c))))

In the do-notation, the monad laws from above are equivalently written:

Law 1

  do y <- return x
     f y

= do f x

Law 2

  do x <- m
     return x

= do m

Law 3

  do b <- do a <- m
             f a
     g b

= do a <- m
     b <- f a
     g b

= do a <- m
     do b <- f a
        g b

See: Haskell 2010: Do Expressions

Maybe

The Maybe monad is the simplest first example of a monad instance. The Maybe monad models computations which fail to yield a value at any point during computation.

The Maybe type has two value constructors. The first, Just, is a unary constructor representing a successful computation, while the second, Nothing, is a nullary constructor that represents failure.

data Maybe a = Just a | Nothing

The monad instance describes the implementation of (>>=) for Maybe by pattern matching on the possible inputs that could be passed to the bind operation (i.e., Nothing or Just x). The instance declaration also provides an implementation of return, which in this case is simply Just.

instance Monad Maybe where
  (Just x) >>= k = k x            -- 'k' is a function with type  (a -> Maybe a)
  Nothing  >>= k = Nothing

  return = Just                   -- Just's type signature is (a -> Maybe a), in
                                  -- other words, extremely similar to the
                                  -- type of 'return' in the typeclass
                                  -- declaration above.

The following code shows some simple operations to do within the Maybe monad.

In the first example, The value Just 3 is passed via (>>=) to the lambda function \x -> return (x + 1). x refers to the Int portion of Just 3, and we can use x in the second half of the lambda expression, where return (x + 1) evaluates to Just 4, indicating a successful computation.

(Just 3) >>= (\x -> return (x + 1))
-- Just 4

In the second example, the value Nothing is passed via (>>=) to the same lambda function as in the previous example. However, according to the Maybe Monad instance, whenever Nothing is bound to a function, the expression's result will be Nothing.

Nothing >>= (\x -> return (x + 1))
-- Nothing

In the next example, return is applied to 4 and returns Just 4.

return 4 :: Maybe Int
-- Just 4

The next code examples show the use of do notation within the Maybe monad to do addition that might fail. Desugared examples are provided as well.

example1 :: Maybe Int
example1 = do
  a <- Just 3                -- Bind 3 to name a
  b <- Just 4                -- Bind 4 to name b
  return $ a + b             -- Evaluate (a + b), then use 'return' to ensure
                             -- the result is in the Maybe monad in order to
                             -- satisfy the type signature
-- Just 7

desugared1 :: Maybe Int
desugared1 = Just 3 >>= \a ->    -- This example is the desugared
               Just 4 >>= \b ->  -- equivalent to example1
                 return $ a + b
-- Just 7

example2 :: Maybe Int
example2 = do
  a <- Just 3                -- Bind 3 to name a
  b <- Nothing               -- Bind Nothing to name b
  return $ a + b
-- Nothing                   -- This result might be somewhat surprising, since
                             -- addition within the Maybe monad can actually
                             -- return 'Nothing'. This result occurs because one
                             -- of the values, Nothing, indicates computational
                             -- failure. Since the computation failed at one
                             -- step within the process, the whole computation
                             -- fails, leaving us with 'Nothing' as the final
                             -- result.

desugared2 :: Maybe Int
desugared2 = Just 3 >>= \a ->     -- This example is the desugared
               Nothing >>= \b ->  -- equivalent to example2
                 return $ a + b
-- Nothing

List

The List monad is the second simplest example of a monad instance. As always, this monad implements both (>>=) and return. The definition of bind says that when the list m is bound to a function f, the result is a concatenation of map f over the list m. The return method simply takes a single value x and injects into a singleton list [x].

instance Monad [] where
  m >>= f   =  concat (map f m)          -- 'm' is a list
  return x  =  [x]

In order to demonstrate the List monad's methods, we will define two functions: m and f. m is a simple list, while f is a function that takes a single Int and returns a two element list [1, 0].

m :: [Int]
m = [1,2,3,4]

f :: Int -> [Int]
f = \x -> [1,0]               -- 'f' always returns [1, 0]

The evaluation proceeds as follows:

m >>= f
==> [1,2,3,4] >>= \x -> [1,0]
==> concat (map (\x -> [1,0]) [1,2,3,4])
==> concat ([[1,0],[1,0],[1,0],[1,0]])
==> [1,0,1,0,1,0,1,0]

The list comprehension syntax in Haskell can be implemented in terms of the list monad. List comprehensions can be considered syntactic sugar for more obviously monadic implementations. Examples a and b illustrate these use cases.

The first example (a) illustrates how to write a list comprehension. Although the syntax looks strange at first, there are elements of it that may look familiar. For instance, the use of <- is just like bind in a do notation: It binds an element of a list to a name. However, one major difference is apparent: a seems to lack a call to return. Not to worry, though, the [] fills this role. This syntax can be easily desugared by the compiler to an explicit invocation of return. Furthermore, it serves to remind the user that the computation takes place in the List monad.

a = [
      f x y |        -- Corresponds to 'f x y' in example b
      x <- xs,
      y <- ys,
      x == y         -- Corresponds to 'guard $ x == y' in example b
    ]

The second example (b) shows the list comprehension above rewritten with do notation:

-- Identical to `a`
b = do
  x <- xs
  y <- ys
  guard $ x == y     -- Corresponds to 'x == y' in example a
  return $ f x y     -- Corresponds to the '[]' and 'f x y' in example a

The final examples are further illustrations of the List monad. The functions below each return a list of 3-tuples which contain the possible combinations of the three lists that get bound the names a, b, and c. N.B.: Only values in the list bound to a can be used in a position of the tuple; the same fact holds true for the lists bound to b and c.

example :: [(Int, Int, Int)]
example = do
  a <- [1,2]
  b <- [10,20]
  c <- [100,200]
  return (a,b,c)
-- [(1,10,100),(1,10,200),(1,20,100),(1,20,200),(2,10,100),(2,10,200),(2,20,100),(2,20,200)]

desugared :: [(Int, Int, Int)]
desugared = [1, 2] >>= \a ->
              [10, 20] >>= \b ->
                [100, 200] >>= \c ->
                  return (a, b, c)
-- [(1,10,100),(1,10,200),(1,20,100),(1,20,200),(2,10,100),(2,10,200),(2,20,100),(2,20,200)]

IO

Perhaps the most (in)famous example in Haskell of a type that forms a monad is IO. A value of type IO a is a computation which, when performed, does some I/O before returning a value of type a. These computations are called actions. IO actions executed in main are the means by which a program can operate on or access information in the external world. IO actions allow the program to do many things, including, but not limited to:

• Print a String to the terminal
• Read and parse input from the terminal
• Read from or write to a file on the system
• Establish an ssh connection to a remote computer
• Take input from a radio antenna for singal processing

Conceptualizing I/O as a monad enables the developer to access information outside the program, but operate on the data with pure functions. The following examples will show how we can use IO actions and IO values to receive input from stdin and print to stdout.

Perhaps the most immediately useful function for doing I/O in Haskell is putStrLn. This function takes a String and returns an IO (). Calling it from main will result in the String being printed to stdout followed by a newline character.

putStrLn :: String -> IO ()

Here is some code that prints a couple of lines to the terminal. The first invocation of putStrLn is executed, causing the String to be printed to stdout. The result is bound to a lambda expression that discards its argument, and then the next putStrLn is executed.

main :: IO ()
main = putStrLn "Vesihiisi sihisi hississäään." >>=
         \_ -> putStrLn "Or in English: 'The water devil was hissing
                         in her elevator'."

-- Sugared code, written with do notation
main :: IO ()
main = do putStrLn "Vesihiisi sihisi hississäään."
          putStrLn "Or in English: 'The water devil was hissing in her
                    elevator'."

Another useful function is getLine which has type IO String. This function gets a line of input from stdin. The developer can then bind this line to a name in order to operate on the value within the program.

getLine :: IO String

The code below demonstrates a simple combination of these two functions as well as desugaring IO code. First, putStrLn prints a String to stdout to ask the user to supply their name, with the result being bound to a lambda that discards it argument. Then, getLine is executed, supplying a prompt to the user for entering their name. Next, the resultant IO String is bound to name and passed to putStrLn. Finally, the program prints the name to the terminal.

main :: IO ()
main = do putStrLn "What is your name: "
          name <- getLine
          putStrLn name

The next code block is the desugared equivalent of the previous example; however, the uses of (>>=) are made explict.

main :: IO ()
main = putStrLn "What is your name:" >>=
       \_    -> getLine >>=
       \name -> putStrLn name

Our final example executes in the same way as the previous two examples. This example, though, uses the special (>>) operator to take the place of binding a result to the lamda that discards its argument.

main :: IO ()
main = putStrLn "What is your name: " >> (getLine >>= (\name -> putStrLn name))

See: Haskell 2010: Basic/Input Output

What's the point?

Although it is difficult, if not impossible, to touch, see, or otherwise physically interact with a monad, this construct has some very interesting implications for programmers. For instance, consider the non-intuitive fact that we now have a uniform interface for talking about three very different, but foundational ideas for programming: Failure, Collections and Effects.

Let's write down a new function called sequence which folds a function mcons over a list of monadic computations. We can think of mcons as analogous to the list constructor (i.e. (a : b : [])) except it pulls the two list elements out of two monadic values (p,q) by means of bind. The bound values are then joined with the list constructor :, before finally being rewrapped in the appropriate monadic context with return.

sequence :: Monad m => [m a] -> m [a]
sequence = foldr mcons (return [])

mcons :: Monad m => m t -> m [t] -> m [t]
mcons p q = do
  x <- p          -- 'x' refers to a singleton value
  y <- q          -- 'y' refers to a list. Because of this fact, 'x' can be
  return (x:y)    --  prepended to it

What does this function mean in terms of each of the monads discussed above?

Maybe

Sequencing a list of values within the Maybe context allows us to collect the results of a series of computations which can possibly fail. However, sequence yields the aggregated values only if each computation succeeds. In other words, if even one of the Maybe values in the initial list passed to sequenceis a Nothing, the result of sequence will also be Nothing.

sequence :: [Maybe a] -> Maybe [a]

sequence [Just 3, Just 4]
-- Just [3,4]

sequence [Just 3, Just 4, Nothing]     -- Since one of the results is Nothing,
-- Nothing                             -- the whole computation fails

List

The bind operation for the list monad forms the pairwise list of elements from the two operands. Thus, folding the binds contained in mcons over a list of lists with sequence implements the general Cartesian product for an arbitrary number of lists.

sequence :: [[a]] -> [[a]]

sequence [[1,2,3],[10,20,30]]
-- [[1,10],[1,20],[1,30],[2,10],[2,20],[2,30],[3,10],[3,20],[3,30]]

IO

Applying sequence within the IO context results in still a different result. The function takes a list of IO actions, performs them sequentially, and then returns the list of resulting values in the order sequenced.

sequence :: [IO a] -> IO [a]

sequence [getLine, getLine, getLine]
-- a                                  -- a, b, and 9 are the inputs given by the
-- b                                  -- user at the prompt
-- 9
-- ["a", "b", "9"]                    -- All inputs are returned in a list as
                                      -- an IO [String].

So there we have it, three fundamental concepts of computation that are normally defined independently of each other actually all share this similar structure. This unifying pattern can be abstracted out and reused to build higher abstractions that work for all current and future implementations. If you want a motivating reason for understanding monads, this is it! These insights are the essence of what I wish I knew about monads looking back.

See: Control.Monad

Reader Monad

The reader monad lets us access shared immutable state within a monadic context.

ask :: Reader r r
asks :: (r -> a) -> Reader r a
local :: (r -> r) -> Reader r a -> Reader r a
runReader :: Reader r a -> r -> a

import Control.Monad.Reader

data MyContext = MyContext
  { foo :: String
  , bar :: Int
  } deriving (Show)

computation :: Reader MyContext (Maybe String)
computation = do
  n <- asks bar
  x <- asks foo
  if n > 0
    then return (Just x)
    else return Nothing

ex1 :: Maybe String
ex1 = runReader computation $ MyContext "hello" 1

ex2 :: Maybe String
ex2 = runReader computation $ MyContext "haskell" 0

A simple implementation of the Reader monad:

newtype Reader r a = Reader { runReader :: r -> a }

instance Monad (Reader r) where
  return a = Reader $ \_ -> a
  m >>= k  = Reader $ \r -> runReader (k (runReader m r)) r

ask :: Reader a a
ask = Reader id

asks :: (r -> a) -> Reader r a
asks f = Reader f

local :: (r -> r) -> Reader r a -> Reader r a
local f m = Reader $ runReader m . f

Writer Monad

The writer monad lets us emit a lazy stream of values from within a monadic context.

tell :: w -> Writer w ()
execWriter :: Writer w a -> w
runWriter :: Writer w a -> (a, w)

import Control.Monad.Writer

type MyWriter = Writer [Int] String

example :: MyWriter
example  = do
  tell [1..3]
  tell [3..5]
  return "foo"

output :: (String, [Int])
output = runWriter example
-- ("foo", [1, 2, 3, 3, 4, 5])

A simple implementation of the Writer monad:

import Data.Monoid

newtype Writer w a = Writer { runWriter :: (a, w) }

instance Monoid w => Monad (Writer w) where
  return a = Writer (a, mempty)
  m >>= k  = Writer $ let
      (a, w)  = runWriter m
      (b, w') = runWriter (k a)
      in (b, w `mappend` w')

execWriter :: Writer w a -> w
execWriter m = snd (runWriter m)

tell :: w -> Writer w ()
tell w = Writer ((), w)

This implementation is lazy, so some care must be taken that one actually wants to only generate a stream of thunks. Most often the lazy writer is not suitable for use, instead implement the equivalent structure by embedding some monomial object inside a StateT monad, or using the strict version.

import Control.Monad.Writer.Strict

State Monad

The state monad allows functions within a stateful monadic context to access and modify shared state.

runState  :: State s a -> s -> (a, s)
evalState :: State s a -> s -> a
execState :: State s a -> s -> s

import Control.Monad.State

test :: State Int Int
test = do
  put 3
  modify (+1)
  get

main :: IO ()
main = print $ execState test 0

The state monad is often mistakenly described as being impure, but it is in fact entirely pure and the same effect could be achieved by explicitly passing state. A simple implementation of the State monad takes only a few lines:

newtype State s a = State { runState :: s -> (a,s) }

instance Monad (State s) where
  return a = State $ \s -> (a, s)

  State act >>= k = State $ \s ->
    let (a, s') = act s
    in runState (k a) s'

get :: State s s
get = State $ \s -> (s, s)

put :: s -> State s ()
put s = State $ \_ -> ((), s)

modify :: (s -> s) -> State s ()
modify f = get >>= \x -> put (f x)

evalState :: State s a -> s -> a
evalState act = fst . runState act

execState :: State s a -> s -> s
execState act = snd . runState act

Monad Tutorials

So many monad tutorials have been written that it begs the question: what makes monads so difficult when first learning Haskell? I hypothesize there are three aspects to why this is so:

1. There are several levels on indirection with desugaring.

A lot of the Haskell we write is radically rearranged and transformed into an entirely new form under the hood.

Most monad tutorials will not manually expand out the do-sugar. This leaves the beginner thinking that monads are a way of dropping into a pseudo-imperative language inside of code and further fuels that misconception that specific instances like IO are monads in their full generality.

main = do
  x <- getLine
  putStrLn x
  return ()

Being able to manually desugar is crucial to understanding.

main =
  getLine >>= \x ->
    putStrLn x >>= \_ ->
      return ()

2. Asymmetric binary infix operators for higher order functions are not common in other languages.

(>>=) :: Monad m => m a -> (a -> m b) -> m b

On the left hand side of the operator we have an m a and on the right we have a -> m b. Although some languages do have infix operators that are themselves higher order functions, it is still a rather rare occurrence.

So with a function desugared, it can be confusing that (>>=) operator is in fact building up a much larger function by composing functions together.

main =
  getLine >>= \x ->
    putStrLn >>= \_ ->
      return ()

Written in prefix form, it becomes a little bit more digestible.

main =
  (>>=) getLine (\x ->
    (>>=) putStrLn (\_ ->
          return ()
    )
  )

Perhaps even removing the operator entirely might be more intuitive coming from other languages.

main = bind getLine (\x -> bind putStrLn (\_ -> return ()))
  where
    bind x y = x >>= y

3. Ad-hoc polymorphism is not commonplace in other languages.

Haskell's implementation of overloading can be unintuitive if one is not familiar with type inference. It is abstracted away from the user, but the (>>=) or bind function is really a function of 3 arguments with the extra typeclass dictionary argument ($dMonad) implicitly threaded around.

main $dMonad = bind $dMonad getLine (\x -> bind $dMonad putStrLn (\_ -> return $dMonad ()))

Except in the case where the parameter of the monad class is unified ( through inference ) with a concrete class instance, in which case the instance dictionary ($dMonadIO) is instead spliced throughout.

main :: IO ()
main = bind $dMonadIO getLine (\x -> bind $dMonadIO putStrLn (\_ -> return $dMonadIO ()))

Now, all of these transformations are trivial once we understand them, they're just typically not discussed. In my opinion the fundamental fallacy of monad tutorials is not that intuition for monads is hard to convey ( nor are metaphors required! ), but that novices often come to monads with an incomplete understanding of points (1), (2), and (3) and then trip on the simple fact that monads are the first example of a Haskell construct that is the confluence of all three.

See: Monad Tutorial Fallacy

Monad Transformers

mtl / transformers

So, the descriptions of Monads in the previous chapter are a bit of a white lie. Modern Haskell monad libraries typically use a more general form of these, written in terms of monad transformers which allow us to compose monads together to form composite monads. The monads mentioned previously are subsumed by the special case of the transformer form composed with the Identity monad.

type State  s = StateT  s Identity
type Writer w = WriterT w Identity
type Reader r = ReaderT r Identity

instance Monad m => MonadState s (StateT s m)
instance Monad m => MonadReader r (ReaderT r m)
instance (Monoid w, Monad m) => MonadWriter w (WriterT w m)

In terms of generality the mtl library is the most common general interface for these monads, which itself depends on the transformers library which generalizes the "basic" monads described above into transformers.

Transformers

At their core monad transformers allow us to nest monadic computations in a stack with an interface to exchange values between the levels, called lift.

lift :: (Monad m, MonadTrans t) => m a -> t m a
liftIO :: MonadIO m => IO a -> m a

class MonadTrans t where
    lift :: Monad m => m a -> t m a

class (Monad m) => MonadIO m where
    liftIO :: IO a -> m a

instance MonadIO IO where
    liftIO = id

Just as the base monad class has laws, monad transformers also have several laws:

Law #1

lift . return = return

Law #2

lift (m >>= f) = lift m >>= (lift . f)

Or equivalently:

Law #1

  lift (return x)

= return x

Law #2

  do x <- lift m
     lift (f x)

= lift $ do x <- m
            f x

It's useful to remember that transformers compose outside-in but are unrolled inside out.

See: Monad Transformers: Step-By-Step

Basics

The most basic use requires us to use the T-variants for each of the monad transformers in the outer layers and to explicitly lift and return values between the layers. Monads have kind (* -> *), so monad transformers which take monads to monads have ((* -> *) -> * -> *):

Monad (m :: * -> *)
MonadTrans (t :: (* -> *) -> * -> *)

So, for example, if we wanted to form a composite computation using both the Reader and Maybe monads we can now put the Maybe inside of a ReaderT to form ReaderT t Maybe a.

import Control.Monad.Reader

type Env = [(String, Int)]
type Eval a = ReaderT Env Maybe a

data Expr
  = Val Int
  | Add Expr Expr
  | Var String
  deriving (Show)

eval :: Expr -> Eval Int
eval ex = case ex of

  Val n -> return n

  Add x y -> do
    a <- eval x
    b <- eval y
    return (a+b)

  Var x -> do
    env <- ask
    val <- lift (lookup x env)
    return val

env :: Env
env = [("x", 2), ("y", 5)]

ex1 :: Eval Int
ex1 = eval (Add (Val 2) (Add (Val 1) (Var "x")))

example1, example2 :: Maybe Int
example1 = runReaderT ex1 env
example2 = runReaderT ex1 []

The fundamental limitation of this approach is that we find ourselves lift.lift.lifting and return.return.returning a lot.

ReaderT

For example, there exist three possible forms of the Reader monad. The first is the Haskell 98 version that no longer exists, but is useful for understanding the underlying ideas. The other two are the transformers and mtl variants.

Reader

newtype Reader r a = Reader { runReader :: r -> a }

instance MonadReader r (Reader r) where
  ask       = Reader id
  local f m = Reader (runReader m . f)

ReaderT

newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }

instance (Monad m) => Monad (ReaderT r m) where
  return a = ReaderT $ \_ -> return a
  m >>= k  = ReaderT $ \r -> do
      a <- runReaderT m r
      runReaderT (k a) r

instance MonadTrans (ReaderT r) where
    lift m = ReaderT $ \_ -> m

MonadReader

class (Monad m) => MonadReader r m | m -> r where
  ask   :: m r
  local :: (r -> r) -> m a -> m a

instance (Monad m) => MonadReader r (ReaderT r m) where
  ask       = ReaderT return
  local f m = ReaderT $ \r -> runReaderT m (f r)

So, hypothetically the three variants of ask would be:

ask :: Reader r r
ask :: Monad m => ReaderT r m r
ask :: MonadReader r m => m r

In practice only the last one is used in modern Haskell.

Newtype Deriving

Newtypes let us reference a data type with a single constructor as a new distinct type, with no runtime overhead from boxing, unlike an algebraic datatype with a single constructor. Newtype wrappers around strings and numeric types can often drastically reduce accidental errors.

Consider the case of using a newtype to distinguish between two different text blobs with different semantics. Both have the same runtime representation as a text object, but are distinguished statically, so that plaintext can not be accidentally interchanged with encrypted text.

newtype Plaintext = Plaintext Text
newtype Crytpotext = Cryptotext Text

encrypt :: Key -> Plaintext -> Cryptotext
decrypt :: Key -> Cryptotext -> Plaintext

The other common use case is using newtypes to derive logic for deriving custom monad transformers in our business logic. Using -XGeneralizedNewtypeDeriving we can recover the functionality of instances of the underlying types composed in our transformer stack.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype Velocity = Velocity { unVelocity :: Double }
  deriving (Eq, Ord)

v :: Velocity
v = Velocity 2.718

x :: Double
x = 2.718

-- Type error is caught at compile time even though
-- they are the same value at runtime!
err = v + x

newtype Quantity v a = Quantity a
  deriving (Eq, Ord, Num, Show)

data Haskeller
type Haskellers = Quantity Haskeller Int

a = Quantity 2 :: Haskellers
b = Quantity 6 :: Haskellers

totalHaskellers :: Haskellers
totalHaskellers = a + b

Couldn't match type `Double' with `Velocity'
Expected type: Velocity
  Actual type: Double
In the second argument of `(+)', namely `x'
In the expression: v + x

Using newtype deriving with the mtl library typeclasses we can produce flattened transformer types that don't require explicit lifting in the transform stack. For example, here is a little stack machine involving the Reader, Writer and State monads.

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Control.Monad.Reader
import Control.Monad.Writer
import Control.Monad.State

type Stack   = [Int]
type Output  = [Int]
type Program = [Instr]

type VM a = ReaderT Program (WriterT Output (State Stack)) a

newtype Comp a = Comp { unComp :: VM a }
  deriving (Monad, MonadReader Program, MonadWriter Output, MonadState Stack)

data Instr = Push Int | Pop | Puts

evalInstr :: Instr -> Comp ()
evalInstr instr = case instr of
  Pop    -> modify tail
  Push n -> modify (n:)
  Puts   -> do
    tos <- gets head
    tell [tos]

eval :: Comp ()
eval = do
  instr <- ask
  case instr of
    []     -> return ()
    (i:is) -> evalInstr i >> local (const is) eval

execVM :: Program -> Output
execVM = flip evalState [] . execWriterT . runReaderT (unComp eval)

program :: Program
program = [
     Push 42,
     Push 27,
     Puts,
     Pop,
     Puts,
     Pop
  ]

main :: IO ()
main = mapM_ print $ execVM program

Pattern matching on a newtype constructor compiles into nothing. For example theextractB function does not scrutinize the MkB constructor like the extractA does, because MkB does not exist at runtime, it is purely a compile-time construct.

data A = MkA Int
newtype B = MkB Int

extractA :: A -> Int
extractA (MkA x) = x

extractB :: B -> Int
extractB (MkB x) = x

Efficiency

The second monad transformer law guarantees that sequencing consecutive lift operations is semantically equivalent to lifting the results into the outer monad.

do x <- lift m  ==  lift $ do x <- m
   lift (f x)                 f x

Although they are guaranteed to yield the same result, the operation of lifting the results between the monad levels is not without cost and crops up frequently when working with the monad traversal and looping functions. For example, all three of the functions on the left below are less efficient than the right hand side which performs the bind in the base monad instead of lifting on each iteration.

-- Less Efficient      More Efficient
forever (lift m)    == lift (forever m)
mapM_ (lift . f) xs == lift (mapM_ f xs)
forM_ xs (lift . f) == lift (forM_ xs f)

Monad Morphisms

The base monad transformer package provides a MonadTrans class for lifting to another monad:

lift :: Monad m => m a -> t m a

But often times we need to work with and manipulate our monad transformer stack to either produce new transformers, modify existing ones or extend an upstream library with new layers. The mmorph library provides the capacity to compose monad morphism transformation directly on transformer stacks. The equivalent of type transformer type-level map is the hoist function.

hoist :: Monad m => (forall a. m a -> n a) -> t m b -> t n b

Hoist takes a monad morphism (a mapping from a m a to a n a) and applies in on the inner value monad of a transformer stack, transforming the value under the outer layer.

The monad morphism generalize takes an Identity monad into any another monad m.

generalize :: Monad m => Identity a -> m a

For example, it generalizes State s a (which is StateT s Identity a) to StateT s m a.

So we can generalize an existing transformer to lift an IO layer onto it.

import Control.Monad.State
import Control.Monad.Morph

type Eval a = State [Int] a

runEval :: [Int] -> Eval a -> a
runEval = flip evalState

pop :: Eval Int
pop = do
  top <- gets head
  modify tail
  return top

push :: Int -> Eval ()
push x = modify (x:)

ev1 :: Eval Int
ev1 = do
  push 3
  push 4
  pop
  pop

ev2  :: StateT [Int] IO ()
ev2 = do
  result <- hoist generalize ev1
  liftIO $ putStrLn $ "Result: " ++ show result

See: mmorph

Language Extensions

It's important to distinguish between different categories of language extensions general and specialized.

The inherent problem with classifying the extensions into the general and specialized categories is that it's a subjective classification. Haskellers who do type system research will have a very different interpretation of Haskell than people who do web programming. As such this is a conservative assessment, as an arbitrary baseline let's consider FlexibleInstances and OverloadedStrings "everyday" while GADTs and TypeFamilies are "specialized".

Key

• Benign implies both that importing the extension won't change the semantics of the module if not used and that enabling it makes it no easier to shoot yourself in the foot.
• Historical implies that one shouldn't use this extension, it's in GHC purely for backwards compatibility. Sometimes these are dangerous to enable.
• Steals syntax means that enabling this extension means that certain code valid in vanilla Haskell will no longer be accepted. For example, f $(a) is the same as f $ (a) in Haskell98, but TemplateHaskell will interpret $(a) as a splice.

See: GHC Extension Reference

The Benign

It's not obvious which extensions are the most common but it's fairly safe to say that these extensions are benign and are safely used extensively:

• OverloadedStrings
• FlexibleContexts
• FlexibleInstances
• GeneralizedNewtypeDeriving
• TypeSynonymInstances
• MultiParamTypeClasses
• FunctionalDependencies
• NoMonomorphismRestriction
• GADTs
• BangPatterns
• DeriveGeneric
• ScopedTypeVariables

The Dangerous

GHC's typechecker sometimes just casually tells us to enable language extensions when it can't solve certain problems. These include:

• DatatypeContexts
• OverlappingInstances
• IncoherentInstances
• ImpredicativeTypes
• AllowAmbigiousTypes

These almost always indicate a design flaw and shouldn't be turned on to remedy the error at hand, as much as GHC might suggest otherwise!

Type Inference

Inference in Haskell is usually precise, although there are several boundary cases where inference is difficult or impossible to infer a principal type of an expression. There a two common cases:

Mutually Recursive Binding Groups

f x = const x g
g y = f 'A'

The inferred type signatures are correct in their usage, but don't represent the most general signatures. When GHC analyzes the module it analyzes the dependencies of expressions on each other, groups them together, and applies substitutions from unification across mutually defined groups. As such the inferred types may not be the most general types possible, and an explicit signature may be desired.

-- Inferred types
f :: Char -> Char
g :: t -> Char

-- Most general types
f :: a -> a
g :: a -> Char

Polymorphic recursion

data Tree a = Leaf | Bin a (Tree (a, a))

size Leaf = 0
size (Bin _ t) = 1 + 2 * size t

The problem with this expression is because the inferred type variable a in size spans two possible types (a and (a,a)), the recursion is polymorphic. These two types won't pass the occurs-check of the typechecker and it yields an incorrect inferred type.

    Occurs check: cannot construct the infinite type: t0 = (t0, t0)
    Expected type: Tree t0
      Actual type: Tree (t0, t0)
    In the first argument of `size', namely `t'
    In the second argument of `(*)', namely `size t'
    In the second argument of `(+)', namely `2 * size t'

Simply adding an explicit type signature corrects this. Type inference using polymorphic recursion is undecidable in the general case.

size :: Tree a -> Int
size Leaf = 0
size (Bin _ t) = 1 + 2 * size t

See: Static Semantics of Function and Pattern Bindings

Monomorphism Restriction

The most common edge case of the inference is known as the dreaded monomorphism restriction.

When the toplevel declarations of a module are generalized the monomorphism restricts that toplevel values (i.e. expressions not under a lambda ) whose type contains the subclass of the Num type from the Prelude are not generalized and instead are instantiated with a monotype tried sequentially from the list specified by the default which is normally Integer, then Double.

-- Double is inferred by type inferencer.
example1 :: Double
example1 = 3.14

-- In the presense of a lambda, a different type is inferred!
example2 :: Fractional a => t -> a
example2 _ = 3.14

default (Integer, Double)

As of GHC 7.8, the monomorphism restriction is switched off by default in GHCi.

λ: set +t

λ: 3
3
it :: Num a => a

λ: default (Double)

λ: 3
3.0
it :: Num a => a

Extended Defaulting

Haskell normally applies several defaulting rules for ambigious literals in the absence of an explicit type signature. When an ambiguous literal is typechecked if at least one of its typeclass constraints is numeric and all of its classes are standard library classes, the module's default list is consulted, and the first type from the list that will satisfy the context of the type variable is instantiated. So for instance given the following default rules.

default (C1 a,...,Cn a)

The following set of heuristics is used to determine what to instnatiate the ambiguous type variable to.

1. The type variable a appears in no other constraints
2. All the classes Ci are standard.
3. At least one of the classes Ci is numeric.

The default default is (Integer, Double)

This is normally fine, but sometimes we'd like more granular control over defaulting. The -XExtendedDefaultRules loosens the restriction that we're constrained with working on Numerical typeclasses and the constraint that we can only work with standard library classes. If we'd like to have our string literals (using -XOverlodaedStrings) automatically default to the more efficient Text implementation instead of String we can twiddle the flag and GHC will perform the right substitution without the need for an explicit annotation on every string literal.

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE ExtendedDefaultRules #-}

import qualified Data.Text as T

default (T.Text)

example = "foo"

For code typed at the GHCi prompt, the -XExtendedDefaultRules flag is always on, and cannot be switched off.

See: Monomorphism Restriction

Safe Haskell

As everyone eventually finds out there are several functions within the implementation of GHC ( not the Haskell language ) that can be used to subvert the type-system, they are marked with the prefix unsafe. These functions exist only for when one can manually prove the soundness of an expression but can't express this property in the type-system or externalities to Haskell.

unsafeCoerce :: a -> b
unsafePerformIO :: IO a -> a

The Safe Haskell language extensions allow us to restrict the use of unsafe language features using -XSafe which restricts the import of modules which are themselves marked as Safe. It also forbids the use of certain language extensions (-XTemplateHaskell) which can be used to produce unsafe code. The primary use case of these extensions is security auditing.

{-# LANGUAGE Safe #-}
{-# LANGUAGE Trustworthy #-}

{-# LANGUAGE Safe #-}

import Unsafe.Coerce
import System.IO.Unsafe

bad1 :: String
bad1 = unsafePerformIO getLine

bad2 :: a
bad2 = unsafeCoerce 3.14 ()

Unsafe.Coerce: Can't be safely imported!
The module itself isn't safe.

See: Safe Haskell

Partial Type Signatures

The same hole technique can be applied at the toplevel for signatures:

const' :: _
const' x y = x

[1 of 1] Compiling Main             ( src/typedhole.hs, interpreted )

typedhole.hs:3:11:
    Found hole ‘_’ with type: t1 -> t -> t1
    Where: ‘t’ is a rigid type variable bound by
               the inferred type of const' :: t1 -> t -> t1 at foo.hs:4:1
           ‘t1’ is a rigid type variable bound by
                the inferred type of const' :: t1 -> t -> t1 at foo.hs:4:1
    To use the inferred type, enable PartialTypeSignatures
    In the type signature for ‘const'’: _
Failed, modules loaded: none.

Pattern wildcards can also be given explicit names so that GHC will use when reporting the inferred type in the resulting message.

foo :: _a -> _a
foo _ = False

typedhole.hs:6:9:
    Couldn't match expected type ‘_a’ with actual type ‘Bool’
      ‘_a’ is a rigid type variable bound by
           the type signature for foo :: _a -> _a at foo.hs:5:8
    Relevant bindings include foo :: _a -> _a (bound at foo.hs:6:1)
    In the expression: False
    In an equation for ‘foo’: foo _ = False
Failed, modules loaded: none.

The same wildcards can be used in type contexts to dump out inferred type class constraints:

succ' :: _ => a -> a
succ' x = x + 1

typedhole.hs:3:10:
    Found hole ‘_’ with inferred constraints: (Num a)
    To use the inferred type, enable PartialTypeSignatures
    In the type signature for ‘succ'’: _ => a -> a
Failed, modules loaded: none.

When the flag -XPartialTypeSignatures is passed to GHC and the inferred type is unambiguous, GHC will let us leave the holes in place and the compilation will proceed.

typedhole.hs:3:10: Warning:
    Found hole ‘_’ with type: w_
    Where: ‘w_’ is a rigid type variable bound by
                the inferred type of succ' :: w_ -> w_1 -> w_ at foo.hs:4:1
    In the type signature for ‘succ'’: _ -> _ -> _

Recursive Do

Recursive do notation allows to use to self-reference expressions on both sides of a monadic bind. For instance the following uses lazy evaluation to generate a infinite list. This is sometimes used for instantiating cyclic datatypes inside of a monadic context that need to hold a reference to themselves.

{-# LANGUAGE RecursiveDo #-}

justOnes :: Maybe [Int]
justOnes = do
  rec xs <- Just (1:xs)
  return (map negate xs)

See: Recursive Do Notation

Applicative Do

By default GHC desugars do-notation to use implicit invocations of bind and return.

test :: Monad m => m (a, b, c)
test = do
  a <- f
  b <- g
  c <- h
  return (a, b, c)

Desugars into:

test :: Monad m => m (a, b, c)
test =
f >>= \a ->
  g >>= \b ->
    h >>= \c ->
      return (a, b, c)

With ApplicativeDo this instead desugars into use of applicative combinators and a laxer Applicative constraint.

test :: Applicative m => m (a, b, c)
test = (,,) <$> f <*> g <*> h

Pattern Guards

Pattern guards are an extension to the pattern matching syntax. Given a <- pattern qualifier, the right hand side is evaluated and matched against the pattern on the left. If the match fails then the whole guard fails and the next equation is tried. If it succeeds, then the appropriate binding takes place, and the next qualifier is matched, in the augmented environment.

{-# LANGUAGE PatternGuards #-}

combine env x y
   | Just a <- lookup x env
   , Just b <- lookup y env
   = Just $ a + b

   | otherwise = Nothing

ViewPatterns

View patterns are like pattern guards that can be nested inside of other patterns. They are a convenient way of pattern-matching against values of algebraic data types.

{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE NoMonomorphismRestriction #-}

import Safe

lookupDefault :: Eq a => a -> b -> [(a,b)] -> b
lookupDefault k _ (lookup k -> Just s) = s
lookupDefault _ d _ = d

headTup :: (a, [t]) -> [t]
headTup (headMay . snd -> Just n) = [n]
headTup _ = []

headNil :: [a] -> [a]
headNil (headMay -> Just x) = [x]
headNil _ = []

TupleSections

{-# LANGUAGE TupleSections #-}

first :: a -> (a, Bool)
first = (,True)

second :: a -> (Bool, a)
second = (True,)

f :: t -> t1 -> t2 -> t3 -> (t, (), t1, (), (), t2, t3)
f = (,(),,(),(),,)

MultiWayIf

{-# LANGUAGE MultiWayIf #-}

bmiTell :: Float -> String
bmiTell bmi = if
  | bmi <= 18.5 -> "You're underweight."
  | bmi <= 25.0 -> "You're average weight."
  | bmi <= 30.0 -> "You're overewight."
  | otherwise   -> "You're a whale."

EmptyCase

GHC normally requires at least one pattern branch in case statement this restriction can be relaxed with -XEmptyCase. The case statement then immediately yields a Non-exhaustive patterns in case if evaluated.

test = case of

LambdaCase

For case statements, LambdaCase allows the elimination of redundant free variables introduced purely for the case of pattern matching on.

\case
  p1 -> 32
  p2 -> 32

\temp -> case temp of
  p1 -> 32
  p2 -> 32

{-# LANGUAGE LambdaCase #-}

data Exp a
  = Lam a (Exp a)
  | Var a
  | App (Exp a) (Exp a)

example :: Exp a -> a
example = \case
  Lam a b -> a
  Var a   -> a
  App a b -> example a

NumDecimals

NumDecimals allows the use of exponential notation for integral literals that are not necessarily floats. Without it, any use of expontial notation induces a Fractional class constraint.

googol :: Fractional a => a
googol = 1e100

{-# LANGUAGE NumDecimals #-}
googol :: Num a => a
googol = 1e100

PackageImports

Package imports allows us to disambiguate hierarchical package names by their respective package key. This is useful in the case where you have to imported packages that expose the same module. In practice most of the common libraries have taken care to avoid conflicts in the namespace and this is not usually a problem in most modern Haskell.

For example we could explicitly ask GHC to resolve that Control.Monad.Error package be drawn from the mtl library.

import qualified "mtl" Control.Monad.Error as Error
import qualified "mtl" Control.Monad.State as State
import qualified "mtl" Control.Monad.Reader as Reader

RecordWildCards

Record wild cards allow us to expand out the names of a record as variables scoped as the labels of the record implicitly. The extension can be used to extract variables names into a scope or to assign to variables in a record drawing, aligning the record's labels with the variables in scope for the assignment. The syntax introduced is the {..} pattern selector.

{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE OverloadedStrings #-}

import Data.Text

data  Example = Example
  { e1 :: Int
  , e2 :: Text
  , e3 :: Text
  } deriving (Show)

-- Extracting from a record using wildcards.
scope :: Example -> (Int, Text, Text)
scope Example {..} = (e1, e2, e3)

-- Assign to a record using wildcards.
assign :: Example
assign = Example {..}
  where
    (e1, e2, e3) = (1, "Kirk", "Picard")

NamedFieldPuns

Provides alternative syntax for accessing record fields in a pattern match.

data D = D {a :: Int, b :: Int}

f :: D -> Int
f D {a, b} = a - b

-- Order doesn't matter
g :: D -> Int
g D {b, a} = a - b

PatternSynonyms

Suppose we were writing a typechecker, it would be very common to include a distinct TArr term to ease the telescoping of function signatures, this is what GHC does in its Core language. Even though technically it could be written in terms of more basic application of the (->) constructor.

data Type
  = TVar TVar
  | TCon TyCon
  | TApp Type Type
  | TArr Type Type
  deriving (Show, Eq, Ord)

With pattern synonyms we can eliminate the extraneous constructor without losing the convenience of pattern matching on arrow types.

{-# LANGUAGE PatternSynonyms #-}

pattern TArr t1 t2 = TApp (TApp (TCon "(->)") t1) t2

So now we can write an eliminator and constructor for arrow type very naturally.

{-# LANGUAGE PatternSynonyms #-}

import Data.List (foldl1')

type Name  = String
type TVar  = String
type TyCon = String

data Type
  = TVar TVar
  | TCon TyCon
  | TApp Type Type
  deriving (Show, Eq, Ord)


pattern TArr t1 t2 = TApp (TApp (TCon "(->)") t1) t2

tapp :: TyCon -> [Type] -> Type
tapp tcon args = foldl TApp (TCon tcon) args

arr :: [Type] -> Type
arr ts = foldl1' (\t1 t2 -> tapp "(->)" [t1, t2]) ts

elimTArr :: Type -> [Type]
elimTArr (TArr (TArr t1 t2) t3) = t1 : t2 : elimTArr t3
elimTArr (TArr t1 t2) = t1 : elimTArr t2
elimTArr t = [t]

-- (->) a ((->) b a)
-- a -> b -> a
to :: Type
to = arr [TVar "a", TVar "b", TVar "a"]

from :: [Type]
from = elimTArr to

Pattern synonyms can be exported from a module like any other definition by prefixing them with the prefix pattern.

module MyModule (
  pattern Elt
) where

pattern Elt = [a]

• Pattern Synonyms in GHC 8

DeriveTraversable

DeriveFoldable

DeriveFunctor

DeriveGeneric

DeriveAnyClass

With -XDeriveAnyClass we can derive any class. The deriving logic s generates an instance declaration for the type with no explicitly-defined methods. If the typeclass implements a default for each method then this will be well-defined and give rise to an automatic instances.

StaticPointers

DuplicateRecordFields

GHC 8.0 introduced the DuplicateRecordFields extensions which loosens GHC's restriction on records in the same module with identical accessors. The precise type that is being projected into is now deferred to the callsite.

{-# LANGUAGE DuplicateRecordFields #-}

data Person = Person { id :: Int }
data Animal = Animal { id :: Int }
data Vegetable = Vegetable { id :: Int }

test :: (Person, Animal, Vegetable)
test = (Person {id = 1}, Animal {id = 2}, Vegetable {id = 3})

Using just DuplicateRecordFields, projection is still not supported so the following will not work. OverloadedLabels fixes this to some extent.

test :: (Person, Animal, Vegetable)
test = (id (Person 1), id (Animal 2), id (Animal 3))

OverloadedLabels

GHC 8.0 also introduced the OverloadedLabels extension which allows a limited form of polymorphism over labels that share the same name.

To work with overloaded labels types we need to enable several language extensions to work with promoted strings and multiparam typeclasses that underly it's implementation.

extract :: IsLabel "id" t => t
extract = #id

{-# LANGUAGE OverloadedLabels #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE DuplicateRecordFields #-}
{-# LANGUAGE ExistentialQuantification #-}

import GHC.Records (HasField(..))
import GHC.OverloadedLabels (IsLabel(..))

data S = MkS { foo :: Int }
data T x y z = forall b . MkT { foo :: y, bar :: b }

instance HasField x r a => IsLabel x (r -> a) where
  fromLabel = getField

main :: IO ()
main = do
  print (#foo (MkS 42))
  print (#foo (MkT True False))

See:

• OverloadedRecordFields revived

Cpp

The C++ preprocessor is the fallback whenever we really need to separate out logic that has to span multiple versions of GHC and language changes while maintaining backwards compatibility. It can dispatch on the version of GHC being used to compile a module.

{-# LANGUAGE CPP #-}

#if (__GLASGOW_HASKELL__ > 710)
-- Imports for GHC 7.10.x
#else
-- Imports for other GHC
#endif

To demarcate code based on the operating system compiled on.

{-# LANGUAGE CPP #-}

#ifdef OS_Linux
  -- Linux specific logic
#else
# ifdef OS_Win32
  -- Windows specific logic
# else
# ifdef OS_Mac
  -- Macintosh specific logic
# else
  -- Other operating systems
# endif
# endif
#endif

Or on the version of the base library used.

#if !MIN_VERSION_base(4,6,0)
  -- Base specific logic
#endif

It can also be abused to do terrible things like metaprogrammming with strings, but please don't do this.

Historical Extensions

Several language extensions have either been absorbed into the core language or become deprecated in favor of others. Others are just considered misfeatures.

• Rank2Types - Rank2Types has been subsumed by RankNTypes
• XPolymorphicComponents - Was an implementation detail of higher-rank polymorphism that no longer exists.
• NPlusKPatterns - These were largely considered an ugly edge-case of pattern matching language that was best removed.
• TraditionalRecordSyntax - Traditional record syntax was an extension to the Haskell 98 specification for what we now consider standard record syntax.
• OverlappingInstances - Subsumed by explicit OVERLAPPING pragmas.
• IncoherentInstances - Subsumed by explicit INCOHERENT pragmas.
• NullaryTypeClasses - Subsumed by explicit Multiparameter Typeclasses with no parameters.

Type Classes

Minimal Annotations

In the presence of default implementations of typeclasses methods, there may be several ways to implement a typeclass. For instance Eq is entirely defined by either defining when two values are equal or not equal by implying taking the negation of the other. We can define equality in terms of non-equality and vice-versa.

class Eq a where
  (==), (/=) :: a -> a -> Bool
  x == y = not (x /= y)
  x /= y = not (x == y)

Before 7.6.1 there was no way to specify what was the "minimal" definition required to implement a typeclass

class Eq a where
  (==), (/=) :: a -> a -> Bool
  x == y = not (x /= y)
  x /= y = not (x == y)
  {-# MINIMAL (==) #-}
  {-# MINIMAL (/=) #-}

Minimal pragmas are boolean expressions, with | as logical OR, either definition must be defined). Comma indicates logical AND where both sides both definitions must be defined.

{-# MINIMAL (==) | (/=) #-} -- Either (==) or (/=)
{-# MINIMAL (==) , (/=) #-} -- Both (==) and (/=)

Compiling the -Wmissing-methods will warn when a instance is defined that does not meet the minimal criterion.

FlexibleInstances

{-# LANGUAGE FlexibleInstances #-}

class MyClass a

-- Without flexible instances, all instance heads must be type variable. The
-- following would be legal.
instance MyClass (Maybe a)

-- With flexible instances, typeclass heads can be arbitrary nested types. The
-- following would be forbidden without it.
instance MyClass (Maybe Int)

FlexibleContexts

{-# LANGUAGE FlexibleContexts #-}

class MyClass a

-- Without flexible contexts, all contexts must be type variable. The
-- following would be legal.
instance (MyClass a) => MyClass (Either a b)

-- With flexible contexts, typeclass contexts can be arbitrary nested types. The
-- following would be forbidden without it.
instance (MyClass (Maybe a)) => MyClass (Either a b)

OverlappingInstances

Typeclasses are normally globally coherent, there is only ever one instance that can be resolved for a type unambiguously for a type at any call site in the program. There are however extensions to loosen this restriction and perform more manual direction of the instance search.

Overlapping instances loosens the coherent condition (there can be multiple instances) but introduces a criterion that it will resolve to the most specific one.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE OverlappingInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

class MyClass a b where
  fn :: (a,b)

instance MyClass Int b where
  fn = error "b"

instance MyClass a Int where
  fn = error "a"

instance MyClass Int Int where
  fn = error "c"

example :: (Int, Int)
example = fn

Historically enabling this on module-level was not the best idea, since generally we define multiple classes in a module only a subset of which may be incoherent. So as of 7.10 we now have the capacity to just annotate instances with the OVERLAPPING and INCOHERENT pragmas.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

class MyClass a b where
  fn :: (a,b)

instance {-# OVERLAPPING #-} MyClass Int b where
  fn = error "b"

instance {-# OVERLAPPING #-} MyClass a Int where
  fn = error "a"

instance {-# OVERLAPPING #-} MyClass Int Int where
  fn = error "c"

example :: (Int, Int)
example = fn

IncoherentInstances

Incoherent instance loosens the restriction that there be only one specific instance, will choose one arbitrarily (based on the arbitrary sorting of it's internal representation ) and the resulting program will typecheck. This is generally pretty crazy and usually a sign of poor design.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE IncoherentInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

class MyClass a b where
  fn :: (a,b)

instance MyClass Int b where
  fn = error "a"

instance MyClass a Int where
  fn = error "b"

example :: (Int, Int)
example = fn

There is also an incoherent instance.

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}

class MyClass a b where
  fn :: (a,b)

instance {-# INCOHERENT #-} MyClass a Int where
  fn = error "general"

instance {-# INCOHERENT #-} MyClass Int Int where
  fn = error "specific"

example :: (Int, Int)
example = fn

TypeSynonymInstances

{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}

type IntList = [Int]

class MyClass a

-- Without type synonym instances, we're forced to manually expand out type
-- synonyms in the typeclass head.
instance MyClass [Int]

-- With it GHC will do this for us automatically. Type synonyms still need to
-- be fully applied.
instance MyClass IntList

Laziness

Again, a subject on which much ink has been spilled. There is an ongoing discussion in the land of Haskell about the compromises between lazy and strict evaluation, and there are nuanced arguments for having either paradigm be the default. Haskell takes a hybrid approach and allows strict evaluation when needed and uses laziness by default. Needless to say, we can always find examples where strict evaluation exhibits worse behavior than lazy evaluation and vice versa.

The primary advantage of lazy evaluation in the large is that algorithms that operate over both unbounded and bounded data structures can inhabit the same type signatures and be composed without additional need to restructure their logic or force intermediate computations. Languages that attempt to bolt laziness on to a strict evaluation model often bifurcate classes of algorithms into ones that are hand-adjusted to consume unbounded structures and those which operate over bounded structures. In strict languages mixing and matching between lazy vs strict processing often necessitates manifesting large intermediate structures in memory when such composition would "just work" in a lazy language.

By virtue of Haskell being the only language to actually explore this point in the design space to the point of being industrial strength; knowledge about lazy evaluation is not widely absorbed into the collective programmer consciousness and can often be non-intuitive to the novice. This doesn't reflect on the model itself, merely on the need for more instruction material and research on optimizing lazy compilers.

The paradox of Haskell is that it explores so many definably unique ideas ( laziness, purity, typeclasses ) that it becomes difficult to separate out the discussion of any one from the gestalt of the whole implementation.

See:

• Oh My Laziness!
• Reasoning about Laziness
• Lazy Evaluation of Haskell
• More Points For Lazy Evaluation
• How Lazy Evaluation Works in Haskell

Strictness

There are several evaluation models for the lambda calculus:

• Strict - Evaluation is said to be strict if all arguments are evaluated before the body of a function.
• Non-strict - Evaluation is non-strict if the arguments are not necessarily evaluated before entering the body of a function.

These ideas give rise to several models, Haskell itself use the call-by-need model.

Seq and WHNF

A term is said to be in weak head normal-form if the outermost constructor or lambda cannot be reduced further. A term is said to be in normal form if it is fully evaluated and all sub-expressions and thunks contained within are evaluated.

-- In Normal Form
42
(2, "foo")
\x -> x + 1

-- Not in Normal Form
1 + 2
(\x -> x + 1) 2
"foo" ++ "bar"
(1 + 1, "foo")

-- In Weak Head Normal Form
(1 + 1, "foo")
\x -> 2 + 2
'f' : ("oo" ++ "bar")

-- Not In Weak Head Normal Form
1 + 1
(\x -> x + 1) 2
"foo" ++ "bar"

In Haskell normal evaluation only occurs at the outer constructor of case-statements in Core. If we pattern match on a list we don't implicitly force all values in the list. An element in a data structure is only evaluated up to the most outer constructor. For example, to evaluate the length of a list we need only scrutinize the outer Cons constructors without regard for their inner values.

λ: length [undefined, 1]
2

λ: head [undefined, 1]
Prelude.undefined

λ: snd (undefined, 1)
1

λ: fst (undefined, 1)
Prelude.undefined

For example, in a lazy language the following program terminates even though it contains diverging terms.

ignore :: a -> Int
ignore x = 0

loop :: a
loop = loop

main :: IO ()
main = print $ ignore loop

In a strict language like OCaml ( ignoring its suspensions for the moment ), the same program diverges.

let ignore x = 0;; 
let rec loop a = loop a;;

print_int (ignore (loop ()));

In Haskell a thunk is created to stand for an unevaluated computation. Evaluation of a thunk is called forcing the thunk. The result is an update, a referentially transparent effect, which replaces the memory representation of the thunk with the computed value. The fundamental idea is that a thunk is only updated once ( although it may be forced simultaneously in a multi-threaded environment ) and its resulting value is shared when referenced subsequently.

The command :sprint can be used to introspect the state of unevaluated thunks inside an expression without forcing evaluation. For instance:

λ: let a = [1..] :: [Integer]
λ: let b = map (+ 1) a

λ: :sprint a
a = _
λ: :sprint b
b = _
λ: a !! 4
5
λ: :sprint a
a = 1 : 2 : 3 : 4 : 5 : _
λ: b !! 10
12
λ: :sprint a
a = 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : _
λ: :sprint b
b = _ : _ : _ : _ : _ : _ : _ : _ : _ : _ : 12 : _

While a thunk is being computed its memory representation is replaced with a special form known as blackhole which indicates that computation is ongoing and allows for a short circuit for when a computation might depend on itself to complete. The implementation of this is some of the more subtle details of the GHC runtime.

The seq function introduces an artificial dependence on the evaluation of order of two terms by requiring that the first argument be evaluated to WHNF before the evaluation of the second. The implementation of the seq function is an implementation detail of GHC.

seq :: a -> b -> b

⊥ `seq` a = ⊥
a `seq` b = b

The infamous foldl is well-known to leak space when used carelessly and without several compiler optimizations applied. The strict foldl' variant uses seq to overcome this.

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' _ z [] = z
foldl' f z (x:xs) = let z' = f z x in z' `seq` foldl' f z' xs

In practice, a combination between the strictness analyzer and the inliner on -O2 will ensure that the strict variant of foldl is used whenever the function is inlinable at call site so manually using foldl' is most often not required.

Of important note is that GHCi runs without any optimizations applied so the same program that performs poorly in GHCi may not have the same performance characteristics when compiled with GHC.

Strictness Annotations

The extension BangPatterns allows an alternative syntax to force arguments to functions to be wrapped in seq. A bang operator on an arguments forces its evaluation to weak head normal form before performing the pattern match. This can be used to keep specific arguments evaluated throughout recursion instead of creating a giant chain of thunks.

{-# LANGUAGE BangPatterns #-}

sum :: Num a => [a] -> a
sum = go 0
  where
    go !acc (x:xs) = go (acc + x) xs
    go  acc []     = acc

This is desugared into code effectively equivalent to the following:

sum :: Num a => [a] -> a
sum = go 0
  where
    go acc _ | acc `seq` False = undefined
    go acc (x:xs)              = go (acc + x) xs
    go acc []                  = acc

Function application to seq'd arguments is common enough that it has a special operator.

($!) :: (a -> b) -> a -> b
f $! x  = let !vx = x in f vx

Strict Haskell

As of GHC 8.0 strictness annotations can be applied to all definitions in a module automatically. In previous versions it was necessary to definitions via explicit syntactic annotations at all sites.

StrictData

Enabling StrictData makes constructor fields strict by default on any module it is enabled on.

{-# LANGUAGE StrictData #-}

data Employee = Employee
  { name :: T.Text
  , age :: Int
  }

Is equivalent to:

data Employee = Employee
  { name :: !T.Text
  , age :: !Int
  }

Strict

Strict implies -XStrictData and extends strictness annotations to all arguments of functions.

f x y = x + y

Is equivalent to the following function declaration with explicit bang patterns:

f !x !y = x + y

On a module-level this effectively makes Haskell a call-by-value language with some caveats. All arguments to functions are now explicitly evaluated and all data in constructors within this module are in head normal form by construction. However there are some subtle points to this that are better explained in the language guide.

• Strict Extensions

Deepseq

There are often times when for performance reasons we need to deeply evaluate a data structure to normal form leaving no terms unevaluated. The deepseq library performs this task.

The typeclass NFData (Normal Form Data) allows us to seq all elements of a structure across any subtypes which themselves implement NFData.

class NFData a where
  rnf :: a -> ()
  rnf a = a `seq` ()

deepseq :: NFData a => a -> b -> b
($!!) :: (NFData a) => (a -> b) -> a -> b

instance NFData Int
instance NFData (a -> b)

instance NFData a => NFData (Maybe a) where
    rnf Nothing  = ()
    rnf (Just x) = rnf x

instance NFData a => NFData [a] where
    rnf [] = ()
    rnf (x:xs) = rnf x `seq` rnf xs

[1, undefined] `seq` ()
-- ()

[1, undefined] `deepseq` ()
-- Prelude.undefined

To force a data structure itself to be fully evaluated we share the same argument in both positions of deepseq.

force :: NFData a => a -> a
force x = x `deepseq` x

Irrefutable Patterns

A lazy pattern doesn't require a match on the outer constructor, instead it lazily calls the accessors of the values as needed. In the presence of a bottom, we fail at the usage site instead of the outer pattern match.

f :: (a, b) -> Int
f (a,b) = const 1 a

g :: (a, b) -> Int
g ~(a,b) = const 1 a

-- λ: f undefined
-- *** Exception: Prelude.undefined
-- λ: g undefined
-- 1

j :: Maybe t -> t
j ~(Just x) = x

k :: Maybe t -> t
k (Just x) = x

-- λ: j Nothing
-- *** Exception: src/05-laziness/lazy_patterns.hs:15:1-15: Irrefutable pattern failed for pattern (Just x)
--
-- λ: k Nothing
-- *** Exception: src/05-laziness/lazy_patterns.hs:18:1-14: Non-exhaustive patterns in function k

Prelude

What to Avoid?

Haskell being a 25 year old language has witnessed several revolutions in the way we structure and compose functional programs. Yet as a result several portions of the Prelude still reflect old schools of thought that simply can't be removed without breaking significant parts of the ecosystem.

Currently it really only exists in folklore which parts to use and which not to use, although this is a topic that almost all introductory books don't mention and instead make extensive use of the Prelude for simplicity's sake.

The short version of the advice on the Prelude is:

The instances of Foldable for the list type often conflict with the monomorphic versions in the Prelude which are left in for historical reasons. So often times it is desirable to explicitly mask these functions from implicit import and force the use of Foldable and Traversable instead.

Of course often times one wishes only to use the Prelude explicitly and one can explicitly import it qualified and use the pieces as desired without the implicit import of the whole namespace.

import qualified Prelude as P

What Should be in Base

To get work done you probably need.

Custom Preludes

The default Prelude can be disabled in it's entirety by twiddling the -XNoImplicitPrelude flag.

{-# LANGUAGE NoImplicitPrelude #-}

We are then free to build an equivalent Prelude that is more to our liking. Using module reexporting we can pluck the good parts of the prelude and libraries like safe to build up a more industrial focused set of default functions. For example:

module Custom (
  module Exports,
) where

import Data.Int as Exports
import Data.Tuple as Exports
import Data.Maybe as Exports
import Data.String as Exports
import Data.Foldable as Exports
import Data.Traversable as Exports

import Control.Monad.Trans.Except
  as Exports
  (ExceptT(ExceptT), Except, except, runExcept, runExceptT,
   mapExcept, mapExceptT, withExcept, withExceptT)

The Prelude itself is entirely replicable as well, presuming that an entire project is compiled without the implicit Prelude. Several packages have arisen that supply much of the same functionality in a way that appeals to more modern design principles.

Protolude

Protolude is a minimalist Prelude which provides many sensible defaults for writing modern Haskell and is compatible with existing code.

• protolude

{-# LANGUAGE NoImplicitPrelude #-}

import Protolude

Other examples for alternative Preludes include (your mileage may vary with these):

• base-prelude
• basic-prelude
• classy-prelude
• Other Preludes

Partial Functions

A partial function is a function which doesn't terminate and yield a value for all given inputs. Conversely a total function terminates and is always defined for all inputs. As mentioned previously, certain historical parts of the Prelude are full of partial functions.

The difference between partial and total functions is the compiler can't reason about the runtime safety of partial functions purely from the information specified in the language and as such the proof of safety is left to the user to guarantee. They are safe to use in the case where the user can guarantee that invalid inputs cannot occur, but like any unchecked property its safety or not-safety is going to depend on the diligence of the programmer. This very much goes against the overall philosophy of Haskell and as such they are discouraged when not necessary.

head :: [a] -> a
read :: Read a => String -> a
(!!) :: [a] -> Int -> a

Safe

The Prelude has total variants of the historical partial functions (i.e. Text.Read.readMaybe)in some cases, but often these are found in the various utility libraries like safe.

The total versions provided fall into three cases:

• May - return Nothing when the function is not defined for the inputs
• Def - provide a default value when the function is not defined for the inputs
• Note - call error with a custom error message when the function is not defined for the inputs. This is not safe, but slightly easier to debug!

-- Total
headMay :: [a] -> Maybe a
readMay :: Read a => String -> Maybe a
atMay :: [a] -> Int -> Maybe a

-- Total
headDef :: a -> [a] -> a
readDef :: Read a => a -> String -> a
atDef   :: a -> [a] -> Int -> a

-- Partial
headNote :: String -> [a] -> a
readNote :: Read a => String -> String -> a
atNote   :: String -> [a] -> Int -> a

Boolean Blindness

data Bool = True | False

isJust :: Maybe a -> Bool
isJust (Just x) = True
isJust Nothing  = False

The problem with the boolean type is that there is effectively no difference between True and False at the type level. A proposition taking a value to a Bool takes any information given and destroys it. To reason about the behavior we have to trace the provenance of the proposition we're getting the boolean answer from, and this introduces a whole slew of possibilities for misinterpretation. In the worst case, the only way to reason about safe and unsafe use of a function is by trusting that a predicate's lexical name reflects its provenance!

For instance, testing some proposition over a Bool value representing whether the branch can perform the computation safely in the presence of a null is subject to accidental interchange. Consider that in a language like C or Python testing whether a value is null is indistinguishable to the language from testing whether the value is not null. Which of these programs encodes safe usage and which segfaults?

# This one?
if p(x):
    # use x
elif not p(x):
    # don't use x

# Or this one?
if p(x):
    # don't use x
elif not p(x):
    # use x

From inspection we can't tell without knowing how p is defined, the compiler can't distinguish the two either and thus the language won't save us if we happen to mix them up. Instead of making invalid states unrepresentable we've made the invalid state indistinguishable from the valid one!

The more desirable practice is to match on terms which explicitly witness the proposition as a type ( often in a sum type ) and won't typecheck otherwise.

case x of
  Just a  -> use x
  Nothing -> don't use x

-- not ideal
case p x of
  True  -> use x
  False -> don't use x

-- not ideal
if p x
  then use x
  else don't use x

To be fair though, many popular languages completely lack the notion of sum types ( the source of many woes in my opinion ) and only have product types, so this type of reasoning sometimes has no direct equivalence for those not familiar with ML family languages.

In Haskell, the Prelude provides functions like isJust and fromJust both of which can be used to subvert this kind of reasoning and make it easy to introduce bugs and should often be avoided.

Foldable / Traversable

If coming from an imperative background retraining one's self to think about iteration over lists in terms of maps, folds, and scans can be challenging.

Prelude.foldl :: (a -> b -> a) -> a -> [b] -> a
Prelude.foldr :: (a -> b -> b) -> b -> [a] -> b

-- pseudocode
foldr f z [a...] = f a (f b ( ... (f y z) ... ))
foldl f z [a...] = f ... (f (f z a) b) ... y

For a concrete consider the simple arithmetic sequence over the binary operator (+):

-- foldr (+) 1 [2..]
(1 + (2 + (3 + (4 + ...))))

-- foldl (+) 1 [2..]
((((1 + 2) + 3) + 4) + ...)

Foldable and Traversable are the general interface for all traversals and folds of any data structure which is parameterized over its element type ( List, Map, Set, Maybe, ...). These two classes are used everywhere in modern Haskell and are extremely important.

A foldable instance allows us to apply functions to data types of monoidal values that collapse the structure using some logic over mappend.

A traversable instance allows us to apply functions to data types that walk the structure left-to-right within an applicative context.

class (Functor f, Foldable f) => Traversable f where
  traverse :: Applicative g => (a -> g b) -> f a -> g (f b)

class Foldable f where
  foldMap :: Monoid m => (a -> m) -> f a -> m

The foldMap function is extremely general and non-intuitively many of the monomorphic list folds can themselves be written in terms of this single polymorphic function.

foldMap takes a function of values to a monoidal quantity, a functor over the values and collapses the functor into the monoid. For instance for the trivial Sum monoid:

λ: foldMap Sum [1..10]
Sum {getSum = 55}

For instance if we wanted to map a list of some abstract element types into a hashtable of elements based on pattern matching we could use it.

import Data.Foldable
import qualified Data.Map as Map

data Elt
  = Elt Int Double
  | Nil

foo :: [Elt] -> Map.Map Int Double
foo = foldMap go
  where
    go (Elt x y) = Map.singleton x y
    go Nil = Map.empty

The full Foldable class (with all default implementations) contains a variety of derived functions which themselves can be written in terms of foldMap and Endo.

newtype Endo a = Endo {appEndo :: a -> a}

instance Monoid (Endo a) where
  mempty = Endo id
  Endo f `mappend` Endo g = Endo (f . g)

class Foldable t where
    fold    :: Monoid m => t m -> m
    foldMap :: Monoid m => (a -> m) -> t a -> m

    foldr   :: (a -> b -> b) -> b -> t a -> b
    foldr'  :: (a -> b -> b) -> b -> t a -> b

    foldl   :: (b -> a -> b) -> b -> t a -> b
    foldl'  :: (b -> a -> b) -> b -> t a -> b

    foldr1  :: (a -> a -> a) -> t a -> a
    foldl1  :: (a -> a -> a) -> t a -> a

For example:

foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

Most of the operations over lists can be generalized in terms of combinations of Foldable and Traversable to derive more general functions that work over all data structures implementing Foldable.

Data.Foldable.elem    :: (Eq a, Foldable t) => a -> t a -> Bool
Data.Foldable.sum     :: (Num a, Foldable t) => t a -> a
Data.Foldable.minimum :: (Ord a, Foldable t) => t a -> a
Data.Traversable.mapM :: (Monad m, Traversable t) => (a -> m b) -> t a -> m (t b)

Unfortunately for historical reasons the names exported by foldable quite often conflict with ones defined in the Prelude, either import them qualified or just disable the Prelude. The operations in the Foldable all specialize to the same and behave the same as the ones in Prelude for List types.

import Data.Monoid
import Data.Foldable
import Data.Traversable

import Control.Applicative
import Control.Monad.Identity (runIdentity)
import Prelude hiding (mapM_, foldr)

-- Rose Tree
data Tree a = Node a [Tree a] deriving (Show)

instance Functor Tree where
  fmap f (Node x ts) = Node (f x) (fmap (fmap f) ts)

instance Traversable Tree where
  traverse f (Node x ts) = Node <$> f x <*> traverse (traverse f) ts

instance Foldable Tree where
  foldMap f (Node x ts) = f x `mappend` foldMap (foldMap f) ts


tree :: Tree Integer
tree = Node 1 [Node 1 [], Node 2 [] ,Node 3 []]


example1 :: IO ()
example1 = mapM_ print tree

example2 :: Integer
example2 = foldr (+) 0 tree

example3 :: Maybe (Tree Integer)
example3 = traverse (\x -> if x > 2 then Just x else Nothing) tree

example4 :: Tree Integer
example4 = runIdentity $ traverse (\x -> pure (x+1)) tree

The instances we defined above can also be automatically derived by GHC using several language extensions. The automatic instances are identical to the hand-written versions above.

{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveTraversable #-}

data Tree a = Node a [Tree a]
  deriving (Show, Functor, Foldable, Traversable)

See: Typeclassopedia

Corecursion

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

A recursive function consumes data and eventually terminates, a corecursive function generates data and coterminates. A corecursive function is said to be productive if it can always evaluate more of the resulting value in bounded time.

import Data.List

f :: Int -> Maybe (Int, Int)
f 0 = Nothing
f x = Just (x, x-1)

rev :: [Int]
rev = unfoldr f 10

fibs :: [Int]
fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

split

The split package provides a variety of missing functions for splitting list and string types.

import Data.List.Split

example1 :: [String]
example1 = splitOn "." "foo.bar.baz"
-- ["foo","bar","baz"]

example2 :: [String]
example2 = chunksOf 10 "To be or not to be that is the question."
-- ["To be or n","ot to be t","hat is the"," question."]

monad-loops

The monad-loops package provides a variety of missing functions for control logic in monadic contexts.

whileM :: Monad m => m Bool -> m a -> m [a]
untilM :: Monad m => m a -> m Bool -> m [a]
iterateUntilM :: Monad m => (a -> Bool) -> (a -> m a) -> a -> m a
whileJust :: Monad m => m (Maybe a) -> (a -> m b) -> m [b]

Foundation

TODO

See: Foundation

Strings

String

The default Haskell string type is implemented as a naive linked list of characters, this is terrible for most purposes but no one knows how to fix it without rewriting large portions of all code that exists and nobody can commit the time to fix it. So it remains broken, likely forever.

type String = [Char]

For more performance sensitive cases there are two libraries for processing textual data: text and bytestring.

• text - Used for handling unicode data.
• bytestring - Used for handling ASCII data that needs to interchanged with C code or network protocols.

For each of these there are two variants for both text and bytestring.

• lazy Lazy text objects are encoded as lazy lists of strict chunks of bytes.
• strict Byte vectors are encoded as strict Word8 arrays of bytes or code points

Giving rise to the four types.

Conversions

Conversions between strings types ( from : left column, to : top row ) are done with several functions across the bytestring and text libraries. The mapping between text and bytestring is inherently lossy so there is some degree of freedom in choosing the encoding. We'll just consider utf-8 for simplicity.