Daily Dose of Haskell, #1: Get Haskell installed

If you’re going to learn Haskell, installing it on your machine is a
good idea.  Hop onto http://www.haskell.org/platform/ and download the
Haskell Platform.  Try to get at least v2012.2.0.0.

If you don’t want to install Haskell on your own machine, it’s all
installed on Athena; just run 'add -f ghc', and you’ll be good to go.

If the installation succeeds, you should be able to run
'ghc --version' and get a version notice.  You should also be able to
run 'ghci' and get an interpreter.


Daily Dose of Haskell, #2: Prelude functions and operators

All Haskell programs start with the Prelude module in scope.  Prelude
defines a large number of frequently-used and useful functions and
operators.  (In Haskell, an operator is merely a function whose name
consists entirely of symbols.)  All operators are infix, and all
functions are prefix.

Haskell function-call syntax is a bit weird at first – you don’t use
parentheses, and arguments are separated by spaces, not commas.  With
that in mind, you can use 'ghci', the Haskell REPL, as a pretty sweet
calculator:

    Prelude> 2 + 7
    9
    Prelude> 3 ^ 3 - 42.6
    -15.600000000000001
    Prelude> sqrt 96
    9.797958971132712
    Prelude> max 3 7
    7

Your turn: go evaluate some arithmetic expressions in GHCi.


Daily Dose of Haskell, #3: Defining your own functions

Haskell is a @i{functional} programming language, so it’s easy to
define your own functions.  You write them out as equations, just as
you would in math:

    > plusOne x = x + 1

It’s a good idea to place your definitions in a file and load them
into GHCi, rather than trying to define them directly in GHCi.  (The
GHCi syntax is slightly different.)  As a convention, if I start a
line with “>”, it’s in the context in a file, and if I start a line
with “XXX>”, where “XXX” is one or more module names, it’s in the
context of GHCi.

So, having written the above definition to /tmp/stuff.hs, I can run

    Prelude> :load /tmp/stuff.hs
    [1 of 1] Compiling Main             ( /tmp/stuff.hs, interpreted )
    Ok, modules loaded: Main.
    *Main> plusOne 7
    8

Your turn: define a function which, given a, b, c, and x, evaluates
ax² + bx + c.  Use it to verify that 43x² - 16x - 91 has roots at
(8 ± √3977) / 43.


Daily Dose of Haskell, #4: Pattern matching and case analysis

In mathematics, you’d probably define the factorial function in cases,
like this:

    0! = 1
    n! = n × (n-1)!

In Haskell, you can do the same:

    > fact 0 = 1
    > fact n = n * fact (n - 1)

    *Main> fact 0
    1
    *Main> fact 5
    120

Watch out: if you pass a negative number, you’ll infinite-loop; since
this function is not tail recursive, you’ll allocate memory linearly
with time.  If this occurs in a compiled program, you’ll stack
overflow; however, GHCi will happily allow the function to continue
looping until it swaps your machine into oblivion.  Ctrl+C before it’s
too late!

Perhaps you want to avoid this.  In math, you’d write

         ⎧ undefined,  n < 0
    n! = ⎨ 1,          n = 0
         ⎩ n × (n-1)!, n > 0

You can do this in Haskell, too:

    fact n
      | n < 0  = error "negative factorial"
      | n == 0 = 1
      | n > 0  = n * fact (n - 1)

Your turn: implement the absolute value function, the unit step
function, and the Fibonacci function.


Daily Dose of Haskell, #5: Other basic data types

So far, we’ve been working entirely with numbers – integers and
floating-point values.  Haskell has several other atomic data types.
You can construct boolean values using 'True' and 'False', and you can
use character literals by surrounding them with single quotes.

    Prelude> True == False
    False
    Prelude> 'c' /= 'f'
    True

(Not-equal in Haskell is spelled '/=', because it looks like ≠.)

Just as Java has a massive number of classes, Haskell has a massive
number of compound data types.  There are a few, though, that are used
virtually everywhere.  You can build lists by enclosing values in
square brackets, and you can build tuples by enclosing values in
parentheses.  A list of characters is a string, and Haskell has
syntactic sugar for entering them – double quotes.

    Prelude> [4, 7, 3] !! 1
    7
    Prelude> ['f', 'o', 'o']
    "foo"
    Prelude> (3, "foo", True)
    (3,"foo",True)

Your turn: implement xor and nand.


Daily Dose of Haskell, #6: Basic type annotations

Haskell has strong, static typing, but so far, we haven’t explicitly
specified any types at all!  Haskell, unlike languages like Java and
C, can infer types as you use them.  However, you can specify types
explicitly using the special '::' operator, which means “has type”:

    > root2 :: Double
    > root2 = sqrt 2
    >
    > myName :: String
    > myName = "Benjamin Barenblat"

Functions have types with an arrow (->) in them.  For reasons which
will become apparent later, functions of multiple arguments have
multiple arrows:

    > add :: Integer -> Integer -> Integer
    > add x y = x + y

Types you’re already familiar with include Integer, Double, Bool,
Char, and String.  List and tuple type syntax is fairly intuitive:

    > firstPrimes :: [Integer]
    > firstPrimes = [2, 3, 5, 7, 11, 13]
    >
    > me :: (String, Integer, String)
    > me = ("Benjamin Barenblat", 22, "Portland")

Your turn: http://lpaste.net/7440378293053816832 has some simple
Haskell code to build and query a database of people.  Fill in the
commented-out type signatures.


Daily Dose of Haskell, #7: Practice day

Today, instead of introducing anything new, I’ve got a few exercises
on what’s been covered already.  You should do at least 1 and 2, and
I’d very much appreciate it if you did 5, but feel free to do the
others as well.

 1. Implement a predicate 'even' that returns True if and only if its
    argument is even.  It should have signature

        > even :: Integer -> Bool

 2. Reimplement 'even', but this time, avoid using modular
    arithmetic.  Write a recursive procedure instead.

 3. Without looking at the source, implement your own version of
    'elem'.  'elem x lst' returns 'True' if and only if 'x' is an
    element of 'lst'.  Don’t worry about annotating your function with
    a signature.

 4. Write a function

        > powMod :: Integer -> Integer -> Integer -> Integer

    such that 'powMod a x m' produces aˣ (mod m).  Please do this the
    clever way [*]. :)  Show that it works on some @i{massive} numbers
    (like, 100 digits long).

 5. Daily Dose of Haskell has been running for a week!  How am I
    doing?  Am I going too fast? too slow?  Are my exercises silly?
    Do I need to put more thought into what I’m saying?  Are you
    intimidated by people talking about endofunctors?  Feel free to
    publish your thoughts or to send them in personals.  Even if you
    think I’m doing great, I’d appreciate a response – I’m curious how
    many people are still interested.

[*] https://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method


Daily Dose of Haskell, #8: Maybe

So far, all the functions we’ve encountered have signaled error
conditions by throwing (unchecked) exceptions.  Haskell does not have
checked exceptions per se; instead, functions you anticipate will fail
regularly return the special type 'Maybe a', for some other type 'a'.
So a division function might be

    > divide :: Double -> Double -> Maybe Double
    > divide a 0 = Nothing
    > divide a b = Just (a/b)

For those coming from OO backgrounds, think of 'Maybe' as an abstract
class that has two concrete subclasses: 'Nothing' and 'Just'.  In
Haskell, we call 'Nothing' and 'Just' @i{data constructors}; they have types

    Nothing :: Maybe a
    Just :: a -> Maybe a

Note that 'Nothing' can produce a value of type 'Maybe Int', 'Maybe
Double', 'Maybe [String]', etc.  This leverages Haskell’s polymorphism
features, which we’ll discuss later.

Your turn: Write a new factorial function that doesn’t error out or
infinite loop on negative numbers but returns 'Nothing' instead.


Daily Dose of Haskell, #9: Higher-order functions

Yesterday, we talked about getting values into a 'Maybe'.  To get them
back out again, there’s a whole host of functions in Data.Maybe — but
forget them for a minute, because what you really want to use is
pattern matching.  In fact, that’s exactly how 'fromJust' is
implemented:

    > fromJust          :: Maybe a -> a
    > fromJust Nothing  = error "Maybe.fromJust: Nothing" -- yuck
    > fromJust (Just x) = x

Next up: Just like Python, Ruby, and Lisp, Haskell allows you to pass
functions to other functions as arguments.  For instance, you might
write a silly function

    > apply :: (a -> b) -> a -> b
    > apply f x = f x

This function takes two arguments: a function from as to bs, and a
value of type a.  It then applies the function to the value to produce
a value of type b.  (In fact, this function already exists; it’s the
infix operator '$', and it’s really a precedence hack.  You can think
of it as introducing an opening parenthesis that is automatically
closed at the end of the line.  For example, 'exp $ sqrt $ 2 + 3' is
the same as 'exp (sqrt (2 + 3))'.)

Your turn: Write a function of type

    > mapMaybe :: (a -> b) -> Maybe a -> Maybe b

using pattern matching on the second argument.  (Advanced students:
Yes, this is the implementation of 'fmap' for the Maybe functor.
Reimplementing it is a good exercise, so don’t just say
mapMaybe = fmap.)

Optional: Rewrite your factorial function from yesterday using
'mapMaybe'.


Daily Dose of Haskell, #10: Either

Another extremely common data type is 'Either a b'.  It has two data
constructors:

    Left :: a -> Either a b
    Right :: b -> Either a b

Thus, technically speaking, it’s a sum type (or, if you’re a C
programmer, a tagged union).  However, most of the time, people use it
as a slightly more intelligent version of 'Maybe' – 'Either String a'
is very similar to 'Maybe a', except you can provide a string on
failure.  Reusing the division function example from two days ago, one
could write

    > divide :: Double -> Double -> Either String Double
    > divide a 0 = Left "division by zero"
    > divide a b = Right (a/b)

(Hopefully, historical bias against the left side of anything is
enough to remind you that you use 'Right' for the valid result and
'Left' for the error. :)

Just like 'Maybe', you can pattern match on 'Either'’s data
constructors to yank values out of it.

Your turn: Rewrite your factorial function to return an
'Either String Integer'.  It’ll probably be useful to write a function

    > mapEither :: (r -> r') -> Either l r -> Either l r'

(Again, please don’t use 'fmap'.)

PS: After I complained a bit more, I got plenty of feedback.  If you
haven’t sent any, please do so!  If you have, thanks!  It was
extremely helpful.


Daily Dose of Haskell, #11: Defining your own data types

Push 'Maybe' and 'Either' onto your stack; we’ll come back to them in
a couple days.  In the meantime, you can define your own data types
using the 'data' keyword:

    > data Age = Years Integer
    >          deriving (Eq, Ord, Show)

(Don’t worry about the 'deriving' clause just yet; I’ll explain it
soon.)  This defines a type constructor 'Age', with a single data
constructor 'Years' that takes an 'Integer'.  The type constructor is
what you use in type signatures; the data constructor is what you use
to produce values.

    > canDrink :: Age -> Bool
    > canDrink (Years n) = n >= 21

The 'data' notation is very flexible.  You can have more than one data
constructor, and you can also define type constructors that have type
parameters.  If you’re familiar with C++ templates or Java generics,
this is exactly the same – just with much, much nicer syntax:

    > data BinaryTree a = Nil
    >                   | Node (BinaryTree a) a (BinaryTree a)
    >                   deriving (Eq, Show)

Your turn: Build a couple simple binary trees using this data type,
and write a function that does an in-order traversal of the tree.
Your function should have type

    > inOrder :: BinaryTree a -> [a]

You’ll probably want to use the list concatenation operator '++',
which has signature

    (++) :: [a] -> [a] -> [a]


Daily Dose of Haskell, #12: Data type exercise

The 'data' syntax can take a bit of getting used to, so today’s Daily
Dose is an exercise.

  1. Define a new data type 'Location' that wraps a string.

  2. Define a new data type 'Person' with a single constructor that
     accepts a name, an age, and a 'Location'.

  3. Use pattern matching to define accessor functions that accept a
     'Person' and return that person’s name, age, and location.

  4. Write a function 'visit' that takes a 'Person' and a string,
     converts the string to a 'Location', and returns a new 'Person'
     whose location is appropriately set.

  5. Define a new data type 'Class a' that represents a class of
     'a's.  You can either wrap an existing type (e.g., list) or
     define your own data structure with multiple constructors.

  6. Write functions

         > mapClass :: (a -> b) -> Class a -> Class b
         > countClass :: Class a -> Integer


Daily Dose of Haskell, #13: List constructors

We’ve already seen that you can construct lists by enclosing the
elements within brackets.  However, this is really just syntactic
sugar for the actual list representation; lists are actually defined
as something like

    data List a = Nil | Cons a (List a)

The GHC desugarer converts

    [τ] → List τ
    []  → Nil
    x:y → Cons x y

':' is right-associative, so you can write

    Prelude> 2 : 3 : 5 : 7 : []
    [2,3,5,7]

GHC also supports pattern matching on the sugared constructors:

    > myLength :: [a] -> Integer
    > myLength [] = 0
    > myLength (x:xs) = 1 + myLength xs

(By convention, destructing a cons is frequently spelled 'x:xs',
because you get one 'x' and a whole bunch of 'xs' as a result. :)
Being able to destruct lists like this makes writing recursive list
functions a @i{lot} easier!

Your turn: Using your awesome list powers, write your own versions of
'map', 'zip', and 'foldl' (fold from left to right):

    > myMap :: (a -> b) -> [a] -> [b]
    > myZip :: [a] -> [b] -> [(a, b)]
    > myFoldl :: (a -> t -> a) -> a -> [t] -> a

If you don’t know what 'foldl' does, look at the Python documentation
for 'reduce' [1].  [2] may also be helpful, but stay away from [3]
unless you’d like to be spoiled. :)

[1] http://docs.python.org/2/library/functions.html#reduce
[2] https://en.wikipedia.org/wiki/File:Left-fold-transformation.png
[3] https://en.wikipedia.org/wiki/Fold_(higher-order_function)


Daily Dose of Haskell, #14: Type classes

Eventually, you’re going to want to define some interface to which a
bunch of types adhere.  For instance, you might have

    > data Person = Person String Integer
    > data Dog = Dog String Integer

You could write individual accessor functions with types

    personName :: Person -> String
    dogName :: Dog -> String
    personAge :: Person -> Integer
    dogAge :: Dog -> Integer

but this is clunky, not to mention redundant.  (Haskell already tracks
whether you’re working with a dog or a person – why should you?)

Instead, Haskell allows you to declare an interface that both person
and dog satisfy.  To confuse the OOP folks, this is called a @i{type
class}.

    > class HasNameAndAge t where
    >   name :: t -> String
    >   age :: t -> Integer
    >
    > instance HasNameAndAge Person where
    >   name (Person n a) = n
    >   age (Person n a) = a
    >
    > instance HasNameAndAge Dog where
    >   name (Dog n a) = n
    >   age (Dog n a) = a

Now, 'name' and 'age' have exactly the behavior you expect:

    *Main> name (Person "Benjamin" 22)
    "Benjamin"
    *Main> age (Dog "Napoleon" 9)
    9

Your turn: Consider the class

    > class Extractable (t a) where
    >   first :: t -> Maybe a

Write instances of 'Extractable' for lists, 'Maybe', and
'Either String'.


Daily Dose of Haskell, #15: Currying and sections

Today, we’ll take a brief break from higher-level constructs to take a
look at a couple syntax issues we haven’t yet discussed.

You can convert any infix operator to a function by surrounding it
with parentheses, and you can convert any function to an infix
operator by surrounding its name with backticks (`).

    Prelude> (+) 2 7
    9
    Prelude> 49 `div` 2
    24

Any function with two or more arguments can be @i{curried} (partially
applied).  That is, you can apply it to fewer than all of its
arguments, and you’ll get a new function that accepts the rest and
produces a result:

    > plus x y = (+) x y
    > plusOne = plus 1

    *Main> plusOne 7
    8

There’s a nice syntactic sugar, known as @i{sectioning}, for currying
infix operators:

    > plusOne = (1+)
    > square = (^2)

    *Main> plusOne 7
    8
    *Main> square 6
    36

Your turn: Implement

    > divides :: Integer -> Integer -> Boolean
    > (><) :: (Double, Double, Double)
    >          -> (Double, Double, Double)
    >          -> (Double, Double, Double)

– that is, the divisibility predicate and the cross product over
@b{R}³.  Use your cross product implementation and sectioning to
define a function that rotates a vector 90° about the @i{x}-axis
(either direction is fine).


Daily Dose of Haskell, #16: Functors

Haskell has a whole bunch of common type classes.  Today, we’ll cover
one of the most common ones: 'Functor'.  It’s defined as

    class Functor f where
      fmap :: (a -> b) -> f a -> f b

In other words, @i{a 'Functor' is any type that can be meaningfully
mapped over}.  List is a functor.  'Maybe' is a functor.  'Either' is
a functor.  If you define a wrapper datatype

    > data Wrapper a = Wrapper a

then congratulations, you’ve defined the identity functor!
Appropriately, 'fmap' generalizes 'map', 'mapMaybe', 'mapEither', and
any other 'map' operation you can possibly think of.

Your turn: Define a data type that associates an arbitrary string with
a piece of data.  Create a 'Functor' instance for it.

(For the category theoreticians, 'Functor' is a type class
corresponding to the category-theoretic notion of an endofunctor on
Hask, the category of Haskell types.)


Daily Dose of Haskell, #17: Type polymorphism

I’ve been using type variables quite a bit.  Hopefully, you’ve
garnered some intuition about how they work; today, we’re going to
examine a few finer points that may not have come across.

Any lowercase letter in a type signature is a type variable.  It can
be instantiated with any type constructor.  In Haskell, all type
variables are implicitly universally quantified – that is,

    concat :: [[a]] -> [a]

is the same signature as

    concat :: forall a. [[a]] -> [a]

Some people prefer the second notation to the first; if you do, you
can stick '{-# LANGUAGE ExplicitForAll #-}' at the top of your module
and use 'forall' to your heart’s content.  (The '{-#' and '#-}'
surround a GHC pragma.)

You can constrain a type to be a member of one or more type classes:

    > incr :: Functor f => f Integer -> f Integer
    > ceiling' :: (RealFrac a, Integral b) => a -> b

(Don’t worry about the 'RealFrac' and 'Integral' type classes yet;
they’re just to illustrate the syntax.)  Note that the type class(es)
are to the left of a double arrow, '=>'.  (It’s totally reasonable to
think a type class as a theorems, which makes an instance a proof that
every value of a type satisfies the theorem.)

Your turn: For each of the following signatures, only one
implementation is possible!  What is it?

    a -> a
    a -> b -> a
    Either a b -> (Maybe a, Maybe b)


Daily Dose of Haskell, #18: Pointed functors

A pointed functor is a functor with a reasonable “injection” function:

    > class Functor f => Pointed f where
    >   point :: a -> f a

For instance,

    > instance Pointed Maybe where
    >   point = Just

Pointed functors turn out to be a bit of a red herring – they’re not
actually very useful for anything other than teaching.  Hence, they’re
not in base.  If you really want to use them in programming, you can
'cabal install pointed' and 'import Data.Pointed' in your Haskell
file.  However, 'Data.Pointed' literally contains the class definition
I just wrote,* so you should also feel free to just copy and paste
this class definition into your code.

Your turn: Write 'Pointed' instances for

    > data Identity a = Identity a
    >                 deriving (Eq, Show)
    > data BinaryTree a = Nil
    >                   | Node (BinaryTree a) a (BinaryTree a)
    >                   deriving (Eq, Show)
    > data Stack a = Empty
    >              | Push a (Stack a)

as well as for 'Either a' and list.

* Okay, I lied.  Data.Pointed has the definition

    class Pointed f where
      point :: a -> f a

That an instance of 'Pointed' need not be a instance of 'Functor' is
due to a terrible historical mistake that nobody’s worked up the
courage to fix yet.  Anything you declare as a 'Pointed' better be a
'Functor' too, though!


Daily Dose of Haskell, #19: Combining functorized values

Functors support

    fmap :: Functor f => (a -> b) -> f a -> f b

So you can do

    Prelude> fmap (+3) (Just 7)
    Just 10

– that is, you can mutate data inside a functor.  But what if you want
to @i{combine} two pieces of data inside a functor?  For example, how
should we define 'add' such that

    add (Just 3) (Just 7)

evaluates to 'Just 10'?

We need something more powerful than just 'fmap'; we need a mechanism
to combine two functorized values using an arbitrary function.

Your turn: Write functions of type

    > applyMaybe    :: (a -> b -> c) -> Maybe a    -> Maybe b    -> Maybe c
    > applyIdentity :: (a -> b -> c) -> Identity a -> Identity b -> Identity c
    > applyList     :: (a -> b -> c) -> [a]        -> [b]        -> [c]

that apply the first argument to the functorized values inside the
second and third arguments.  The Haskell convention for 'applyList'’s
semantics is to apply the function to all possible argument pairs from
the two lists – e.g.,

    applyList (+) [1,2] [10,20]

should produce

    [11,21,12,22]


Daily Dose of Haskell, #20: Applicative functors

Yesterday, we saw that certain functors have mechanisms to combine two
functorized values.  If those functors are pointed, they’re called
@i{applicative functors}.  Haskell’s applicative functors are defined
in Control.Applicative;¹ I’ve reproduced the class definition below:

    class Functor f => Applicative f where
      pure :: a -> f a -- equal to 'point' from Data.Pointed
      (<*>) :: f (a -> b) -> f a -> f b

      (*>) :: f a -> f b -> f b
      (*>) = liftA2 (const id)

      (<*) :: f a -> f b -> f a
      (<*) = liftA2 const

This class definition looks a bit weird – implementations are provided
for two of the functions!  This is perfectly legal – in an instance,
you can override the preimplemented functions if you desire.

Note that in order to keep applicative functors well-behaved (i.e.,
close to their category theory counterparts), any instance of
'Applicative' must obey the four @i{applicative laws} detailed in the
documentation.  Haskell is insufficiently powerful to throw compiler
errors for instances that do not obey, so it’s up to you to make sure
your instances obey the laws!

(There are technically two laws for functors as well – see the
'Functor' documentation² – but they’re very straightforward.)

Your turn: Implement 'Applicative' instances for the identity and
maybe functors (easy).  Convince yourself that these implementations
satisfy the applicative laws (harder).  For bonus points, formalize
the applicative laws in the theorem prover of your choice and prove
that your implementations satisfy the laws!

¹http://hackage.haskell.org/package/base/docs/Control-Applicative.html#t:Applicative
²http://hackage.haskell.org/package/base/docs/Control-Monad.html#t:Functor


Daily Dose of Haskell, #21: Monads, day 1

Wow, we’re already at monad day.  Go figure.

A functor is pointed if it supports the extra operation 'point'.  A
pointed functor is applicative if it supports the extra operation
'<*>'.  Continuing the pattern, an applicative functor is a monad if
it supports the extra operation 'join':

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

That is, join flattens two levels of monads.

In contrast to many of the instances you’ve written so far, 'join' is
usually pretty easy to write.

Your turn: Write implementations for
    joinMaybe  :: Maybe (Maybe a) -> Maybe a
    joinList   :: [[a]] -> [a]
    joinEither :: Either a (Either a b) -> Either a b

Additional note: Feeling lost?  It’s okay.  This stuff is weird and
abstract and isn’t built into other languages.  Go read the first few
sections of <http://www.haskell.org/haskellwiki/Typeclassopedia>, and
ask questions here.

Additional note: Feeling bored?  Sorry.  I’ve been trying to keep this
as simple and short as possible, which means I’ve skipped over some
stuff.  Go read the first few sections of
<http://www.haskell.org/haskellwiki/Typeclassopedia>, and ask
questions here.


Daily Dose of Haskell, #22: Bind (monads, day 2)

You can use 'join' to chain together two monadic functions:

    > safeDiv :: Double -> Double -> Maybe Double
    > safeDiv n 0 = Nothing
    > safeDiv n d = Just $ n/d
    >
    > safeLog :: Double -> Maybe Double
    > safeLog n
    >   | n <= 0 = Nothing
    >   | n > 0  = Just $ log n
    >
    > logOfDiv :: Double -> Double -> Maybe Double
    > logOfDiv n d = join $ fmap safeLog $ safeDiv n d

This pattern of 'fmap followed by 'join' is really ugly when you get
more than two functions.  For instance, if you want to compute
17 / ln(n/d), you’d need to type

    join $ fmap (safeDiv 17) join $ fmap safeLog $ safeDiv n d

Fortunately, we can define a nice function that does a join and an fmap all in
one:

    > bind :: Monad m => m a -> (a -> m b) -> m b
    > bind val f = join $ fmap f val

To make writing chains of monadic computations easier, Haskell uses
the famous infix operator '>>=' to refer to 'bind'.  So instead of the
monstrosity above, we can write

    safeDiv n d >>= safeLog >>= safeDiv 17

Your turn:

  1. Implement bind for lists, 'Either a', and 'Maybe' … without using
     join.

   2. Convince yourself that join and bind are equally powerful – each
      can be defined in terms of the other.


Daily Dose of Haskell, #23: IO

Monads have a special role in Haskell: they are the gatekeepers for
input and output.  Any function that gives output to the user or
receives output from the user has type 'IO a', for some 'a'; 'IO' is a
special, privileged monad that encapsulates input and output.  (It’s
really actually privileged – the compiler treats it specially.)  For
instance,

    putStrLn :: String -> IO ()
    getLine :: IO String

('()', pronounced “unit”, is the Haskell analogue of 'void'.  It is
the type with exactly one value, also spelled '()' and pronounced
“unit”.)

Every Haskell program has exactly one function called 'main', which
has type 'IO ()'.  With that in mind, we can now (finally!) write a
hello-world program:

    > main :: IO ()
    > main = putStrLn "Hello, world!"

Save this to a file (e.g., 'hello.hs'), and run

    $ ghc --make -o hello hello.hs

You’ll get an executable – your first real, executable Haskell
program.  Congratulations!

Your turn: Use what you know about monads to write an executable
Haskell program that reads a single line from standard input and
outputs it to standard output.


Daily Dose of Haskell, #24: More monad operators

So far, the only monad operation we’ve seen is '>>='.  There are two
other, somewhat lesser operators.

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

Just as 'pure' is the applicative version of 'point', 'return' is the
applicative version of 'pure'.  (All three of these functions should
do exactly the same thing!)  'return' is somewhat unfortunately named;
it has absolutely nothing to do with the 'return' keyword found in
other languages.

'>>', pronounced “then”, sequences two monadic operations but
/discards/ the result of the first.  It’s usually defined as

    a >> b   =   a >>= \_ignored -> b

Your turn: Use the monad operators 'return', '>>', and '>>=' to write
an executable Haskell program that prompts the user for his or her
name, reads the name from standard input, and tells the user hello.
(Please don’t use do-notation; we’ll be covering that tomorrow.)


Daily Dose of Haskell, #25: do-notation

Spoiler alert: Here’s my answer to yesterday’s exercise:

    > main :: IO ()
    > main =
    >   putStrLn "What is your name?"       >>= \_ ->
    >   getLine                             >>= \name ->
    >   putStrLn ("Hello, " ++ name ++ "!")

The first line of 'main' could end with '>>' instead of '>>= \_ ->',
but bear with me for a second.  The point is, this looks suspiciously
like an imperative program – modulo some bookkeeping to keep track of
the results of each operation.

Because bookkeeping is unpleasant, Haskell’s parser supports a nice
syntactic sugar that allows you to express monadic computations as
pseudoimperative programs:

    > main :: IO ()
    > main = do
    >   putStrLn "What is your name?"
    >   name <- getLine
    >   putStrLn ("Hello, " ++ name ++ "!")

You start a block with the keyword 'do', and within a 'do' block, you
can “extract” a result from the monad of discourse using the '<-'
syntax.  Note that '<-' is not a function – it’s syntax!  All 'do'
blocks get desugared at compile-time to a series of monadic operations
sequenced with '>>='.

One other gotcha with do-notation: Instead of 'let foo = bar in …',
you simply write 'let foo = bar'.  (This is equivalent to 'foo <-
return bar'.)

Haskell programmers usually use do-notation rather than explicit
monadic binding.

Your turn: Write a Haskell program (using do-notation) that prints the
first 10 lines from /usr/share/dict/words.  Useful functions for this
exercise include

    lines :: String -> [String]
    take :: Int -> [a] -> [a]
    readFile :: FilePath -> IO String
    unlines :: [String] -> String


Daily Dose of Haskell, #26: Hangman, day 1

For the next few days, we’ll be going through an extended exercise to
get some real experience building a Haskell program – a hangman game,
à la 6.S189’s project 1.

If we’re going to build a hangman game, we need the computer to pick a
random word.  The naïve way to do this is to use 'lines . readFile' to
get a list of words from a file, generate a random index, and use that
word.  However, working with a list of all the words in (e.g.)
/usr/share/dict/words is probably a bad idea – Haskell lists are
linked lists, so we’ll be doing a lot of O(n) operations.

Instead, we’ll use the 'Data.Vector' module, which provides a
highly-optimized array data structure that supports O(1) indexing and
length operations.  Take a few minutes to familiarize yourself with
the interface at
http://hackage.haskell.org/package/vector/docs/Data-Vector.html.

Now create a file and stick

    > import qualified Data.Vector as Vector

at the top.  (This brings 'Data.Vector' into scope, allowing you to
access all its names by prefixing them with 'Vector' – e.g.,
'Vector.head', 'Vector.snoc'.)  Finally, write a function

    > loadWords :: FilePath -> IO (Vector.Vector String)


Daily Dose of Haskell, #27: Hangman, day 2

Picking a random number in Haskell turns out to be surprisingly
confusing, because seeding the PRNG is an I/O operation (doing it
reasonably requires getting more entropy from the system), and
unfortunately, the PRNG needs to get periodically reseeded.  You have
about six different choices for how to deal with this, including

  – carry around a PRNG object that you have to manually reseed every
    so often

  – make every PRNG read live in the 'IO' monad, and automatically
    reseed when necessary

  – use the 'Random' monad to abstract the first approach

I’m a fan of approach #3, but approach #2 is probably simpler for
today’s exercise.  You can, of course, take whichever approach you
want for today’s exercise.  (Note that if you want to use approach #3,
you’ll need to 'cabal install MonadRandom'.)

Anyway, today’s exercise: Write a function

    > randomWord :: Vector.Vector String -> IO String

that, given a vector of words, picks a random word.  Relevant
documentation:

    https://hackage.haskell.org/package/random/docs/System-Random.html
    https://hackage.haskell.org/package/MonadRandom/docs/Control-Monad-Random.html


Daily Dose of Haskell, #28: Hangman, day 3

Fundamentally, we can think of a hangman program as a state machine.
The state is the secret word and the letters that have been guessed.
On each turn, there’s one input (a new letter), and the program
updates the state accordingly.  Haskell provides a useful monad (the
'State' monad) for modeling state machines, but for now, we’ll just
pass the state around.

Your challenge today:

  1. Define a data type for the state of the hangman game.

         > data HangmanState = {- your code here -}
         >                   deriving (Eq, Show)

     Exactly how you store the state is up to you; however, you may be
     interested in the 'Data.Set' module, which exposes a
     size-balanced binary tree.  The documentation is available at
     https://hackage.haskell.org/package/containers/docs/Data-Set.html.

  2. Write functions

         > initialState :: String -> HangmanState
         > updateState :: Char -> HangmanState -> HangmanState

  3. Write functions

         > nGuessesRemaining :: HangmanState -> Integer
         > hasWon :: HangmanState -> Bool


Daily Dose of Haskell, #29: Hangman, day 4

Today, we’ll turn our attention to the frontend of the hangman game.

  1. Write a function

         > announceState :: HangmanState -> IO ()

     that prints a pleasing representation of the hangman state to the
     user.  (This could be as simple as

         You have 3 guesses left!
         Secret word: -I---I--
         Guessed letters: EAOI

     or you can go totally crazy and use ASCII art graphics,
     ncurses-based animation, etc.  The world is your oyster.)

  2. Write a function

         > getGuess :: IO Char

     that prompts the user for a guess and reads one (and only one)
     character from standard input.  If the user types more than one
     character, 'getGuess' should ask again.

  3. Write functions

         > announceWin :: IO ()
         > announceLoss :: IO ()

     that tell users they’ve won or lost, respectively.


Daily Dose of Haskell, #30: Hangman, day 5

Today’s exercise is to finish your hangman game into an executable!  I
have a lurking suspicion that many of you have already done so,
though, so here are some extra, optional challenges:

  – Quite a few words in /usr/share/dict/words are … difficult to
    guess, because they are too short (e.g., “I”) or proper names
    (e.g., “Adonis”).  Filter out all proper names and words under
    five letters from the word list before you pick a word.

  – Give the user an option to ask the computer to guess for him or
    her.  The computer should base its guess on English
    letter-frequency order – see
    <https://en.wikipedia.org/wiki/Letter_frequency#Relative_frequencies_of_letters_in_the_English_language>.
    For double bonus points, analyze the /usr/share/dict/words corpus
    to produce your own letter frequency table!

  – Make it possible to play multiple games without restarting the
    executable.  Don’t reload the word list for each game!

  – Allow multiple simultaneous guesses.

Once you’re done, pat yourself on the back: You’ve created a real,
nontrivial Haskell executable.


Daily Dose of Haskell, #31: A deeper look at functors

If you’ve made it this far, congratulations!  You have the tools to
build small but nontrivial Haskell executables.  However, your code is
probably not very idiomatic, and you probably don’t have the knowledge
to understand most of the Haskell code on the Web.  As a first step
toward that knowledge, we’re going to take a deeper look at the
functor-pointed-applicative-monad hierarchy, which I moved through as
fast as possible so we could get on to writing hangman.

Today’s exercise is thus to revisit the best type class tutorial on
the Web – the Typeclassopedia* – and read (or reread) sections 1–3.
While it’s not required, I highly recommend you also do the associated
exercises.

Additionally, DDoH has been running for a bit over a month, so I’d
like some more feedback!  How’s pacing been?  Have the exercises been
too easy? too hard? too long?  What topics would you like to see DDoH
focus on in the next month?


* https://www.haskell.org/haskellwiki/Typeclassopedia


Daily Dose of Haskell, #32: A deeper look at applicative functors

Today, we’ll start with a quick exercise to get your 'Functor'
thoughts flowing:

  – Write a data structure that lets you associate a file-line-column
    triplet with a piece of data.

  – Is this a functor?  If so, write a 'Functor' instance for it.  If
    not, explain why not.

(This comes straight out of 6.035 last term.)

Okay, all warmed up?  Good.  Now go (re)read section 4 of the
Typeclassopedia.  Once more, doing the exercises is highly
recommended.

Also, are you on the Haskell IRC channel yet?  If not, you should take
a look at irc://irc.freenode.net/haskell.  You’ll learn a lot really
fast.


Daily Dose of Haskell, #33: Can you guess what comes next?

Go (re)read section 5 of the Typeclassopedia.  Once more, doing the
exercises is highly recommended.  You’ll encounter a number of monads
we haven’t discussed before, including 'Reader', 'Writer' and 'Cont'.
We’ll be doing a lot of monad exercises in the next week or so to help
you get more comfortable with them, but in the meantime, if you start
being confused, come back here and talk to people.  Only by
understanding the concrete examples of monads that pervade the Haskell
standard library can you truly understand the abstraction that monads
provide.  At least that’s what byorgey says:
http://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/


Daily Dose of Haskell, #34: Stateful hangman

If you missed it, DDoH is switching to a weekday schedule.  We’re
getting into higher-level territory now (not to mention nearing the
end of term), and I’d like you to have weekends to get unhosed.

Today’s exercise is to get familiar with one of the more useful monads
- the 'State' monad – by working it into your hangman game.  You had a
function

    updateState :: Char -> HangmanState -> HangmanState

which can be changed to

    > import Control.Monad.State (State)
    > updateState :: Char -> State HangmanState ()

Go for it – rewrite your 'updateState' function to use the 'State'
monad.  You’ll probably want to refer to the documentation for the
'State' monad API
<https://hackage.haskell.org/package/mtl/docs/Control-Monad-State-Lazy.html>.


Daily Dose of Haskell, #35: MonadRandom

In addition to the well-known monads in base, there are a number of
other useful monads on Hackage.  One of the more exciting ones is the
random monad, which I alluded to in DDoH #27.  It has the form

    Rand g a

where g is the generator in use.  It’s isomorphic to a state monad,
with the state being the state of the random number generator
currently in use.  (Minor nitpick: 'Rand' is not a monad; it has the
wrong kind.  'Rand g' is the actual monad.)

Your turn: Go 'cabal install MonadRandom', and look at the API
documentation at

    https://hackage.haskell.org/package/MonadRandom/docs/Control-Monad-Random.html

Now, write a function

    > randomElement :: Vector a -> Rand StdGen a

that picks a random element from a vector, and replace 'randomWord'
from your hangman game with a call to 'evalRandIO . randomElement'.


Daily Dose of Haskell, #36: Brainfuck, day 1

Time for another extended exercise!  This time, we’re going to write
an interpreter for a variant of Brainfuck
<http://www.muppetlabs.com/~breadbox/bf/>, a tiny, Turing-complete,
esoteric programming language.

Brainfuck’s concrete syntax consists of only eight instructions.
However, its abstract syntax uses only seven – six atomic operations
and one looping construct.  Your task today is to write an algebraic
data type describing Brainfuck abstract syntax:

    > data BFProgram = BFProgram [BFInstruction]
    >                deriving (Eq, Show)
    > data BFInstruction = {- your code here -}
    >                    deriving (Eq, Show)

For bonus points, write a pretty-printer that converts an instance of
'BFProgram' to its ascii Brainfuck representation.  For total
overkill, use the 'pretty' pretty-printing combinator library off
Hackage.


Daily Dose of Haskell, #37: Brainfuck, day 2

One programs in Brainfuck by manipulating values on a tape (this is a
Turing machine simulator, after all).  Your challenge today is to
define the state of your Brainfuck interpreter.  You can implement a
bounded tape (as in the original implementation), a semi-infinite tape
(with indices 0, 1, …), or a truly infinite tape (with indices …, -1,
0, 1, …) – it’s up to you.  Don’t be afraid to use an infinite tape –
Haskell’s laziness makes working with infinite data structures easy.

Anyway, more concretely, you should write

    > data BFState = {- your code here -}
    > incrementPointer :: BFState -> BFState -- >
    > decrementPointer :: BFState -> BFState -- <
    > getCellValue :: BFState -> Int
    > setCellValue :: Int -> BFState -> BFState

Use these primitives to implement

    > incrementCellValue :: BFState -> BFState -- +
    > decrementCellValue :: BFState -> BFState -- -
    > displayCellValue :: BFState -> IO ()     -- .
    > readCellValue :: BFState -> IO BFState   -- ,


Daily Dose of Haskell, #38 and #39: Monad transformers (Brainfuck, days 3 and 4)

This is a double Daily Dose – that is, it is intended to take two
days.  Consequently, there will be no DDoH tomorrow.

At this point, we’d like to write an evaluation function that
evaluates a 'BFInstruction' and updates the associated 'BFState'.
However, if you try to do this, you’ll quickly run into a nasty
problem: you’d like to use the 'State' monad, but you need to do I/O!

One solution which is used extensively throughout the Haskell
ecosystem is the notion of a @i{monad transformer}, a construct which
allows you to “stack” the features of several monads.  Like monads,
monad transformers are quite abstract; instead of trying to squeeze
them into a few DDoH instances, like I did for monads, I’ll simply
point you toward [1], which is a good and relatively brief
introduction.

Don’t worry about becoming a master of transformers.  There’s plenty
of time for that later.  In the meantime, focus on getting
sufficiently comfortable with transformers that you can write

    > evalInstruction :: BFInstruction -> {- fill in the type -}
    > evalInstruction instruction = {- your code here -}

Advanced aside: While the Haskell community is pretty confident that
monads are cool and froody, we’re extremely concerned about how nasty
monad transformers can be, especially when you have a half dozen of
them all stacked up.  ezyang has a good summary of the problems with
monad transformers [2].  I’m excited by monad layers [3], but I have
not used them enough to determine just how well they fix the problems
with transformers.

[1] https://en.wikibooks.org/wiki/Haskell/Monad_transformers
[2] http://blog.ezyang.com/2013/09/if-youre-using-lift-youre-doing-it-wrong-probably/
[3] https://hackage.haskell.org/package/layers


[Editor’s note: andersk notes that layers seems to solve most existing
problems with transformers, but lacks a clear path forward in the face
of as yet undiscovered ones:

    Huh.  This package looks like an attempt to jam the transitive
    closure of all previously discovered ideas in the monad
    transformer space along with some random hacks into one package to
    solve all previously enumerated problems.  The resulting
    complexity gives me very little confidence that this will solve
    new problems.

I lack the domain knowledge to see this for myself, but I definitely
trust Anders’ judgment on these types of questions (actually, on most
Haskell questions), so I’ll probably be staying away from layers in
the future.  The quest for non-horrendous mechanisms for combining
monads continues.]


Daily Dose of Haskell, #40: While loops (Brainfuck, day 5)

Shortly, we’ll be writing our master evaluation function.  For the time being,
assume it exists:

    > evalProgram :: BFProgram -> StateT BFState IO ()
    > evalProgram = undefined

With that signature in mind, let’s look at while loops: Write

    > evalWhile :: BFProgram -> StateT BFState IO ()

which should interpret its 'BFProgram' argument as the body of a while loop and
evaluate it with the appropriate semantics.  Note that Haskell does not require
any explicit declarations for mutually recursive functions – all functions
defined in the same module at the top level are all able to call each other at
any time.


Daily Dose of Haskell, #41: Brainfuck, day 6

You’ve written functions 'evalInstruction' and 'evalWhile'.  Now, go
for the kill: write 'evalProgram', which accepts a 'BFProgram' and
interprets it.

Congratulations!  The hard part is over.  Now comes the easy part:
actually parsing real Brainfuck programs (inasmuch as any Brainfuck
programs can be called “real”).  We could use lexer and parser
generators like Alex and Happy for this, or we could use a parser
combinator library like Parsec or Attoparsec; however, all are serious
overkill for a language as simple as Brainfuck.  Instead, we’ll be
writing a simple recursive-descent parser.

First step: Get rid of comments.  Write a function

    stripComments :: String -> String

that removes all characters that do not represent Brainfuck
instructions.


Daily Dose of Haskell, #42: Brainfuck, day 7

Today, we’ll start writing the actual meat of our parser.  There are a
variety of ways to structure a Haskell parser; one reasonable one is
to use a state monad where the state is the unparsed tokens in the
input stream and the result is an abstract syntax tree.  Thus,

    > parseToken :: State String BFInstruction

might be a function that eats one character off the input stream and
produces a single AST node.  Today, you should implement 'parseToken'
for all tokens except '[' and ']'.  (Just error out with an
'undefined' if you encounter those.)  Remember to update your state as
you go!


Daily Dose of Haskell, #43: Brainfuck, day 8

'parseToken' works pretty well, but it’s not quite what we want: it
has no way to signal an end-of-file condition.  Change your
'parseToken' such that it has signature

    > parseToken :: State String (Maybe BFInstruction)

(Advanced readers may wonder why we’re not using a 'StateT String
Maybe' instead of wrapping the 'Maybe' monad.  It’s because I’m
hesitant to introduce 'MonadPlus' right now.)


Daily Dose of Haskell, #44: Brainfuck, day 9

Now we have a function that parses one token; next we need a function
that parses a whole stream.  Write

    > parseTokens :: State String [BFInstruction]

that continues running 'parseToken' until it returns 'Nothing'.


Daily Dose of Haskell, #45: Brainfuck, day 10

With 'parseTokens' in hand, you can now fill in the 'undefined' cases
in 'parseToken' – namely, '[' and ']'.  When 'parseToken' encounters a
'[', it should proceed forward until in encounters a matching ']',
storing the tokens in-between in the 'BFProgram' inside a 'While'.
There are a couple different ways to do this; I recommend starting by
simply not handling nested blocks, after which a reasonable strategy
to handle nested ones should make itself apparent.


Daily Dose of Haskell, #46: Brainfuck, day 11

At this point, writing

    > parseProgram :: State String BFProgram

should be totally trivial.  It shouldn’t be too hard to fill in the
body of 'evalProgram', either!  Do both of those things now.


Daily Dose of Haskell, #47: Brainfuck, day 12

We’re almost there!  Now that the parser’s complete, fill in

    > evalProgram :: BFProgram -> StateT BFState IO ()


Daily Dose of Haskell, #48: Done

We still have one more issue with our backend: 'evalInstruction' is
not total – it lacks a case for 'While'.  Fill in that case now.

Now comes the fun part: Write a function

    > loadAndExecute :: FilePath -> IO ()

that accepts a file path and
  – reads the file,
  – strips out comments,
  – parses it, and
  – runs it.

Be sure to use 'evalStateT' when you actually run the program!
Remember, our state is an infinite tape, and Haskell will get very
unhappy trying to print an infinite tape.

Here’s a hello world program (straight off Wikipedia) you can use to
test your implementation:

    ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

For something a bit more exciting, check out
<http://esoteric.sange.fi/brainfuck/bf-source/quine/quine410.b>, which
is, as its name suggests, a 410-byte Brainfuck quine.  My
implementation took a few seconds to crunch through this, but it
worked!


This concludes Daily Dose of Haskell for the time being.  It may
revive again in the future, but my attention and yours have clearly
turned elsewhere.  Again, if you’re interested in continuing Haskell
work, let me know – a Scheme compiler is the next big project, and I
suspect it’s going to be pretty awesome. :)